welcome: please sign in
location: Diff for "FinalProblemDescriptions/StrategicCompanies"
Differences between revisions 3 and 11 (spanning 8 versions)
⇤ ← Revision 3 as of 2012-11-05 21:43:38 →
Size: 4690
Editor: PatrikSchneider
Comment: Fix
← Revision 11 as of 2013-03-16 12:00:33 → ⇥
Size: 4674
Editor: GiovambattistaIanni
Comment:
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
#acl EditorsGroup:read,write,revert,admin MarioAlviano:read,write All:read
Line 3: Line 5:
<<TableOfContents>>
Line 7: Line 8:
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. In the Strategic Companies problem, a collection C = c,,1,,, ..., c,,m,, 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 9: Line 10:
In the Strategic Companies problem, a collection

  C = c,,1,,, ..., c,,m,,

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:

 * 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>>		  * 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). <<BR>>
Line 20: Line 15:
 1. each product is produced by at most four companies; and 
 1. each company is controlled by at most four companies. <<BR>>		  1. each product is produced by at most four companies; and
 2. each company is controlled by at most four companies. <<BR>>
Line 23: Line 18:
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.		 Under these restrictions the problem is still NP^NP-complete. <<BR>>
Line 28: Line 20:
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'. 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.

The goal of the problem is a follows: Given two distinct companies c,,i,,,c,,j,, in C, we ask for checking whether no strategic set C' containing both c,,i,, and c,,j,, does exist. Queries of this benchmark have thus to be answered cautiously.
Line 32: Line 27:
 * '''Input''': {{{produced_by/5, controlled_by/5, strategic_pair/2}}}  * '''Input''': {{{produced_by/5, controlled_by/5, strategic_pair/2, non_strategic_pair/2}}}
Line 34: Line 29:
 * '''Output''': {{{strategic/1}}}  * '''Output''': {{{yes}}} or {{{no}}} (meant as the propositional assertions {{{yes.}}} and {{{no.}}})
Line 40: Line 35:
 - 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 c,,1,,, c,,2,,, c,,3,, and c,,4,,;
Line 42: Line 37:
 - 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 c,,1,,, c,,2,,, c,,3,, and c,,4,,;
Line 44: Line 39:
 - A ground fact of the form {{{strategic_pair(c1,c2)}}}, specifying the query goal: is there a strategic set containing both c1 and c2?  - A ground query of the form {{{non_strategic_pair(c1,c2)?}}}, specifying the query goal, i.e., whether no strategic set containing both c,,1,, and c,,2,, does exist.
Line 48: Line 43:
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).		 produced_by(pasta,barilla,dececco,dececco,dececco).
produced_by(tonno,callipo,star,star,star).
controlled_by(barilla,star,star,star,star).
controlled_by(dececco,barilla,barilla,barilla,barilla).
non_strategic_pair(barilla,star)?
Line 55: Line 52:
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. The output must be {{{yes.}}} or {{{no.}}} intended as {{{0}}}-ary facts. See the specification for outputs of query problems, [[https://www.mat.unical.it/aspcomp2013/files/aspoutput.txt|here]].

For instance:
{{{
no.
}}}
Line 59: Line 63:
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).}}}		 Input:
{{{
produced_by(pasta,barilla,dececco,dececco,dececco).
produced_by(tonno,callipo,star,star,star).
controlled_by(barilla,star,star,star,star).
controlled_by(dececco,barilla,barilla,barilla,barilla).
non_strategic_pair(barilla, callipo)?
}}}
Line 63: Line 72:
Output: {{{strategic_pair(c1,c2).}}} Output:
{{{
yes.
}}}
Line 65: Line 77:
Additional sample instances: [[https://www.mat.unical.it/aspcomp2013/files/samples/strategic_companies-sample.zip|download]]
Line 74: Line 86:
== 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.

Strategic Companies

Problem Description

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. 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 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 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 whether no strategic set C' containing both ci and cj does exist. Queries of this benchmark have thus to be answered cautiously.

Predicates

  • Input: produced_by/5, controlled_by/5, strategic_pair/2, non_strategic_pair/2

  • Output: yes or no (meant as the propositional assertions yes. and no.)

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 query of the form non_strategic_pair(c1,c2)?, specifying the query goal, i.e., whether no strategic set containing both c1 and c2 does exist.

For instance: 

produced_by(pasta,barilla,dececco,dececco,dececco).
produced_by(tonno,callipo,star,star,star).
controlled_by(barilla,star,star,star,star).
controlled_by(dececco,barilla,barilla,barilla,barilla).
non_strategic_pair(barilla,star)?

Output format

The output must be yes. or no. intended as 0-ary facts. See the specification for outputs of query problems, here.

For instance: 

no.

Example(s)

Input: 

produced_by(pasta,barilla,dececco,dececco,dececco).
produced_by(tonno,callipo,star,star,star).
controlled_by(barilla,star,star,star,star).
controlled_by(dececco,barilla,barilla,barilla,barilla).
non_strategic_pair(barilla, callipo)?

Output: 

yes.

Additional sample instances: download

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
  • Original Authors: Marco Maratea, Francesco Ricca
    • Affiliation: University of Genova and University of Calabria, Italy

ASP Competition 2013: FinalProblemDescriptions/StrategicCompanies (last edited 2013-03-16 12:00:33 by GiovambattistaIanni)