#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. PLEASE UPDATE Changelog when changing }}} == Problem List - Domains included in BOTH 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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/06-Permutation-Pattern-Matching.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/01-Permutation-Pattern-Matching/encoding.asp|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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/04-Valves-Location-Problem.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/02-Valves-Location-Problem/encoding.asp|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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/08-Connected-Maximum-density-Still-Life.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/04-Connected-Maximum-density-Still-Life/encoding.asp|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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/09-Graceful-Graphs.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/05-Graceful-Graphs/encoding.asp|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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/12-Bottle-filling-problem.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/06-Bottle-filling-problem/encoding.asp|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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/26-Nomystery.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/07-Nomystery/encoding.asp|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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/27-Sokoban.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/08-Sokoban/encoding.asp|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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/14-Ricochet-Robot.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/09-Ricochet-Robot/encoding.asp|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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/29-Crossing-Minimization.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/10-Crossing-Minimization/encoding.asp|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|get]] || N.A. ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/11-Reachability/encoding.asp|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|get]] || N.A. ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/12-Strategic-Companies/encoding.asp|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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/22-Solitaire.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/13-Solitaire/encoding.asp|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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/25-Weighted-Sequence-Problem.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/14-Weighted-Sequence-Problem/encoding.asp|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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/33-StableMarriage.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/15-StableMarriage/encoding.asp|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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/24-Incremental-Scheduling.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/16-Incremental-Scheduling/encoding.asp|Incremental Scheduling]] || == Problem List - Domains included in the 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/links/samples/qualitative_temporal_spatial_reasoning.zip|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/05-Qualitative-spatial-and-temporal-reasoning.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/17-Qualitative-spatial-and-temporal-reasoning/encoding.asp|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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/02-Chemical-Classification.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/18-Chemical-Classification/encoding.asp|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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/03-Abstract-Dialectical-Frameworks-Well-founded-Model.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/19-Abstract-Dialectical-Frameworks-Well-founded-Model/encoding.asp|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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/28-Visit-all.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/20-Visit-all/encoding.asp|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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/21-Complex-Optimization-of-Answer-Sets.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/21-Complex-Optimization-of-Answer-Sets/encoding.asp|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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/30-Knight-Tour-with-holes.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/22-Knight-Tour-with-holes/encoding.asp|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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/20-Maximal-Clique.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/23-Maximal-Clique/encoding.asp|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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/17-Labyrinth.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/24-Labyrinth/encoding.asp|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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/23-Minimal-Diagnosis.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/25-Minimal-Diagnosis/encoding.asp|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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/31-Hanoi-Tower.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/26-Hanoi-Tower/encoding.asp|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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/19-GraphColouring.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aspcore-2/27-GraphColouring/encoding.asp|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. == Instance set == * The .zip file containing the sha256sums of all the instance family from which instances will be selected randomly is available [[https://www.mat.unical.it/aspcomp2013/files/hashesASPCOMP2013.zip]]. The sha256sum of the file itself is [[https://www.mat.unical.it/aspcomp2013/files/hashesASPCOMP2013.txt|this]]. Note, the archive is password protected, credentials to be disclosed after the competition. * How we will select instances is specified [[http://www.mat.unical.it/aspcomp2013/files/scoringdetails2013.pdf|here]]. == Changelog == * Mar 19th, 2013: * Update definition of Incremental Scheduling by means of some clarifications. * Mar 16th, 2013: * Included check for multiple parallel moves in Nomystery checker; * The Visitall checker has now static binaries inside; * Removed the checkers for Reachability and Strategic Companies: query problems have a special treatment which makes checkers useless for participants; * Fixed the Labyrinth checker. * Mar 15th, 2013: * A number of fixes in Sokoban aspcore-2 encoding and in the corresponding checker. * Mar 14th, 2013: * Fixed directory in checker scripts of Graceful Graphs and Ricochet Robots. * Fixed encoding and checker for Knight Tour with Holes. * Mar 3rd, 2013: * Fix example in Solitaire domain description page. * Mar 2nd, 2013: * Fix in the syntax of weak contraints for all the ASPCore-2 encodings of optimization problems (Abstract Dialectical Frameworks, Crossing Minimization, Maximal Clique, Connected Maximum-Density Still Life, Valves Location) * Mar 1st, 2013: * Fix semantics for {{{pushtogoal}}} and {{{pushtonongoal}}} in the Sokoban domain. * Add sample instances for Qualitative Spatial Reasoning domain. * Fix encoding for Graceful Graphs domain. * Fix encoding for Connected Maximum-density Still Life domain. * Feb. 25th, 2013: * Updated Valves Location Problem and Abstract Dialectical Frameworks Well-founded Model Problem checkers to additionally output the costs of the provided solution. * 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.