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.

In the optimization version of this problem, we are given a situation of shareholdership, and we aim at computing 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)

INPUT

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

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

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

controller(c1). controller(c2).

toBeControlled(c4).

POSSIBLE OUTPUTS

buy(c1,p1,c2,30,900).

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

Problem peculiarities

Type: Optimization/Beyond-NP Competition: Model & Solve only

Besides its companion benchmark, this problem adds the requirement of finding an optimal solution, making the problem expectedly computationally harder. As its companion problem, its natural declarative specification requires the availability of an aggregate quantifier (a sum) which is recursively dependent from the predicate one aggregates on.

Author(s)

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