#acl EditorsGroup:read,write All:read = Official Problem Suite = <> {{{#!wiki comment NOTE: URLs to encodings and sample instances NOT to be changed. For fixing encodings change their SVN image at SVNASPCOMP:/benchmarks/encodings and check them in. The website image will align within minutes. }}} == 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 ||[[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]] || == 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 || ||[[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 Optimization of Answer Sets ||Martin Gebser, Roland Kaminski, Torsten Schaub ||Search || Beyond NP ||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 ||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]] ||[[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]] || == 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. '''N'''ew 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 [[BenchmarkProblems|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 [[https://www.mat.unical.it/aspcomp2013/ProblemIOSpecification#checker|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. 22nd, 2013: * Updated Knight Tour with Holes description * 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.