Submitted Benchmarks
Submission of benchmark problems is now closed. We thank the submitters for the received benchmarks.
Find the call for benchmark problems here, and the requirements on instances and on test programs here.
We have further split up the decision problems in three categories with very different characteristics:
- Polynomially solvable problems (P)
- NP-problems, not known to be polynomially solvable
- NP^NP problems: this class contains only the strategic company problem.
Different rankings will be made based on this distinction.
| Benchmark Class |
Type |
Submitted by |
|---|
| HydraulicPlanning |
Decision,P |
Michael Gelfond, Ricardo Morales and Yuanlin Zhang.
|
| HydraulicLeaking |
Decision,P |
Michael Gelfond, Ricardo Morales and Yuanlin Zhang.
|
| CompanyControls |
Decision,P |
Mario Alviano
|
| GrammarBasedInformationExtraction |
Decision,P |
Marco Manna
|
| Reachability |
Decision,P |
Giorgio Terracina
|
| |
Decision,NP |
Gayathri Namasivayam and Miroslaw Truszczynski |
| Sokoban |
Decision,NP |
Wolfgang Faber |
| 15Puzzle |
Decision,NP |
Lengning Liu, Miroslaw Truszczynski and Martin Gebser
|
| HamiltonianPath |
Decision,NP |
Lengning Liu, Miroslaw Truszczynski and Martin Gebser
|
| SchurNumbers |
Decision,NP |
Lengning Liu, Miroslaw Truszczynski and Martin Gebser
|
| TravellingSalesperson |
Decision,NP |
Lengning Liu, Miroslaw Truszczynski and Martin Gebser
|
| WeightBoundedDominatingSet |
Decision,NP |
Lengning Liu, Miroslaw Truszczynski and Martin Gebser
|
| Labyrinth |
Decision,NP |
Martin Gebser
|
| GeneralizedSlitherlink |
Decision,NP |
Wolfgang Faber
|
| HierarchicalClustering |
Decision,NP |
Gayathri Namasivayam and Miroslaw Truszczynski
|
| ConnectedDominatingSet |
Decision,NP |
Gayathri Namasivayam and Miroslaw Truszczynski
|
| GraphPartitioning |
Decision,NP |
Gayathri Namasivayam and Miroslaw Truszczynski
|
| Hanoi |
Decision,NP |
Gayathri Namasivayam, Miroslaw Truszczynski and Giorgio Terracina
|
| Fastfood |
Decision,NP |
Wolfgang Faber
|
| WireRouting |
Decision,NP |
Gayathri Namasivayam and Miroslaw Truszczynski
|
| Sudoku |
Decision,NP |
Neng-Fa Zhou
|
| DisjunctiveScheduling |
Decision,NP |
Neng-Fa Zhou
|
| KnightTour |
Decision,NP |
Neng-Fa Zhou
|
| ChannelRouting |
Decision,NP |
Neng-Fa Zhou
|
| EdgeMatching |
Decision,NP |
Martin Brain
|
| GraphColouring |
Decision,NP |
Martin Brain
|
| MazeGeneration |
Decision,NP |
Martin Brain
|
| Solitaire |
Decision,NP |
Martin Brain
|
| StrategicCompanies |
Decision,NP^NP |
Mario Alviano, Marco Maratea and Francesco Ricca
|
| GolombRuler |
Optimization |
Martin Brain
|
| MaximalClique |
Optimization |
Johan Wittocx
|
| 15PuzzleOpt |
Optimization |
Lengning Liu, Miroslaw Truszczynski and Martin Gebser
|
| TravellingSalespersonOptimize |
Optimization |
Lengning Liu, Miroslaw Truszczynski and Martin Gebser
|
| WeightBoundedDominatingSetOptimize |
Optimization |
Lengning Liu, Miroslaw Truszczynski and Martin Gebser
|
| LabyrinthOptimize |
Optimization |
Martin Gebser
|
| SokobanOptimize |
Optimization |
Wolfgang Faber
|
| FastfoodOptimize |
Optimization |
Wolfgang Faber
|
| CompanyControlsOptimize |
Optimization |
Mario Alviano
|
|