welcome: please sign in

Upload page content

You can upload content for the page named below. If you change the page name, you can also upload content for another page. If the page name is empty, we derive the page name from the file name.

File to load page content from
Page name
Comment

location: ProblemsDescription / CompanyControlsOptimize

Company Controls Optimize

Contents

  1. Company Controls Optimize
    1. Problem Description
    2. Input format
    3. Output format
    4. Example
    5. Author(s)

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.

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

Author(s)

Author: Mario Alviano
Affiliation: https://www.mat.unical.it/aspcomp2011/ProblemsDescription/CompanyControlsOptimize