welcome: please sign in
location: Diff for "OfficialProblemSuite"
Differences between revisions 58 and 59
Revision 58 as of 2013-02-19 23:46:28
Size: 14517
Comment: link sample instances to slinks pointing to an automatically up-to-date svn copy
Revision 59 as of 2013-02-20 00:21:51
Size: 15693
Comment: link encodings to slinks pointing to an automatically up-to-date svn copy
Deletions are marked like this. Additions are marked like this.
Line 8: Line 8:
||N01 ||Permutation Pattern Matching ||Martin Lackner, Andreas Pfandler ||Search ||NP ||Combinatorial ||[[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/PermutationPatternMatching|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/permutation_pattern_matching-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/permutation_pattern_matching-checker.zip|download]] ||[[attachment:Permutation-Pattern-Matching-ENCODING.txt|Permutation Pattern Matching]] ||
||N02 ||Valves Location Problem ||Andrea Peano ||Optimization ||Beyond NP ||Combinatorial ||[[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/ValvesLocation|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/valves_location_problem-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/valves_location_problem-checker.zip|download]] ||[[attachment:Valves-Location-Problem-ENCODING.txt|Valves Location Problem]] ||
||N04 ||Connected Maximum-density Still Life ||Christian Drescher ||Optimization ||Beyond NP ||AI ||[[https://www.mat.unical.it/aspcomp2013/ConnectedMaximumDensityStillLife|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/still_life-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/still_life-checker.zip|download]] ||[[attachment:Connected-Maximum-density-Still-Life-ENCODING.txt|Connected Maximum-density Still Life]] ||
||N05 ||Graceful Graphs ||Christian Drescher ||Search ||NP ||Graph ||[[https://www.mat.unical.it/aspcomp2013/GracefulGraphs|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/graceful_graphs-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/graceful_graphs-checker.zip|download]] ||[[attachment:Graceful-Graphs-ENCODING.txt|Graceful Graphs]] ||
||N06 ||Bottle Filling Problem ||Wolfgang Faber ||Search || ||Combinatorial ||[[https://www.mat.unical.it/aspcomp2013/BottleFillingProblem|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/bottle_filling-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/bottle_filling-checker.zip|download]] ||[[attachment:Bottle-Filling-Problem-ENCODING.txt|Bottle Filling Problem]] ||
||N07 ||Nomystery ||Giovambattista Ianni, Carlos Linares López*, Hootan Nakhost* ||Search || ||Planning ||[[https://www.mat.unical.it/aspcomp2013/Nomystery|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/nomystery-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/nomystery-checker.zip|download]] ||[[attachment:Nomystery-ENCODING.txt|Nomystery]] ||
||N08 ||Sokoban ||Giovambattista Ianni, Wolfgang Faber*, Carlos Linares López* ||Search || ||Planning ||[[https://www.mat.unical.it/aspcomp2013/Sokoban|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/sokoban-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/sokoban-checker.zip|download]] ||[[attachment:Sokoban-ENCODING.txt|Sokoban]] ||
||N09 ||Ricochet Robots ||Julius Höfler, Martin Gebser, Philipp Obermeier, Roland Kaminski, Torsten Schaub ||Search || ||Puzzle ||[[https://www.mat.unical.it/aspcomp2013/RicochetRobot|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/ricochet_robot-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/ricochet_robot-checker.zip|download]] ||[[attachment:Ricochet-Robots-ENCODING.txt|Ricochet Robot]] ||
||O10 ||Crossing Minimization ||Carmine Dodaro, Graeme Gange*, Peter Stuckey* ||Optimization ||Beyond NP ||Graph ||[[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/CrossingMinimization|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/crossing_minimization-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/crossing_minimization-checker.zip|download]] ||[[attachment:Crossing-Minimization-ENCODING.txt|Crossing Minimization]] ||
||N11'''*''' ||Reachability ||Carmine Dodaro, Giorgio Terracina* ||Query ||P ||Graph ||[[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/Reachability|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/reachability-sample.zip|download]] || ||[[attachment:Reachability-ENCODING.txt|Reachability]] ||
||N12'''*''' ||Strategic Companies ||Mario Alviano, Marco Maratea*, Francesco Ricca* ||Query ||Beyond NP ||AI ||[[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/StrategicCompanies|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/strategic_companies-sample.zip|download]] || ||[[attachment:Strategic-Companies-ENCODING.txt|Strategic Companies]] ||
||O13 ||Solitaire ||Marcello Balduccini, Yuliya Lierler* ||Search ||NP ||Puzzle ||[[https://www.mat.unical.it/aspcomp2013/Solitaire|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/solitaire-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/solitaire-checker.zip|download]] ||[[attachment:Solitaire-ENCODING.txt|Solitaire]] ||
||O14 ||Weighted-Sequence Problem ||Marcello Balduccini, Yuliya Lierlier, Shaden Smith ||Search ||NP ||Database ||[[https://www.mat.unical.it/aspcomp2013/WeightedSequenceProblem|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/weighted_sequence-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/weighted_sequence-checker.zip|download]] ||[[attachment:Weighted-Sequence-Problem-ENCODING.txt|Weighted-Sequence Problem]] ||
||O15 ||Stable Marriage ||Mario Alviano, Carmine Dodaro, Francesco Ricca ||Search ||P ||Graph ||[[https://www.mat.unical.it/aspcomp2013/StableMarriage|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/stablemarriage-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/stable_marriage-checker.zip|download]] ||[[attachment:Stable-Marriage-ENCODING.txt|Stable Marriage]] ||
||O16 ||Incremental Scheduling ||Marcello Balduccini, Yuliya Lierler* ||Search ||NP ||Scheduling ||[[https://www.mat.unical.it/aspcomp2013/IncrementalScheduling|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/incremental_scheduling-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/incremental-scheduling-checker.zip|download]] ||[[attachment:Incremental-Scheduling-ENCODING.txt|Incremental Scheduling]] ||
||N01 ||Permutation Pattern Matching ||Martin Lackner, Andreas Pfandler ||Search ||NP ||Combinatorial ||[[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/PermutationPatternMatching|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/permutation_pattern_matching-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/permutation_pattern_matching-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/permutation_pattern_matching-encoding.txt|Permutation Pattern Matching]] ||
||N02 ||Valves Location Problem ||Andrea Peano ||Optimization ||Beyond NP ||Combinatorial ||[[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/ValvesLocation|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/valves_location_problem-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/valves_location_problem-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/valves_location_problem-encoding.txt|Valves Location Problem]] ||
||N04 ||Connected Maximum-density Still Life ||Christian Drescher ||Optimization ||Beyond NP ||AI ||[[https://www.mat.unical.it/aspcomp2013/ConnectedMaximumDensityStillLife|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/still_life-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/still_life-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/still_life-encoding.txt|Connected Maximum-density Still Life]] ||
||N05 ||Graceful Graphs ||Christian Drescher ||Search ||NP ||Graph ||[[https://www.mat.unical.it/aspcomp2013/GracefulGraphs|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/graceful_graphs-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/graceful_graphs-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/graceful_graphs-encoding.txt|Graceful Graphs]] ||
||N06 ||Bottle Filling Problem ||Wolfgang Faber ||Search || ||Combinatorial ||[[https://www.mat.unical.it/aspcomp2013/BottleFillingProblem|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/bottle_filling-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/bottle_filling-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/bottle_filling-encoding.txt|Bottle Filling Problem]] ||
||N07 ||Nomystery ||Giovambattista Ianni, Carlos Linares López*, Hootan Nakhost* ||Search || ||Planning ||[[https://www.mat.unical.it/aspcomp2013/Nomystery|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/nomystery-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/nomystery-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/nomystery-encoding.txt|Nomystery]] ||
||N08 ||Sokoban ||Giovambattista Ianni, Wolfgang Faber*, Carlos Linares López* ||Search || ||Planning ||[[https://www.mat.unical.it/aspcomp2013/Sokoban|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/sokoban-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/sokoban-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/sokoban-encoding.txt|Sokoban]] ||
||N09 ||Ricochet Robots ||Julius Höfler, Martin Gebser, Philipp Obermeier, Roland Kaminski, Torsten Schaub ||Search || ||Puzzle ||[[https://www.mat.unical.it/aspcomp2013/RicochetRobot|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/ricochet_robot-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/ricochet_robot-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/ricochet_robot-encoding.txt|Ricochet Robot]] ||
||O10 ||Crossing Minimization ||Carmine Dodaro, Graeme Gange*, Peter Stuckey* ||Optimization ||Beyond NP ||Graph ||[[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/CrossingMinimization|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/crossing_minimization-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/crossing_minimization-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/crossing_minimization-encoding.txt|Crossing Minimization]] ||
||N11'''*''' ||Reachability ||Carmine Dodaro, Giorgio Terracina* ||Query ||P ||Graph ||[[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/Reachability|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/reachability-sample.zip|download]] || ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/reachability-encoding.txt|Reachability]] ||
||N12'''*''' ||Strategic Companies ||Mario Alviano, Marco Maratea*, Francesco Ricca* ||Query ||Beyond NP ||AI ||[[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/StrategicCompanies|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/strategic_companies-sample.zip|download]] || ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/strategic_companies-encoding.txt|Strategic Companies]] ||
||O13 ||Solitaire ||Marcello Balduccini, Yuliya Lierler* ||Search ||NP ||Puzzle ||[[https://www.mat.unical.it/aspcomp2013/Solitaire|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/solitaire-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/solitaire-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/solitaire-encoding.txt|Solitaire]] ||
||O14 ||Weighted-Sequence Problem ||Marcello Balduccini, Yuliya Lierlier, Shaden Smith ||Search ||NP ||Database ||[[https://www.mat.unical.it/aspcomp2013/WeightedSequenceProblem|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/weighted_sequence-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/weighted_sequence-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/weighted_sequence-encoding.txt|Weighted-Sequence Problem]] ||
||O15 ||Stable Marriage ||Mario Alviano, Carmine Dodaro, Francesco Ricca ||Search ||P ||Graph ||[[https://www.mat.unical.it/aspcomp2013/StableMarriage|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/stablemarriage-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/stable_marriage-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/stablemarriage-encoding.txt|Stable Marriage]] ||
||O16 ||Incremental Scheduling ||Marcello Balduccini, Yuliya Lierler* ||Search ||NP ||Scheduling ||[[https://www.mat.unical.it/aspcomp2013/IncrementalScheduling|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/incremental_scheduling-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/incremental-scheduling-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/incremental_scheduling-encoding.txt|Incremental Scheduling]] ||
Line 30: Line 30:
||N17 ||Qualitative Spatial Reasoning ||Jason Jingshi Li ||Search ||NP ||Formal logic || ||[[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/QualitativeSpatialTemporalReasoning|view]] || ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/qualitative_spatial_reasoning-checker.zip|download]] ||[[attachment:Qualitative-Spatial-Reasoning-ENCODING.txt|Qualitative Spatial Reasoning]] ||
||N18 ||Chemical Classification ||Despoina Magka ||Search ||P ||Natural Sciences || ||[[
https://www.mat.unical.it/aspcomp2013/ChemicalClassification|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/chemical_classification-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/chemical_classification-checker.zip|download]] ||[[attachment:Chemical-Classification-ENCODING.txt|Chemical Classification]] '''(60+ MB)''' ||
||N19 ||Abstract Dialectical Frameworks Well-founded Model ||Stefan Ellmauthaler, Johannes Wallner ||Optimization || ||Formal logic || ||[[https://www.mat.unical.it/aspcomp2013/AbstractDialecticalFrameworks|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/abstract_dialectical_frameworks-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/abstract_dialectical_frameworks-checker.zip|download]] ||[[attachment:Abstract-Dialectical-Frameworks-Well-founded-Model-ENCODING.txt|Abstract Dialectical Frameworks Well-founded Model]] ||
||N20 ||Visit-all ||Giovambattista Ianni,Nir Lipovetzky*, Carlos Linares López* ||Search || ||Planning || ||[[
https://www.mat.unical.it/aspcomp2013/VisitAll|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/visitall-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/visit_all-checker.zip|download]] ||[[attachment:Visit-all-ENCODING.txt|Visit-all]] ||
||N21 ||Complex Optimization of Answer Sets ||Martin Gebser, Roland Kaminski, Torsten Schaub ||Search || ||Synthetic ||
||[[https://www.mat.unical.it/aspcomp2013/ComplexOptimizationAnswerSets|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/complex_optimization-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/complex_optimization-checker.zip|download]] ||[[attachment:Complex-Optimization-of-Answer-Sets-ENCODING.txt|Complex Optimization of Answer Sets]] ||
||N22'''*''' ||Knight Tour with Holes ||Francesco Calimeri, Neng-Fa Zhou* ||Search ||NP ||Puzzle || ||[[https://www.mat.unical.it/aspcomp2013/KnightTour|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/knight_tour-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/knight_tour-checker.zip|download]] ||[[attachment:Knight-Tour-with-Holes-ENCODING.txt|Knight Tour with Holes]] ||
||O23 ||Maximal Clique Problem ||Guenther Charwat, Martin Kronegger, Johan Wittocx* ||Optimization ||Beyond NP ||Graph || ||[[
https://www.mat.unical.it/aspcomp2013/MaximalClique|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/maximal_clique-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/maximal_clique-checker.zip|download]] ||[[attachment:Maximal-Clique-Problem-ENCODING.txt|Maximal Clique Problem]] ||
||O24 ||Labyrinth ||Carmine Dodaro, Giovambattista Ianni, Martin Gebser* ||Search ||NP ||Puzzle ||
||[[https://www.mat.unical.it/aspcomp2013/Labyrinth|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/labyrinth-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/labyrinth-checker.zip|download]] ||[[attachment:Labyrinth-ENCODING.txt|Labyrinth]] ||
||O25 ||Minimal Diagnosis ||Marcello Balduccini, Martin Gebser* ||Search ||Beyond NP ||Diagnosis ||
||[[https://www.mat.unical.it/aspcomp2013/MinimalDiagnosis|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/minimal_diagnosis-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/minimal_diagnosis-checker.zip|download]] ||[[attachment:Minimal-Diagnosis-ENCODING.txt|Minimal Diagnosis]] ||
||O26 ||Hanoi Tower ||Gayathri Namasivayam, Miroslaw Truszczynski, Shaden Smith, Alex Westlund ||Search ||NP ||AI || ||[[https://www.mat.unical.it/aspcomp2013/HanoiTower|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/hanoi_tower-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/hanoi_tower-checker.zip|download]] ||[[attachment:Hanoi-Tower-ENCODING.txt|Hanoi Tower]] ||
||O27 ||Graph Colouring ||Johannes Wallner, Marcello Balduccini*, Yuliya Lierler* ||Search ||NP ||Graph ||
||[[https://www.mat.unical.it/aspcomp2013/GraphColouring|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/graph_colouring-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/graph_colouring-checker.zip|download]] ||[[attachment:Graph-Colouring-ENCODING.txt|Graph Colouring]] ||
||N17 ||Qualitative Spatial Reasoning ||Jason Jingshi Li ||Search ||NP ||Formal logic || ||[[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/QualitativeSpatialTemporalReasoning|view]] || ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/qualitative_spatial_reasoning-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/qualitative_spatial_reasoning-encoding.txt|Qualitative Spatial Reasoning]] ||
||N18 ||
Chemical Classification ||Despoina Magka ||Search ||P ||Natural Sciences || ||[[https://www.mat.unical.it/aspcomp2013/ChemicalClassification|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/chemical_classification-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/chemical_classification-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/chemical_classification-encoding.txt|Chemical Classification]] '''(60+ MB)''' ||
||N19 ||Abstract Dialectical Frameworks Well-founded Model ||Stefan Ellmauthaler, Johannes Wallner ||Optimization || ||Formal logic || ||[[https://www.mat.unical.it/aspcomp2013/AbstractDialecticalFrameworks|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/abstract_dialectical_frameworks-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/abstract_dialectical_frameworks-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/abstract_dialectical_frameworks-encoding.txt|Abstract Dialectical Frameworks Well-founded Model]] ||
||N20 ||
Visit-all ||Giovambattista Ianni,Nir Lipovetzky*, Carlos Linares López* ||Search || ||Planning || ||[[https://www.mat.unical.it/aspcomp2013/VisitAll|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/visitall-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/visit_all-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/visitall-encoding.txt|Visit-all]] ||
||N21 ||Complex O
ptimization of Answer Sets ||Martin Gebser, Roland Kaminski, Torsten Schaub ||Search || ||Synthetic || ||[[https://www.mat.unical.it/aspcomp2013/ComplexOptimizationAnswerSets|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/complex_optimization-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/complex_optimization-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/complex_optimization-encoding.txt|Complex Optimization of Answer Sets]] ||
||N22'''*''' ||Knight Tour with Holes ||Francesco Calimeri, Neng-Fa Zhou* ||Search ||NP ||Puzzle || ||[[https://www.mat.unical.it/aspcomp2013/KnightTour|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/knight_tour-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/knight_tour-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/knight_tour-encoding.txt|Knight Tour with Holes]] ||
||O23 ||
Maximal Clique Problem ||Guenther Charwat, Martin Kronegger, Johan Wittocx* ||Optimization ||Beyond NP ||Graph || ||[[https://www.mat.unical.it/aspcomp2013/MaximalClique|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/maximal_clique-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/maximal_clique-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/maximal_clique-encoding.txt|Maximal Clique Problem]] ||
||O24 ||L
abyrinth ||Carmine Dodaro, Giovambattista Ianni, Martin Gebser* ||Search ||NP ||Puzzle || ||[[https://www.mat.unical.it/aspcomp2013/Labyrinth|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/labyrinth-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/labyrinth-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/labyrinth-encoding.txt|Labyrinth]] ||
||O25 ||Minimal Diagnosis ||Marcello Balduccini, Martin Gebser* ||Search ||Beyond NP ||Diagnosis || ||[[https://www.mat.unical.it/aspcomp2013/MinimalDiagnosis|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/minimal_diagnosis-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/minimal_diagnosis-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/minimal_diagnosis-encoding.txt|Minimal Diagnosis]] ||
||O26 ||Hanoi Tower ||
Gayathri Namasivayam, Miroslaw Truszczynski, Shaden Smith, Alex Westlund ||Search ||NP ||AI || ||[[https://www.mat.unical.it/aspcomp2013/HanoiTower|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/hanoi_tower-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/hanoi_tower-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/hanoi_tower-encoding.txt|Hanoi Tower]] ||
||O27 ||
Graph Colouring ||Johannes Wallner, Marcello Balduccini*, Yuliya Lierler* ||Search ||NP ||Graph || ||[[https://www.mat.unical.it/aspcomp2013/GraphColouring|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/samples/graph_colouring-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/graph_colouring-checker.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/graph_colouring-encoding.txt|Graph Colouring]] ||

Official Problem Suite

Problem List - Model & Solve and System Track


Nr

Name

Author(s)

Type

Complexity

Domain

Problem Description

Sample Instances

Checker

ASP-Core-2 encoding

N01

Permutation Pattern Matching

Martin Lackner, Andreas Pfandler

Search

NP

Combinatorial

view

download

download

Permutation Pattern Matching

N02

Valves Location Problem

Andrea Peano

Optimization

Beyond NP

Combinatorial

view

download

download

Valves Location Problem

N04

Connected Maximum-density Still Life

Christian Drescher

Optimization

Beyond NP

AI

view

download

download

Connected Maximum-density Still Life

N05

Graceful Graphs

Christian Drescher

Search

NP

Graph

view

download

download

Graceful Graphs

N06

Bottle Filling Problem

Wolfgang Faber

Search

Combinatorial

view

download

download

Bottle Filling Problem

N07

Nomystery

Giovambattista Ianni, Carlos Linares López*, Hootan Nakhost*

Search

Planning

view

download

download

Nomystery

N08

Sokoban

Giovambattista Ianni, Wolfgang Faber*, Carlos Linares López*

Search

Planning

view

download

download

Sokoban

N09

Ricochet Robots

Julius Höfler, Martin Gebser, Philipp Obermeier, Roland Kaminski, Torsten Schaub

Search

Puzzle

view

download

download

Ricochet Robot

O10

Crossing Minimization

Carmine Dodaro, Graeme Gange*, Peter Stuckey*

Optimization

Beyond NP

Graph

view

download

download

Crossing Minimization

N11*

Reachability

Carmine Dodaro, Giorgio Terracina*

Query

P

Graph

view

download

Reachability

N12*

Strategic Companies

Mario Alviano, Marco Maratea*, Francesco Ricca*

Query

Beyond NP

AI

view

download

Strategic Companies

O13

Solitaire

Marcello Balduccini, Yuliya Lierler*

Search

NP

Puzzle

view

download

download

Solitaire

O14

Weighted-Sequence Problem

Marcello Balduccini, Yuliya Lierlier, Shaden Smith

Search

NP

Database

view

download

download

Weighted-Sequence Problem

O15

Stable Marriage

Mario Alviano, Carmine Dodaro, Francesco Ricca

Search

P

Graph

view

download

download

Stable Marriage

O16

Incremental Scheduling

Marcello Balduccini, Yuliya Lierler*

Search

NP

Scheduling

view

download

download

Incremental Scheduling

Problem List - System Track only


Nr

Name

Author(s)

Type

Complexity

Domain

ASP-Core-2 Encoding

Problem Description

Sample Instances

Checker

ASP-Core-2 encoding

N17

Qualitative Spatial Reasoning

Jason Jingshi Li

Search

NP

Formal logic

view

download

Qualitative Spatial Reasoning

N18

Chemical Classification

Despoina Magka

Search

P

Natural Sciences

view

download

download

Chemical Classification (60+ MB)

N19

Abstract Dialectical Frameworks Well-founded Model

Stefan Ellmauthaler, Johannes Wallner

Optimization

Formal logic

view

download

download

Abstract Dialectical Frameworks Well-founded Model

N20

Visit-all

Giovambattista Ianni,Nir Lipovetzky*, Carlos Linares López*

Search

Planning

view

download

download

Visit-all

N21

Complex Optimization of Answer Sets

Martin Gebser, Roland Kaminski, Torsten Schaub

Search

Synthetic

view

download

download

Complex Optimization of Answer Sets

N22*

Knight Tour with Holes

Francesco Calimeri, Neng-Fa Zhou*

Search

NP

Puzzle

view

download

download

Knight Tour with Holes

O23

Maximal Clique Problem

Guenther Charwat, Martin Kronegger, Johan Wittocx*

Optimization

Beyond NP

Graph

view

download

download

Maximal Clique Problem

O24

Labyrinth

Carmine Dodaro, Giovambattista Ianni, Martin Gebser*

Search

NP

Puzzle

view

download

download

Labyrinth

O25

Minimal Diagnosis

Marcello Balduccini, Martin Gebser*

Search

Beyond NP

Diagnosis

view

download

download

Minimal Diagnosis

O26

Hanoi Tower

Gayathri Namasivayam, Miroslaw Truszczynski, Shaden Smith, Alex Westlund

Search

NP

AI

view

download

download

Hanoi Tower

O27

Graph Colouring

Johannes Wallner, Marcello Balduccini*, Yuliya Lierler*

Search

NP

Graph

view

download

download

Graph Colouring

Legenda

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. New problems with a * denote an old problem with changes in its specification.

  • 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.

  • Complexity. One of P, NP or Beyond-NP. To be read as the known complexity of the underlying decisional problem associated to the domain at hand. P: known to be solvable in polynomial time in the size of input. NP: known to be solvable

in non-deterministic polynomial time in the size of input. Beyond-NP: any other problem.

  • Domain. The domain type, e.g. graph, scheduling, planning etc.

  • Problem Description. Problem specifications in their official form, with latest notes and updates.

  • Sample Instances. A link to sample instances for the given problem.

  • Checker. A checker script for validating solutions. See here for the checker I/O specifications.

  • ASP-Core-2 encoding. The encoding which will be used in the System Track. Recall that the Model & Solve track has no fixed encoding, no fixed input language instead.

Changelog

  • Feb. 18th, 2013:
    • Updated Bottle Filling sample instances
  • Feb. 14th, 2013:
    • Updated ASP-Core-2 encoding for Valves Location

  • Feb. 13th, 2013:
    • Updated ASP-Core-2 encoding for Ricochet Robot

    • Removed Rotating workforce scheduling from the problem list.

  • Feb. 11th, 2013:
    • Marked with * codes of 2011's problems with slight different specification.

    • Updated Crossing Minimization and Maximal Clique Problem checkers to additionally output the costs of the provided solution.
    • A fix in the Valves Location encoding.

  • Feb. 10th, 2013:
    • Fix, update and clarify specs for Rotating Workforce Scheduling.
  • Feb. 9th, 2013:
    • Specified that trucks can carry more than one package in Nomystery.
    • Added sample instances for Reachability.
    • Update specs for Strategic Companies.
    • Fix specs for Reachability.

ASP Competition 2013: OfficialProblemSuite (last edited 2020-10-05 10:54:33 by FrancescoCalimeri)