Official Problem Suite
Problem List - Model & Solve and System Track
Nr |
Name |
Author(s) |
Type |
Complexity |
Domain |
Problem Description |
Sample Instances |
Checker |
N01 |
Permutation Pattern Matching |
Martin Lackner, Andreas Pfandler |
Search |
NP |
Combinatorial |
|
|
|
N02 |
Valves Location Problem |
Andrea Peano |
Optimization |
Beyond NP |
Combinatorial |
|||
N03 |
Rotating Workforce Scheduling |
Francesco Calimeri, Thomas Krennwallner, Nysret Musliu |
Search |
|
Scheduling |
|
|
|
N04 |
Connected Maximum-density Still Life |
Christian Drescher |
Optimization |
Beyond NP |
AI |
|||
N05 |
Graceful Graphs |
Christian Drescher |
Search |
NP |
Graph |
|||
N06 |
Bottle Filling Problem |
Wolfgang Faber |
Search |
|
Combinatorial |
|||
N07 |
Nomystery |
Giovambattista Ianni, Carlos Linares López*, Hootan Nakhost* |
Search |
|
Planning |
|
||
N08 |
Sokoban |
Giovambattista Ianni, Wolfgang Faber*, Carlos Linares López* |
Search |
|
Planning |
|||
N09 |
Ricochet Robots |
Julius Höfler, Martin Gebser, Philipp Obermeier, Roland Kaminski, Torsten Schaub |
Search |
|
Puzzle |
|
||
O10 |
Crossing Minimization |
Carmine Dodaro, Graeme Gange*, Peter Stuckey* |
Optimization |
Beyond NP |
Graph |
|
|
|
O11 |
Reachability |
Carmine Dodaro, Giorgio Terracina* |
Query |
P |
Graph |
|
|
|
O12 |
Strategic Companies |
Mario Alviano, Marco Maratea*, Francesco Ricca* |
Query |
Beyond NP |
AI |
|||
O13 |
Solitaire |
Marcello Balduccini, Yuliya Lierler* |
Search |
NP |
Puzzle |
|
||
O14 |
Weighted-Sequence Problem |
Marcello Balduccini, Yuliya Lierlier, Shaden Smith |
Search |
NP |
Database |
|||
O15 |
Stable Marriage |
Mario Alviano, Carmine Dodaro, Francesco Ricca |
Search |
P |
Graph |
|
||
O16 |
Incremental Scheduling |
Marcello Balduccini, Yuliya Lierler* |
Search |
NP |
Scheduling |
|
Problem List - System Track only
Nr |
Name |
Author(s) |
Type |
Complexity |
Domain |
ASP-Core-2 Encoding |
Problem Description |
Sample Instances |
Checker |
N17 |
Qualitative Spatial Reasoning |
Jason Jingshi Li |
Search |
NP |
Formal logic |
|
|
||
N18 |
Chemical Classification |
Despoina Magka |
Search |
P |
Natural Sciences |
|
|||
N19 |
Abstract Dialectical Frameworks Well-founded Model |
Stefan Ellmauthaler, Johannes Wallner |
Optimization |
|
Formal logic |
|
|||
N20 |
Visit-all |
Giovambattista Ianni,Nir Lipovetzky*, Carlos Linares López* |
Search |
|
Planning |
|
|
||
N21 |
Complex Optimization of Answer Sets |
Martin Gebser, Roland Kaminski, Torsten Schaub |
Search |
|
Synthetic |
|
|||
O22 |
Knight Tour with Holes |
Francesco Calimeri, Neng-Fa Zhou* |
Search |
NP |
Puzzle |
|
|||
O23 |
Maximal Clique Problem |
Guenther Charwat, Martin Kronegger, Johan Wittocx* |
Optimization |
Beyond NP |
Graph |
|
|||
O24 |
Labyrinth |
Carmine Dodaro, Giovambattista Ianni, Martin Gebser* |
Search |
NP |
Puzzle |
|
|||
O25 |
Minimal Diagnosis |
Marcello Balduccini, Martin Gebser* |
Search |
Beyond NP |
Diagnosis |
|
|||
O26 |
Hanoi Tower |
Gayathri Namasivayam, Miroslaw Truszczynski, Shaden Smith, Alex Westlund |
Search |
NP |
AI |
|
|||
O27 |
Graph Colouring |
Johannes Wallner, Marcello Balduccini*, Yuliya Lierler* |
Search |
NP |
Graph |
|
Legend
Columns in the table below are to be read as following:
Nr. ID of the benchmark. The prefixes N resp. O denote a newly added resp. a 2011 benchmark.
Author(s). Names of authors. A * denotes that they authored the respective package in previous years.
Type. One of Search, Optimization, Query. See the problem classification page.
Final Problem Description. Problem specifications in their official form, with latest notes and updates.
Sample Instances. A link to sample instances of the given problem.