welcome: please sign in
location: Diff for "FinalProblemDescriptions/StrategicCompanies"
Differences between revisions 1 and 18 (spanning 17 versions)
⇤ ← Revision 1 as of 2011-01-18 16:00:09 →
Size: 3476
Editor: CarmenSantoro
Comment:
← Revision 18 as of 2011-02-02 17:40:25 → ⇥
Size: 4793
Editor: MarioAlviano
Comment: Mi ha cancellato la pagina!
Deletions are marked like this. Additions are marked like this.
Line 7: Line 7:
* Input Predicates: produced_by/5, controlled_by/5
* Query Predicate: query/2

* Output Predicates: strategic/1

Strategic companies is a well-known NP^NP-complete problem that has often been used for systems comparisons, and also in the previous ASP Competitions.		 Strategic companies is a well-known NP^NP^-complete problem that has often been used for systems comparisons, and also in the previous ASP Competitions.
Line 16: Line 11:
   C = c_1, ..., c_m   C = c,,1,,, ..., c,,m,,
Line 18: Line 13:
of companies is given, for some m>=1. Each company produces some goods in a set G, and each company c_i in C is possibly controlled by a set of owner companies O_i (where O_i 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: of companies is given, for some {{{m>=1}}}. Each company produces some goods in a set {{{G}}}, and each company c,,i,, in C is possibly controlled by a set of owner companies O,,i,, (where O,,i,, 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:
Line 20: Line 15:
 - Companies in C' produce all goods in $G$;  * Companies in C' produce all goods in G;
 * If O,,i,, is a subset of C', the associated company c,,i,, must belong to C'(for each i=1,...,m). <<BR>>
Line 22: Line 18:
 - If O_i is a subset of C', the associated company c_i must belong to C'(for each i=1,...,m$. In our setting, instances are subject to two additional restrictions:
Line 24: Line 20:
In our setting, instances are subjected to two additional restrictions:  1. each product is produced by at most four companies; and
 1. each company is controlled by at most four companies. <<BR>>
Line 26: Line 23:
 1. each product is produced by at most four companies; and Under these restrictions the problem is still NP^NP^-complete. <<BR>>
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 c,,a,,, c,,b,, and c,,c,,. Analogously, if a company c is controlled by less than four companies.
Line 28: Line 28:
 2. each company is controlled by at most four companies. The goal of the problem is a follows: given two distinct companies c,,i,,,c,,j,, in C, we ask for checking the existence of a strategic set C' such that c,,i,, and c,,j,, occur in C'.
Line 30: Line 30:
Under these restrictions the problem is still NP^NP-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 c_a, c_b and c_c. Analogously, if a company c is controlled by less than four companies.		 == Predicates ==
Line 35: Line 32:
Moreover, two distinct companies c_i,c_j in C are provided in input (by means of predicate query), and the existence of a strategic set C' such that c_i and c_j occur in C' has to be checked.  * '''Input''': {{{produced_by/5, controlled_by/5, strategic_pair/2}}}

 * '''Output''': {{{strategic/1}}}
Line 39: Line 38:
An instance of STRATCOMP is modeled by the following facts that will be provided in the input file: An instance of Strategic Companies is modeled by the following facts that will be provided in the input file:
Line 41: Line 40:
 - A set of facts of the form produced_by(p,c1,c2,c3,c4), where produced_by(p,c1,c2,c3,c4) means that product P is produced by companies c1, c2, c3 and c4;  - A set of facts of the form {{{produced_by(p,c1,c2,c3,c4)}}}, where {{{produced_by(p,c1,c2,c3,c4)}}} means that product P is produced by companies c1, c2, c3 and c4;
Line 43: Line 42:
 - A set of facts of the form controlled_by(c,c1,c2,c3,c4), where controlled_by(c,c1,c2,c3,c4) means that company c is jointly controlled by c1, c2, c3 and c4;  - A set of facts of the form {{{controlled_by(c,c1,c2,c3,c4)}}}, where {{{controlled_by(c,c1,c2,c3,c4)}}} means that company c is jointly controlled by c1, c2, c3 and c4;
Line 45: Line 44:
 - A ground query atom of the form query(c1,c2), specifying the query goal: Do c1 and c2 belong to a (minimal) strategic set?  - A ground fact of the form {{{strategic_pair(c1,c2)}}}, specifying the query goal: is there a strategic set containing both c1 and c2?

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).
}}}
Line 48: Line 54:
For instance: == 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.
Line 50: Line 57:
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).
query(callipo,barilla)?		 == Example(s) ==
Line 54: Line 59:
== Output format == 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).}}}
Line 56: Line 63:
If the answer to the input query is positive (i.e., for query(c1,c2), c1 and c2 jointly belong to a minimal strategic set), the output must contain a number of ground atoms of the form strategic(i) (where "strategic(i)" stands for "company i is strategic") witnessing that c1 and c2 belong to a strategic set. Output: {{{strategic_pair(c1,c2)}}}
Line 58: Line 65:
== Example ==
== 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.

  * Encoding updated on 01/02/2011;
  * Training Instances updated on 31/01/2011;

== 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.
Line 64: Line 84:
   * Affiliation:    * Affiliation: University of Genova

Strategic Companies

Contents

  1. Strategic Companies
    1. Problem Description
    2. Predicates
    3. Input format
    4. Output format
    5. Example(s)
    6. Notes and updates
    7. Problem Peculiarities
    8. Author(s)

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

  • C = c1, ..., cm

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:

  • Companies in C' produce all goods in G;

  • If Oi is a subset of C', the associated company ci must belong to C'(for each i=1,...,m).

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: produced_by/5, controlled_by/5, strategic_pair/2

  • Output: strategic/1

Input format

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

  • - A set of facts of the form produced_by(p,c1,c2,c3,c4), where produced_by(p,c1,c2,c3,c4) means that product P is produced by companies c1, c2, c3 and c4;

    - A set of facts of the form controlled_by(c,c1,c2,c3,c4), where controlled_by(c,c1,c2,c3,c4) means that company c is jointly controlled by c1, c2, c3 and c4;

    - A ground fact of the form strategic_pair(c1,c2), specifying the query goal: is there a strategic set containing both c1 and c2?

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.

  • Encoding updated on 01/02/2011;
  • Training Instances updated on 31/01/2011;

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)

  • Author: Mario Alviano
    • Affiliation: University of Calabria, Italy
  • Author: Marco Maratea
    • Affiliation: University of Genova
  • Author: Francesco Ricca
    • Affiliation: University of Calabria, Italy

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