Company Controls Optimization version
Problem 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).
owns(c2,c3,45).
owns(c3,c4,40).
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
toBeControlled(c4).
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
buy(c1,p1,c2,30,900).
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
|