Class Tree
Description Company Controls is a problem in the area of stock market, in which the goal is to determine the pair of companies X,Y such that X controls Y, given information on stock possessions of companies.

We are interested in an extension of this problem requiring an optimization process.

Given a situation of shareholdership, compute a cost-minimal set of purchases such that at least one company in a given set A controls a specific company B.

Remind that, in order to control a company Y, a company X has to exert control over more than 50% of the stock of Y. Company X can exert control over stock of Y in two different ways: X itself may possess a certain percentage of stock of Y, in this case we say that X directly exerts control over the respective percentage of stock of Y.
Alternatively, if X controls a company Z, which exerts control over stock of Y, then we say that X indirectly exerts control over the respective stock of Y. Company then exerts control over the sum of stock of Y over which it directly and indirectly exerts control.

The input is comprised of the set of all the companies, the percentages of directly owned stock, the set A of controller companies and the company B to be controlled. Moreover, a set S of on sale stock packages
is given.

More details about the original version of the problem can be found in

* Inderpal Singh Mumick and Hamid Pirahesh and Raghu Ramakrishnan, "The Magic of Duplicates and Aggregates", Proceedings of the 16th International Conference on Very Large Data Bases (VLDB'90),
pp. 264-277.
* David B. Kemp and Peter J. Stuckey, "Semantics of Logic Programs with Aggregates", Proceedings of the International Symposium on Logic Programming (ISLP'91), pp. 387-401.

Input format

The set of companies is specified by instances of "company", for example

company(c1). company(c2). company(c3). company(c4).

The percentages of directly owned stock is given by instances of "owns", for example

owns(c1,c2,30). owns(c1,c3,20). owns(c1,c4,20).

The packages on sale are specified by instances of "onSale(P,Y,S,C)", where P is the ID of the package, S is the percentage of Y on sale, and C is the cost of the package, for example

onSale(p1,c2,30,900). onSale(p2,c3,10,550). onSale(p3,c4,15,550).

Companies in the set A are specified by instances of "controller", for example

controller(c1). controller(c2).

The company B to be controlled is specified by an instance of"toBeControlled", for example


Output format

The output should be specified by instances of "buy(X,P,Y,S,C)", where X is the company which bought the package onSale(P,Y,S,C). For example, a correct answer for the input above could be


This is also an optimal solution, while the following is correct but not optimal:

buy(c2,p2,c3,10,550). buy(c2,p3,c4,15,550).

Authors: Mario Alviano
1 - 1 of 1