Company Controls Optimize

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 the following papers:

* 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.

Predicates

• Input: company/1, owns/3, onSale/4, controller/1, toBeControlled/1

• Output: buy/5

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).

Example(s)

Author(s)

• Author: Mario Alviano
  • Affiliation: University of Calabria, Italy