|
Size: 3304
Comment:
|
← Revision 13 as of 2011-01-18 15:07:59 ⇥
Size: 6541
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| = UNDER CONSTRUCTION = | = Preliminary List of Selected Benchmark Problems = |
| Line 3: | Line 3: |
| = List of Selected Benchmark Problems = | <<BR>> |
| Line 5: | Line 5: |
| <<BR>> || # || '''Problem''' || '''Author(s)''' || '''Model & Solve track''' || '''System track''' || '''Language (sub)class''' || '''Type''' || '''Complexity''' || || || || || ''(yes/no)'' || ''(yes/no)'' || ''(ASP-Core/ASP-RfC/Open)'' || ''(Search/Optimization/Query)'' || ''(P/NP/Beyond NP)'' || ''(Preliminary) Problem description'' || Accepted and available on the Competition Platform || || 1 || Crossing minimization in layered graphs || Stuckey || YES || NO || Open || Optimization || ??? || || 2 || Reachability || Terracina || YES || YES || ASP-Core || Search || P || || 3 || Strategic Companies || Alviano || YES || YES || ASP-Core || Search || Beyond NP || || 4 || Company Controls || Alviano || YES || YES || ASP-RfC??? || Optimization || P || || 5 || Company Controls Optimize || Alviano || YES || NO || Open || Optimization || ??? || || 6 || Grammar-Based Information Extraction || Manna || YES || YES || ASP-Core || Search || P || || 7 || Generalized Slitherlink || Faber || YES || YES??? || ASP-RfC??? || Search || NP || || 8 || Fastfood Optimality Check || Faber || YES || YES??? || ASP-RfC??? || Search || NP || || 9 || Fastfood Optimization || Faber || YES || NO || Open || Optimization || ??? || || 10 || Sokoban Decision || Faber || YES || YES || ASP-Core || Search || NP || || 11 || Sokoban Optimization || Faber || YES || NO || Open || Optimization || ??? || || 12 || Knight Tour || Neng-Fa Zhou || YES || YES || ASP-Core || Search || NP || || 13 || Disjunctive Scheduling || Neng-Fa Zhou || YES || YES || ASP-Core || Search || NP || || 14 || Packing Problem || Neng-Fa Zhou || YES || YES || ASP-Core || Search || NP || || 16 || Maximal Clique || Wittocx || YES || NO || ASP-Core/ASP-RfC || Optimization || ??? || || 17 || Labyrinth || Gebser || YES || YES || ASP-Core || Search || NP || || 18 || Minimal Diagnosis || Gebser || YES || YES || ASP-Core || || Beyond NP || || 19 || Multi Context System Querying || Schueller || YES || YES || ASP-Core || Search || NP || || 20 || Numberlink || Neng-Fa Zhou, Tamura || YES || ??? || ASP-Core || || ??? || || 21a || Reverse Folding || Formisano, Dovier, Pontelli || YES || YES || ASP-Core || || || || 21b || Gas Diffusion || Formisano, Dovier, Pontelli || YES || YES??? || Open || || || || 21c || Tangram || Formisano, Dovier, Pontelli || YES || YES??? || Open || || || || 22 || Hanoi Tower || Truszczynski || YES || YES || ASP-Core || Search || NP || || 23 || Magic Square Sets || You || YES || YES??? || ASP-RfC || Search || NP??? || || 25 || Graph Colouring || Lierler, Balduccini || YES || YES || ASP-Core || Search || NP || || 26 || Solitaire || Lierler, Balduccini || YES || YES??? || ASP-Core || Search || NP || || 27 || Partner Units || Friedrich || YES || YES || ASP-RFC??? || Search || NP || || 27b || Partner Units - Polynomial || Friedrich || || YES || ASP-Core || Search || P || || 28 || Weight-Assignment Tree || Lierler || YES || NO || ASP-Core || Search || NP || || 30 || Hydraulic Leaking || Calimeri || NO || YES || ASP-Core || Search || P || || 31 || Hydraulic Planning || Calimeri || NO || YES || ASP-Core || Search || P || || 32 || Stable Marriage Problem || Ricca || || || ASP-Core || || P || |
||'''#'''||'''Problem Name'''||'''Author(s)'''||'''Model & Solve Competition'''||'''System Competition'''||'''Type'''||'''Class'''||'''Language for System Competition'''||'''Preliminary Problem Description'''|| ||1||Crossing minimization in layered graphs||Peter Stuckey and Graeme Gange||Yes||No||Optimization||Beyond NP/Opt||-||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/CrossingMinimizationInLayeredGraphs|view]]|| ||2||Reachability||Giorgio Terracina||Yes||Yes||Query||P||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/Reachability|view]]|| ||3||Strategic Companies||Mario Alviano, Marco Maratea and Francesco Ricca||Yes||Yes||Search||Beyond NP||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/StrategicCompanies|view]]|| ||4||Company Controls||Mario Alviano||Yes||Yes||Optimization||P||ASP-RfC||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/CompanyControls|view]]|| ||5||Company Controls Optimize||Mario Alviano||Yes||No||Optimization||Beyond NP/Opt||-||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/CompanyControlsOptimize|view]]|| ||6||Grammar-Based Information Extraction||Marco Manna||Yes||Yes||Search||P||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/Grammar-BasedInformationExtraction|view]]|| ||7||Generalized Slitherlink||Wolfgang Faber||Yes||No||Search||NP||-||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/GeneralizedSlitherlink|view]]|| ||8||Fastfood Optimality Check||Wolfgang Faber||Yes||No||Search||NP||-||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/FastfoodOptimalityCheck|view]]|| ||9||Fastfood Optimization||Wolfgang Faber||Yes||No||Optimization||Beyond NP/Opt||-||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/FastfoodOptimization|view]]|| ||10||Sokoban Decision||Wolfgang Faber||Yes||Yes||Search||NP||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/SokobanDecision|view]]|| ||11||Sokoban Optimization||Wolfgang Faber||Yes||No||Optimization||Beyond NP/Opt||-||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/SokobanOptimization|view]]|| ||12||Knight Tour||Neng-Fa Zhou||Yes||Yes||Search||NP||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/KnightTour|view]]|| ||13||Disjunctive Scheduling||Neng-Fa Zhou||Yes||Yes||Search||NP||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/DisjunctiveScheduling|view]]|| ||14||Packing Problem||Neng-Fa Zhou||Yes||Yes||Search||NP||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/PackingProblem|view]]|| ||15||Tomography Problem||Neng-Fa Zhou||Yes||Yes||Optimization||NP||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/TomographyProblem|view]]|| ||16||Maximal Clique||Johan Wittocx||Yes||No||Optimization||Beyond NP/Opt||-||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/MaximalClique|view]]|| ||17||Labyrinth||Martin Gebser||Yes||Yes||Search||NP||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/Labyrinth|view]]|| ||18||Minimal Diagnosis||Martin Gebser||Yes||Yes||Search||Beyond NP||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/MinimalDiagnosis|view]]|| ||19||Multi Context System Querying||Peter Schüller||No||Yes||Query||NP||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/MultiContextSystemQuerying|view]]|| ||20||Numberlink||Naoyuki Tamura and Neng-Fa Zhou||Yes||Yes||Search||NP||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/Numberlink|view]]|| ||21a||Reverse Folding||Andrea Formisano, Agostino Dovier and Enrico Pontelli||Yes||No||Search||NP||-||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/ReverseFolding|view]]|| ||21b||Gas Diffusion||Andrea Formisano, Agostino Dovier and Enrico Pontelli||Yes||Yes||Search||NP||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/GasDiffusion|view]]|| ||21c||Tangram||Andrea Formisano, Agostino Dovier and Enrico Pontelli||Yes||No||Search||NP||-||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/Tangram|view]]|| ||22||Hanoi Tower||Miroslaw Truszczynski||Yes||Yes||Search||NP||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/HanoiTower|view]]|| ||23||Magic Square Sets||Yisong Wang and Jia-Huai You||Yes||No||Search||NP||ASP-RfC ||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/MagicSquareSets|view]]|| ||24||Airport Pickup||A. Ricardo Morales||Yes||No||Search||NP||-||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/AirportPickup|view]]|| ||25||Graph Colouring||Yuliya Lierler and Marcello Balduccini||Yes||Yes||Search||NP||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/GraphColouring|view]]|| ||26||Solitaire||Yuliya Lierler and Marcello Balduccini||Yes||Yes||Search||NP||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/Solitaire|view]]|| ||27||Partner Units||Anna Ryabokon, Andreas Falkner and Gerhard Friedrich||Yes||No||Search||NP||-||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/PartnerUnits|view]]|| ||27b||Partner Units - Polynomial||Anna Ryabokon, Andreas Falkner and Gerhard Friedrich||Yes||Yes||Search||P||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/PartnerUnitsPolynomial|view]]|| ||28||Weight-Assignment Tree||Yuliya Lierler||Yes||Yes||Search||NP||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/WeightAssignmentTree|view]]|| ||30||Hydraulic Leaking||Francesco Calimeri and Maria Carmela Santoro||Yes||Yes||Search||P||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/HydraulicLeaking|view]]|| ||31||Hydraulic Planning||Francesco Calimeri and Maria Carmela Santoro||Yes||Yes||Search||P||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/HydraulicPlanning|view]]|| ||32||Stable Marriage problem||Francesco Ricca||Yes||Yes||Search||P||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/StableMarriageProblem|view]]|| ||33||Maze Generation||Martin Brain and Mario Alviano||Yes||Yes||Search||NP||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/MazeGeneration|view]]|| ||35||Incremental Scheduling||Marcello Balduccini and Yuliya Lierler||Yes||Yes||Search||NP||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/IncrementalScheduling|view]]|| |
Preliminary List of Selected Benchmark Problems
# |
Problem Name |
Author(s) |
Model & Solve Competition |
System Competition |
Type |
Class |
Language for System Competition |
Preliminary Problem Description |
1 |
Crossing minimization in layered graphs |
Peter Stuckey and Graeme Gange |
Yes |
No |
Optimization |
Beyond NP/Opt |
- |
|
2 |
Reachability |
Giorgio Terracina |
Yes |
Yes |
Query |
P |
ASP-Core |
|
3 |
Strategic Companies |
Mario Alviano, Marco Maratea and Francesco Ricca |
Yes |
Yes |
Search |
Beyond NP |
ASP-Core |
|
4 |
Company Controls |
Mario Alviano |
Yes |
Yes |
Optimization |
P |
ASP-RfC |
|
5 |
Company Controls Optimize |
Mario Alviano |
Yes |
No |
Optimization |
Beyond NP/Opt |
- |
|
6 |
Grammar-Based Information Extraction |
Marco Manna |
Yes |
Yes |
Search |
P |
ASP-Core |
|
7 |
Generalized Slitherlink |
Wolfgang Faber |
Yes |
No |
Search |
NP |
- |
|
8 |
Fastfood Optimality Check |
Wolfgang Faber |
Yes |
No |
Search |
NP |
- |
|
9 |
Fastfood Optimization |
Wolfgang Faber |
Yes |
No |
Optimization |
Beyond NP/Opt |
- |
|
10 |
Sokoban Decision |
Wolfgang Faber |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
11 |
Sokoban Optimization |
Wolfgang Faber |
Yes |
No |
Optimization |
Beyond NP/Opt |
- |
|
12 |
Knight Tour |
Neng-Fa Zhou |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
13 |
Disjunctive Scheduling |
Neng-Fa Zhou |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
14 |
Packing Problem |
Neng-Fa Zhou |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
15 |
Tomography Problem |
Neng-Fa Zhou |
Yes |
Yes |
Optimization |
NP |
ASP-Core |
|
16 |
Maximal Clique |
Johan Wittocx |
Yes |
No |
Optimization |
Beyond NP/Opt |
- |
|
17 |
Labyrinth |
Martin Gebser |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
18 |
Minimal Diagnosis |
Martin Gebser |
Yes |
Yes |
Search |
Beyond NP |
ASP-Core |
|
19 |
Multi Context System Querying |
Peter Schüller |
No |
Yes |
Query |
NP |
ASP-Core |
|
20 |
Numberlink |
Naoyuki Tamura and Neng-Fa Zhou |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
21a |
Reverse Folding |
Andrea Formisano, Agostino Dovier and Enrico Pontelli |
Yes |
No |
Search |
NP |
- |
|
21b |
Gas Diffusion |
Andrea Formisano, Agostino Dovier and Enrico Pontelli |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
21c |
Tangram |
Andrea Formisano, Agostino Dovier and Enrico Pontelli |
Yes |
No |
Search |
NP |
- |
|
22 |
Hanoi Tower |
Miroslaw Truszczynski |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
23 |
Magic Square Sets |
Yisong Wang and Jia-Huai You |
Yes |
No |
Search |
NP |
ASP-RfC |
|
24 |
Airport Pickup |
A. Ricardo Morales |
Yes |
No |
Search |
NP |
- |
|
25 |
Graph Colouring |
Yuliya Lierler and Marcello Balduccini |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
26 |
Solitaire |
Yuliya Lierler and Marcello Balduccini |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
27 |
Partner Units |
Anna Ryabokon, Andreas Falkner and Gerhard Friedrich |
Yes |
No |
Search |
NP |
- |
|
27b |
Partner Units - Polynomial |
Anna Ryabokon, Andreas Falkner and Gerhard Friedrich |
Yes |
Yes |
Search |
P |
ASP-Core |
|
28 |
Weight-Assignment Tree |
Yuliya Lierler |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
30 |
Hydraulic Leaking |
Francesco Calimeri and Maria Carmela Santoro |
Yes |
Yes |
Search |
P |
ASP-Core |
|
31 |
Hydraulic Planning |
Francesco Calimeri and Maria Carmela Santoro |
Yes |
Yes |
Search |
P |
ASP-Core |
|
32 |
Stable Marriage problem |
Francesco Ricca |
Yes |
Yes |
Search |
P |
ASP-Core |
|
33 |
Maze Generation |
Martin Brain and Mario Alviano |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
35 |
Incremental Scheduling |
Marcello Balduccini and Yuliya Lierler |
Yes |
Yes |
Search |
NP |
ASP-Core |