#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 }}} {{{#!wiki caution Please note that this is an old page. Due to some maintenance, some links might have been lost. For your convenience, please find the whole benchmark suite (i.e., encodings, samples and checkers) HERE: * [[https://www.mat.unical.it/aspcomp2013/files/links/aspcomp2013-encodings-samples-checkers.tar.gz|ASPCOMP 2013: encodings, samples, checkers]] (.tar.gz file, approx. 256MB) * [[https://www.mat.unical.it/ianni/aspcomp2013instances/|ASPCOMP 2013: instances]] (web page) - link is reported also in the [[#instanceset|Instance Set Section]] of this page We apologize for the inconvenience. }}} == 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/01-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/02-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/04-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/05-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 || NP ||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/06-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 || NP ||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/07-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 || NP ||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/08-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 || NP ||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/09-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/10-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/13-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/14-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/15-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/16-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''' ||'''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/17-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]] || N.A. ||[[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 || Beyond NP|| 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/19-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 || NP ||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/20-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/22-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/23-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/24-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/25-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/26-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/27-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|here]]. 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]]. * <> Full instance set: [[https://www.mat.unical.it/ianni/aspcomp2013instances/|here]] == Alternative Encodings == In the System Track, participants can propose '''strictly syntactical''' variants of official encodings: * Alternative encodings compatible with Gringo 3: [[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/aalto-gringo/alternate-aspcomp2013.tar.gz | download]] * Alternative encodings compatible with WASP: [[https://www.mat.unical.it/aspcomp2013/files/links/benchmarks/encodings/wasp-enc/alternate-aspcomp2013-wasp.tar.gz| download]] == What do checkers expect as their input? How do I check my solution compliance ? == * See [[https://www.mat.unical.it/aspcomp2013/ProblemIOSpecification#checker|here]] == Changelog == * Apr 11th, 2013 <> The numbers chosen as starting seed are 15-35-38-44-48, as of the [[https://www.national-lottery.co.uk/player/euromillions/results/prizeBreakdown.ftl?drawNumber=579&drawSequence=0|Euromillion Lottery]] of Tuesday April 9th 2013. * Mar 27th, 2013: * Elimination of redundant global variables and minor variable renamings to encodings of problem 02,04,07,08 and 20 * Mar 25th, 2013: * Published WASP alternative encodings (these are aspcore-2 with minor compatibility adjustments). * Minor uniformation between the 3 currently available encoding sets (aspcore-2, gringo 3, wasp). * Mar 24th, 2013: a shortening to the Valves Location encoding (in aspcore-2 and all alternatives) * Mar 23th, 2013: * Updated Valves Location checker * Mar 21st, 2013: * Fix some typos in description of Solitaire problem, and accordingly fix encoding. * Gringo 3 alternative encodings available * Mar 20th, 2013: * Update definition of Qualitative Spatial Reasoning. * Update checker for Qualitative Spatial Reasoning. * 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.