welcome: please sign in
location: FinalProblemDescriptions / StrategicCompanies

Strategic Companies

Problem Description

Strategic companies is a well-known NPNP-complete problem that has often been used for systems comparisons, and also in the previous ASP Competitions.

In the Strategic Companies problem, a collection

of companies is given, for some m>=1. Each company produces some goods in a set G, and each company ci in C is possibly controlled by a set of owner companies Oi (where Oi is a subset of C, for each i=1,...,m). In this context, a set C' of companies (i.e., a subset of C) is a "strategic set" if it is minimal among all the sets satisfying the following conditions:

In our setting, instances are subject to two additional restrictions:

  1. each product is produced by at most four companies; and
  2. each company is controlled by at most four companies.

Under these restrictions the problem is still NPNP-complete.
Instances of strategic companies are encoded by means of the predicates produced_by and controlled_by. In particular, there is a fact producedBy(p,c1,c2,c3,c4) when a product p is produced by companies c1, c2, c3 and c4, and a fact controlledBy(c,c1,c2,c3,c4) when a company c is controlled by companies c1, c2, c3 and c4. If a product p is produced by less than four companies (but at least one), the atom produced_by(p,c_a,c_b,c_c,c_d) contains repetitions of companies. For instance, producedBy(p,c_a,c_b,c_c,c_c) is used for representing that p is produced solely by ca, cb and cc. Analogously, if a company c is controlled by less than four companies.

The goal of the problem is a follows: given two distinct companies ci,cj in C, we ask for checking the existence of a strategic set C' such that ci and cj occur in C'.

Predicates

Input format

An instance of Strategic Companies is modeled by the following facts that will be provided in the input file:

For instance:

produced_by(pasta,barilla,amato,dececco,divella). produced_by(tonno,callipo,star,almera,asdomar).
controlled_by(callipo,star,almera,asdomar,barilla). controlled_by(barilla,callipo,almera,dececco,star). 
strategic_pair(callipo,barilla).

Output format

For strategic_pair(c1,c2) in input, if c1 and c2 jointly belong to a minimal strategic set, the output must contain a number of ground atoms of the form strategic(c_i) (where "strategic(c_i)" stands for "company c_i is strategic") encoding the minimal strategic set which c1 and c2 belong to.

Example(s)

Input: produced_by(pasta,barilla,amato,dececco,divella). produced_by(tonno,callipo,star,almera,asdomar). controlled_by(callipo,star,almera,asdomar,barilla). controlled_by(barilla,callipo,almera,dececco,star). strategic_pair(callipo,barilla).

Output: strategic_pair(c1,c2).

Notes and updates

Note that this is a search problem, despite the seemingly presence of a query in input. With respect to former edition of the competition, the output format requires an entire strategic set to be output, and not just the subpart of the set showing that c1 and c2 belong to it.

Problem Peculiarities

Type: search/Beyond-NP Competition: both M&S and System competition

This problem is challenging both from the modelling point of view (it is required the availability of constructs allowing an "\exist \forall" quantification over solutions, or some appropriate optimization construct), and from the computational point of view.

Author(s)

ASP Competition 2011: FinalProblemDescriptions/StrategicCompanies (last edited 2011-02-02 17:55:02 by MarioAlviano)