|
Size: 23209
Comment:
|
Size: 6231
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 2: | Line 2: |
| = Problem Suite Selection Table = <<TableOfContents>> |
= Official Problem Suite = |
| Line 5: | Line 4: |
| == Legenda == | == Problem List - Model & Solve and System Track == <<BR>> ||<tablewidth="1024px" tableheight="421px" tablestyle="">'''Nr''' ||'''Name''' ||'''Author(s)''' || '''Type''' || '''Complexity''' ||'''Domain''' || '''Problem Description''' ||'''Sample Instances''' || || N01 ||Permutation Pattern Matching || Martin Lackner, Andreas Pfandler || Search || NP || Combinatorial ||[[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/PermutationPatternMatching|view]] || || || N02 ||Valves Location Problem || Andrea Peano || Optimization || Beyond NP || Combinatorial ||[[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/ValvesLocation|view]] || || || N03 ||Rotating Workforce Scheduling || Francesco Calimeri, Thomas Krennwallner, Nysret Musliu || Search || || Scheduling || || || || N04 ||Connected Maximum-density Still Life || Christian Drescher || Optimization || Beyond NP || AI || [[https://www.mat.unical.it/aspcomp2013/ConnectedMaximumDensityStillLife|view]] || || || N05 || Graceful Graphs || Christian Drescher || Search || || Graph || [[https://www.mat.unical.it/aspcomp2013/GracefulGraphs|view]] || || || N06 ||Bottle Filling Problem || Wolfgang Faber || Search || || Combinatorial || [[https://www.mat.unical.it/aspcomp2013/BottleFillingProblem|view]] || || || N07 ||Nomystery || Giovambattista Ianni, Carlos Linares López*, Hootan Nakhost* || Search || || Planning || [[https://www.mat.unical.it/aspcomp2013/Nomystery|view]] || || || N08 ||Sokoban || Giovambattista Ianni, Wolfgang Faber*, Carlos Linares López* || Search || || Planning || [[https://www.mat.unical.it/aspcomp2013/Sokoban|view]] || || || N09 || Ricochet Robots || Julius Höfler, Martin Gebser, Philipp Obermeier, Roland Kaminski, Torsten Schaub || Search || || Puzzle || [[https://www.mat.unical.it/aspcomp2013/RicochetRobot|view]] || || || O10 ||Crossing Minimization || Carmine Dodaro, Graeme Gange*, Peter Stuckey* || Optimization || Beyond NP || Graph || [[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/CrossingMinimization|view]] || || || O11 ||Reachability || Carmine Dodaro, Giorgio Terracina* || Query || P || Graph ||[[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/Reachability|view]] || || || O12 ||Strategic Companies || Mario Alviano, Marco Maratea*, Francesco Ricca* || Query || Beyond NP || AI || [[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/StrategicCompanies|view]] || || || O13 ||Solitaire || Marcello Balduccini, Yuliya Lierler* || Search || NP || Puzzle || [[https://www.mat.unical.it/aspcomp2013/Solitaire|view]] || || || O14 || Weighted-Sequence Problem || Marcello Balduccini, Yuliya Lierlier, Shaden Smith || Search || NP || Database || [[https://www.mat.unical.it/aspcomp2013/WeightedSequenceProblem|view]] || || || O15 ||Stable Marriage || Mario Alviano, Carmine Dodaro, Francesco Ricca || Search || P || Graph || [[https://www.mat.unical.it/aspcomp2013/StableMarriage|view]] || || || O16 ||Incremental Scheduling || Marcello Balduccini, Yuliya Lierler* || Search || NP || Scheduling || [[https://www.mat.unical.it/aspcomp2013/IncrementalScheduling|view]] || || == Problem List - System Track only == <<BR>> ||<tablewidth="1024px" tableheight="421px" tablestyle="">'''Nr''' ||'''Name''' ||'''Author(s)''' || '''Type''' || '''Complexity''' ||'''Domain''' || '''Problem Description''' ||'''Sample Instances''' || || N17 ||Qualitative Spatial Reasoning || Jason Jingshi Li || Search || NP || Formal logic || [[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/QualitativeSpatialTemporalReasoning|view]] || || || N18 ||Chemical Classification || Despoina Magka || Search || P || Natural Sciences || [[https://www.mat.unical.it/aspcomp2013/ChemicalClassification|view]] || || || N19 ||Abstract Dialectical Frameworks Well-founded Model || Stefan Ellmauthaler, Johannes Wallner || Optimization || || Formal logic || [[https://www.mat.unical.it/aspcomp2013/AbstractDialecticalFrameworks|view]] || || || N20 || Visit-all || Giovambattista Ianni,Nir Lipovetzky*, Carlos Linares López* || Search || || Planning || [[https://www.mat.unical.it/aspcomp2013/VisitAll|view]] || || || N21 ||Complex Optimization of Answer Sets || Martin Gebser, Roland Kaminski, Torsten Schaub || Search || || Synthetic || [[https://www.mat.unical.it/aspcomp2013/ComplexOptimizationAnswerSets|view]] || || || O22 ||Knight Tour with Holes || Francesco Calimeri, Neng-Fa Zhou* || Search || NP || Puzzle ||[[https://www.mat.unical.it/aspcomp2013/KnightTour|view]] || || || O23 ||Maximal Clique Problem || Guenther Charwat, Martin Kronegger, Johan Wittocx* || Optimization || Beyond NP || Graph || [[https://www.mat.unical.it/aspcomp2013/MaximalClique|view]] || || || O24 ||Labyrinth || Carmine Dodaro, Giovambattista Ianni, Martin Gebser* || Search || NP || Puzzle ||[[https://www.mat.unical.it/aspcomp2013/Labyrinth|view]] || || || O25 ||Minimal Diagnosis || Marcello Balduccini, Martin Gebser* || Search || Beyond NP || Diagnosis ||[[https://www.mat.unical.it/aspcomp2013/MinimalDiagnosis|view]] || || || O26 ||Hanoi Tower || Gayathri Namasivayam, Miroslaw Truszczynski, Shaden Smith, Alex Westlund || Search || NP || AI ||[[https://www.mat.unical.it/aspcomp2013/HanoiTower|view]] || || || O27 ||Graph Colouring || Johannes Wallner, Marcello Balduccini*, Yuliya Lierler* || Search || NP || Graph || [[https://www.mat.unical.it/aspcomp2013/GraphColouring|view]] || || == Legend == |
| Line 8: | Line 44: |
| * '''Present at 2nd Competition'''. The problem (or a variant thereof) was already present in the former edition of the competition. A ''^*^'' denotes there were introduced slight changes in the problem specification. You should consult the Section ''Notes & Updates'' in the corresponding problem sheet. * '''Model & Solve Competition'''. The problem has been selected as part of the Model & Solve Competition. * '''System Competition'''. The problem has been selected as part of the System Competition. |
* '''Nr'''. ID of the benchmark. The prefixes ''N'' resp. ''O'' denote a newly added resp. a 2011 benchmark. * '''Author(s)'''. Names of authors. A ''^*^'' denotes that they authored the respective package in previous years. |
| Line 12: | Line 47: |
| * '''Class'''. One of ''P'' (polynomial), ''NP'' (NP-Hard, not known to be more), ''Beyond NP'' (more than NP-Hard). See the problem [[BenchmarkProblems|classification]] page. * '''Language for System Competition'''. If the problem takes part in the System Competition, here is the smallest language fragment which the official encoding will be contained in (one of ''ASP-Core''/''ASP-RfC''). Recall that '''language restrictions do not apply''' when the same problem is run in the Model & Solve track. |
|
| Line 15: | Line 48: |
| * '''Training instances'''. A set of 5 training instances with heterogenous difficulty level, fairly enough similar to official instances. Participants '''will not''' be benchmarked on these instances in the official competition run. * '''ASP-Core/ASP-RfC encoding'''. If the problem takes part in the System Competition you will find here the official encoding which systems will be fed with. Take note that, in the spirit of the competition, this will be the one judged ''more natural'' and declarative, not the cleverest one. * '''Full Package'''. Original problem packages used in the competition. Each package contains: * A folder containing all instances. * Three text files, containing the full lists of the instances from the System Track, the Model&Solve Track, and the training set (that was available to the participants before the competition), respectively. * A folder containing the machinery exploited to generate such instances, if available ("generator") * The problem encoding, if available (see table below). * A folder containing the machinery exploited to check whether a witness solution for a given instance is correct or not ("checker"). == Full Problem List == <<BR>> ||<tablewidth="1272px" tableheight="2821px" tablestyle="">'''#''' ||'''Problem Name''' ||'''Author(s)''' ||Suitable for 2013 '''System Track''' (YES/NO and why, author of the note) ||Suitable '''for 2013 Model & Solve''' (YES/NO and why, author of the note) ||Actions to take (change encoding, change specs, changes instances, etc.) ||'''Present at the 2nd ASP Competition 2009''' ||'''Model & Solve Competition 2011''' ||'''System Competition 2011''' ||'''Type''' ||'''Class''' ||'''Language for System Competition''' ||'''Final Problem Description''' ||'''Training Instances''' ||'''ASP-Core/ASP-RfC encoding''' ||'''Full Package''' || ||1 ||Crossing minimization in layered graphs ||Peter Stuckey and Graeme Gange || || || ||No ||Yes ||No ||Optimization ||Beyond NP/Opt ||- ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/CrossingMinimization|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/CrossingMinimization/crossing_minimization-trainInstances.zip|download]] ||- ||[[http://www.mat.unical.it/aspcomp2011/files/CrossingMinimization/crossing_minimization-full_package.zip|download]] || ||2 ||Reachability ||Giorgio Terracina || || || ||Yes* ||Yes ||Yes ||Query ||P ||ASP-Core ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/Reachability|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/Reachability/reachability-trainInstances.zip|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/Reachability/reachability.enc.asp|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/Reachability/reachability-full_package.zip|download]] || ||3 ||Strategic Companies ||Mario Alviano, Marco Maratea and Francesco Ricca || || || ||Yes* ||Yes ||Yes ||Search ||Beyond NP ||ASP-Core ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/StrategicCompanies|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/StrategicCompanies/strategic_companies-trainInstances.zip|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/StrategicCompanies/strategic_companies.enc.asp|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/StrategicCompanies/strategic_companies-full_package.zip|download]] || ||4 ||Company Controls ||Mario Alviano || || || ||Yes* ||Yes ||No ||Search ||P ||- ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/CompanyControls|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/CompanyControls/company_controls-trainInstances.zip|download]] ||- ||[[http://www.mat.unical.it/aspcomp2011/files/CompanyControls/company_controls-full_package.zip|download]] || ||5 ||Company Controls Optimize ||Mario Alviano || || || ||Yes ||Yes ||No ||Optimization ||Beyond NP/Opt ||- ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/CompanyControlsOptimize|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/CompanyControlsOptimize/company_controls_optimize-trainInstances.zip|download]] ||- ||[[http://www.mat.unical.it/aspcomp2011/files/CompanyControlsOptimize/company_controls_optimize-full_package.zip|download]] || ||6 ||Grammar-Based Information Extraction ||Marco Manna || || || ||Yes ||Yes ||Yes ||Search ||P ||ASP-Core ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/Grammar-BasedInformationExtraction|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/Grammar-BasedInformationExtraction/grammar_based_information_extraction-trainInstances.zip|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/Grammar-BasedInformationExtraction/grammar_based_information_extraction.enc.asp|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/Grammar-BasedInformationExtraction/grammar_based_information_extraction-full_package.zip|download]] || ||7 ||Generalized Slitherlink ||Wolfgang Faber || || || ||Yes ||Yes ||No ||Search ||NP ||- ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/GeneralizedSlitherlink|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/GeneralizedSlitherlink/generalized_slitherlink-trainInstances.zip|download]] ||- ||[[http://www.mat.unical.it/aspcomp2011/files/GeneralizedSlitherlink/generalized_slitherlink-full_package.zip|download]] || ||8 ||Fastfood Optimality Check ||Wolfgang Faber || || || ||Yes ||Yes ||No ||Search ||NP ||ASP-RfC ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/FastfoodOptimalityCheck|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/FastfoodOptimalityCheck/fastfood_optimality_check-trainInstances.zip|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/FastfoodOptimalityCheck/fastfood_optimality_check.enc.asp|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/FastfoodOptimalityCheck/fastfood_optimality_check-full_package.zip|download]] || ||9 ||Fastfood Optimization ||Wolfgang Faber || || || ||Yes ||Yes ||No ||Optimization ||Beyond NP/Opt ||- ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/FastfoodOptimization|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/FastfoodOptimization/fastfoodoptimization-trainInstances.zip|download]] ||- ||[[http://www.mat.unical.it/aspcomp2011/files/FastfoodOptimization/fastfood_optimization-full_package.zip|download]] || ||10 ||Sokoban Decision ||Wolfgang Faber || || || ||Yes ||Yes ||Yes ||Search ||NP ||ASP-Core ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/SokobanDecision|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/SokobanDecision/sokoban_decision-trainInstances.zip|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/SokobanDecision/sokoban_decision.enc.asp|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/SokobanDecision/sokoban_decision-full_package.zip|download]] || ||11 ||Sokoban Optimization ||Wolfgang Faber || || || ||Yes ||Yes ||No ||Optimization ||Beyond NP/Opt ||- ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/SokobanOptimization|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/SokobanOptimization/sokoban_optimization-trainInstances.zip|download]] ||- ||[[http://www.mat.unical.it/aspcomp2011/files/SokobanOptimization/sokoban_optimization-full_package.zip|download]] || ||12 ||Knight Tour ||Neng-Fa Zhou, Francesco Calimeri and Maria Carmela Santoro || || || ||Yes ||Yes ||Yes ||Search ||NP ||ASP-Core ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/KnightTour|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/KnightTour/knight_tour-trainInstances.zip|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/KnightTour/knight_tour.enc.asp|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/KnightTour/knight_tour-full_package.zip|download]] || ||13 ||Disjunctive Scheduling ||Neng-Fa Zhou, Francesco Calimeri and Maria Carmela Santoro || || || ||Yes ||Yes ||Yes ||Search ||NP ||ASP-Core ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/DisjunctiveScheduling|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/DisjunctiveScheduling/disjunctive_scheduling-trainInstances.zip|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/DisjunctiveScheduling/disjunctive_scheduling.enc.asp|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/DisjunctiveScheduling/disjunctive_scheduling-full_package.zip|download]] || ||14 ||Packing Problem ||Neng-Fa Zhou || || || ||No ||Yes ||Yes ||Search ||NP ||ASP-Core ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/Packing|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/Packing/packing-trainInstances.zip|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/Packing/packing.enc.asp|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/Packing/packing_problem-full_package.zip|download]] || ||15 ||Tomography (Graph set covering) ||Neng-Fa Zhou || || || ||No ||Yes ||No ||Optimization ||NP/Opt ||ASP-Core ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/Tomography|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/Tomography/tomography-trainInstances.zip|download]] ||- ||[[http://www.mat.unical.it/aspcomp2011/files/Tomography/tomography-full_package.zip|download]] || ||16 ||Maximal Clique ||Johan Wittocx || || || ||Yes ||Yes ||No ||Optimization ||Beyond NP/Opt ||- ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/MaximalClique|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/MaximalClique/maximal_clique-trainInstances.zip|download]] ||- ||[[http://www.mat.unical.it/aspcomp2011/files/MaximalClique/maximal_clique-full_package.zip|download]] || ||17 ||Labyrinth ||Martin Gebser || || || ||Yes ||Yes ||Yes ||Search ||NP ||ASP-Core ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/Labyrinth|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/Labyrinth/labyrinth-trainInstances.zip|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/Labyrinth/labyrinth.enc.asp|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/Labyrinth/labyrinth-full_package.zip|download]] || ||18 ||Minimal Diagnosis ||Martin Gebser || || || ||No ||Yes ||Yes ||Search ||Beyond NP ||ASP-Core ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/MinimalDiagnosis|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/MinimalDiagnosis/minimal_diagnosis-trainInstances.zip|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/MinimalDiagnosis/minimal_diagnosis.enc.asp|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/MinimalDiagnosis/minimal_diagnosis-full_package.zip|download]] || ||19 ||Multi Context System Querying ||Peter Schüller || || || ||No ||No ||Yes ||Query ||NP ||ASP-Core ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/MultiContextSystemQuerying|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/MultiContextSystemQuerying/multi_context_system_querying-trainInstances.zip|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/MultiContextSystemQuerying/multi_context_system_querying.enc.asp|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/MultiContextSystemQuerying/multi_context_system_querying-full_package.zip|download]] || ||20 ||Numberlink ||Naoyuki Tamura and Neng-Fa Zhou || || || ||No ||Yes ||Yes ||Search ||NP ||ASP-Core ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/Numberlink|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/Numberlink/numberlink-trainInstances.zip|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/Numberlink/numberlink.enc.asp|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/Numberlink/numberlink-full_package.zip|download]] || ||21 ||Reverse Folding ||Andrea Formisano, Agostino Dovier and Enrico Pontelli || || || ||No ||Yes ||No ||Search ||NP ||- ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/ReverseFolding|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/ReverseFolding/reverse_folding-trainInstances.zip|download]] ||- ||[[http://www.mat.unical.it/aspcomp2011/files/ReverseFolding/reverse_folding-full_package.zip|download]] || ||22 ||Hanoi Tower ||Miroslaw Truszczynski, Shaden Smith and Alex Westlund || || || ||Yes* ||Yes ||Yes ||Search ||NP ||ASP-Core ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/HanoiTower|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/HanoiTower/hanoi_tower-trainInstances.zip|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/HanoiTower/hanoi_tower.enc.asp|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/HanoiTower/hanoi_tower-full_package.zip|download]] || ||23 ||Magic Square Sets ||Yisong Wang and Jia-Huai You || || || ||No ||Yes ||No ||Search ||NP ||ASP-RfC ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/MagicSquareSets|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/MagicSquareSets/magic_square_sets-trainInstances.zip|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/MagicSquareSets/magic_square.enc.asp|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/MagicSquareSets/magic_square_sets-full_package.zip|download]] || ||24 ||Airport Pickup ||A. Ricardo Morales || || || ||No ||Yes ||No ||Search ||NP ||- ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/AirportPickup|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/AirportPickup/airport_pickup-trainInstances.zip|download]] ||- ||[[http://www.mat.unical.it/aspcomp2011/files/AirportPickup/airport_pickup-full_package.zip|download]] || ||25 ||Graph Colouring ||Yuliya Lierler and Marcello Balduccini || || || ||Yes ||Yes ||Yes ||Search ||NP ||ASP-Core ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/GraphColouring|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/GraphColouring/graph_colouring-trainInstances.zip|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/GraphColouring/graph_colouring.enc.asp|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/GraphColouring/graph_colouring-full_package.zip|download]] || ||26 ||Solitaire ||Yuliya Lierler and Marcello Balduccini || || || ||Yes ||Yes ||Yes ||Search ||NP ||ASP-Core ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/Solitaire|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/Solitaire/solitaire-trainInstances.zip|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/Solitaire/solitaire.enc.asp|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/Solitaire/solitaire-full_package.zip|download]] || ||27 ||Partner Units ||Anna Ryabokon, Andreas Falkner and Gerhard Friedrich || || || ||No ||Yes ||No ||Search ||NP ||- ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/PartnerUnits|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/PartnerUnits/partner_units-trainInstances.zip|download]] ||- ||[[http://www.mat.unical.it/aspcomp2011/files/PartnerUnits/partner_units-full_package.zip|download]] || ||28 ||Weight-Assignment Tree ||Yuliya Lierler || || || ||No ||Yes ||Yes ||Search ||NP ||- ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/WeightAssignmentTree|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/WeightAssignmentTree/weight_assignment_tree-trainInstances.zip|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/WeightAssignmentTree/weight_assignment_tree.enc.asp|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/WeightAssignmentTree/weight_assignment_tree-full_package.zip|download]] || ||30 ||Hydraulic Leaking ||Francesco Calimeri and Maria Carmela Santoro || || || ||Yes* ||Yes ||Yes ||Search ||P ||ASP-Core ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/HydraulicLeaking|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/HydraulicLeaking/hydraulic_leaking-trainInstances.zip|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/HydraulicLeaking/hydraulic_leaking.enc.asp|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/HydraulicLeaking/hydraulic_leaking-full_package.zip|download]] || ||31 ||Hydraulic Planning ||Francesco Calimeri and Maria Carmela Santoro || || || ||Yes* ||Yes ||Yes ||Search ||P ||ASP-Core ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/HydraulicPlanning|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/HydraulicPlanning/hydraulic_planning-trainInstances.zip|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/HydraulicPlanning/hydraulic_planning.enc.asp|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/HydraulicPlanning/hydraulic_planning-full_package.zip|download]] || ||32 ||Stable Marriage ||Francesco Ricca, Mario Alviano and Marco Manna || || || ||No ||Yes ||Yes ||Search ||P ||ASP-Core ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/StableMarriage|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/StableMarriage/stable_marriage-trainInstances.zip|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/StableMarriage/stable_marriage.enc.asp|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/StableMarriage/stable_marriage-full_package.zip|download]] || ||33 ||Maze Generation ||Martin Brain and Mario Alviano || || || ||Yes* ||Yes ||Yes ||Search ||NP ||ASP-Core ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/MazeGeneration|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/MazeGeneration/maze_generation-trainInstances.zip|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/MazeGeneration/maze_generation.enc.asp|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/MazeGeneration/maze_generation-full_package.zip|download]] || ||34 ||Partner Units - Polynomial ||Anna Ryabokon, Andreas Falkner and Gerhard Friedrich || || || ||No ||Yes ||Yes ||Search ||P ||ASP-Core ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/PartnerUnitsPolynomial|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/PartnerUnitsPolynomial/partner_units_polynomial-trainInstances.zip|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/PartnerUnitsPolynomial/partner_units_polynomial.enc.asp|download]] ||[[http://www.mat.unical.it/aspcomp2011/files/PartnerUnitsPolynomial/partner_units_polynomial-full_package.zip|download]] || ||35 ||Incremental Scheduling ||Marcello Balduccini and Yuliya Lierler || || || ||No ||Yes ||No ||Search ||NP ||ASP-Core ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/IncrementalScheduling|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/IncrementalScheduling/incremental_scheduling-trainInstances.zip|download]] ||- ||[[http://www.mat.unical.it/aspcomp2011/files/IncrementalScheduling/incremental_scheduling-full_package.zip|download]] || ||36 ||Tangram ||Andrea Formisano, Agostino Dovier and Enrico Pontelli || || || ||No ||Yes ||No ||Search ||NP ||- ||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/Tangram|view]] ||[[http://www.mat.unical.it/aspcomp2011/files/Tangram/tangram-trainInstances.zip|download]] ||- ||[[http://www.mat.unical.it/aspcomp2011/files/Tangram/tangram-full_package.zip|download]] || ||37 ||Combinatory Categorial Grammar ||Yulia Lierler and Peter Schüller || TK: Yes, encoding & data [[http://www.kr.tuwien.ac.at/staff/ps/aspccgtk/|here]] || TK: Yes, encoding & data [[http://www.kr.tuwien.ac.at/staff/ps/aspccgtk/|here]] || TK: Spec missing ||No ||No ||No ||Search/Optimization ||NP ||- ||- ||- ||- ||- || ||38 ||Rotating Workforce Scheduling ||Nysret Musliu || TK: Yes, data [[http://www.dbai.tuwien.ac.at/staff/musliu/benchmarks/|here]] || TK: Yes, data [[http://www.dbai.tuwien.ac.at/staff/musliu/benchmarks/|here]] || TK: Spec & encoding missing ||No ||No ||No ||Search/Optimization ||NP ||- ||- ||- ||- ||- || ||39 ||Shift Design and Break Scheduling ||Nysret Musliu & Lena Widl || TK: Yes, data [[http://www.dbai.tuwien.ac.at/proj/SoftNet/Supervision/Benchmarks/|here]] || TK: Yes, data [[http://www.dbai.tuwien.ac.at/proj/SoftNet/Supervision/Benchmarks/|here]] || TK: Spec & encoding missing ||No ||No ||No ||Search/Optimization ||NP ||- ||- ||- ||- ||- || ||40 ||Shift Design Problem ||Nysret Musliu || TK: Yes, data [[http://www.dbai.tuwien.ac.at/proj/Rota/benchmarks.html|here]] || TK: Yes, data [[http://www.dbai.tuwien.ac.at/proj/Rota/benchmarks.html|here]] || TK: Spec & encoding missing ||No ||No ||No ||Search/Optimization ||NP ||- ||- ||- ||- ||- || ||41 ||Portfolio Selection ||Andrea Schaerf & Luca Di Gaspero || TK: Yes, data [[http://satt.diegm.uniud.it/index.php?page=portfolio-selection|here]] || TK: Yes, data [[http://satt.diegm.uniud.it/index.php?page=portfolio-selection|here]] || TK: Spec & encoding missing ||No ||No ||No ||Search/Optimization ||NP ||- ||- ||- ||- ||- || ||42 ||Curriculum-Based Course Timetabling problem ||Andrea Schaerf & Luca Di Gaspero || TK: Yes, data [[http://tabu.diegm.uniud.it/ctt/|here]] || TK: Yes, data [[http://tabu.diegm.uniud.it/ctt/|here]] || TK: Spec & encoding missing ||No ||No ||No ||Search/Optimization ||NP ||- ||- ||- ||- ||- || ||43 ||Traveling Tournament problem ||Michael Trick || TK: Yes, data [[http://mat.gsia.cmu.edu/TOURN/|here]] || TK: Yes, data [[http://mat.gsia.cmu.edu/TOURN/|here]] || TK: Spec & encoding missing ||No ||No ||No ||Search/Optimization ||NP ||- ||- ||- ||- ||- || ||44 ||Social Golfer Problem ||Markus Trska & Nysret Musliu || TK: Yes, data [[http://web.student.tuwien.ac.at/~e0225855/sgp/sgp.html|here]] and prolog encoding [[http://web.student.tuwien.ac.at/~e0225855/various/golf_swi.pl|here]] || TK: Yes, data [[http://web.student.tuwien.ac.at/~e0225855/sgp/sgp.html|here]] and prolog encoding [[http://web.student.tuwien.ac.at/~e0225855/various/golf_swi.pl|here]] || TK: Spec & encoding missing ||No ||No ||No ||Search/Optimization ||NP ||- ||- ||- ||- ||- || |
* '''Sample Instances'''. A link to sample instances of the given problem. |
Official Problem Suite
Problem List - Model & Solve and System Track
Nr |
Name |
Author(s) |
Type |
Complexity |
Domain |
Problem Description |
Sample Instances |
N01 |
Permutation Pattern Matching |
Martin Lackner, Andreas Pfandler |
Search |
NP |
Combinatorial |
|
|
N02 |
Valves Location Problem |
Andrea Peano |
Optimization |
Beyond NP |
Combinatorial |
|
|
N03 |
Rotating Workforce Scheduling |
Francesco Calimeri, Thomas Krennwallner, Nysret Musliu |
Search |
|
Scheduling |
|
|
N04 |
Connected Maximum-density Still Life |
Christian Drescher |
Optimization |
Beyond NP |
AI |
|
|
N05 |
Graceful Graphs |
Christian Drescher |
Search |
|
Graph |
|
|
N06 |
Bottle Filling Problem |
Wolfgang Faber |
Search |
|
Combinatorial |
|
|
N07 |
Nomystery |
Giovambattista Ianni, Carlos Linares López*, Hootan Nakhost* |
Search |
|
Planning |
|
|
N08 |
Sokoban |
Giovambattista Ianni, Wolfgang Faber*, Carlos Linares López* |
Search |
|
Planning |
|
|
N09 |
Ricochet Robots |
Julius Höfler, Martin Gebser, Philipp Obermeier, Roland Kaminski, Torsten Schaub |
Search |
|
Puzzle |
|
|
O10 |
Crossing Minimization |
Carmine Dodaro, Graeme Gange*, Peter Stuckey* |
Optimization |
Beyond NP |
Graph |
|
|
O11 |
Reachability |
Carmine Dodaro, Giorgio Terracina* |
Query |
P |
Graph |
|
|
O12 |
Strategic Companies |
Mario Alviano, Marco Maratea*, Francesco Ricca* |
Query |
Beyond NP |
AI |
|
|
O13 |
Solitaire |
Marcello Balduccini, Yuliya Lierler* |
Search |
NP |
Puzzle |
|
|
O14 |
Weighted-Sequence Problem |
Marcello Balduccini, Yuliya Lierlier, Shaden Smith |
Search |
NP |
Database |
|
|
O15 |
Stable Marriage |
Mario Alviano, Carmine Dodaro, Francesco Ricca |
Search |
P |
Graph |
|
|
O16 |
Incremental Scheduling |
Marcello Balduccini, Yuliya Lierler* |
Search |
NP |
Scheduling |
|
Problem List - System Track only
Nr |
Name |
Author(s) |
Type |
Complexity |
Domain |
Problem Description |
Sample Instances |
N17 |
Qualitative Spatial Reasoning |
Jason Jingshi Li |
Search |
NP |
Formal logic |
|
|
N18 |
Chemical Classification |
Despoina Magka |
Search |
P |
Natural Sciences |
|
|
N19 |
Abstract Dialectical Frameworks Well-founded Model |
Stefan Ellmauthaler, Johannes Wallner |
Optimization |
|
Formal logic |
|
|
N20 |
Visit-all |
Giovambattista Ianni,Nir Lipovetzky*, Carlos Linares López* |
Search |
|
Planning |
|
|
N21 |
Complex Optimization of Answer Sets |
Martin Gebser, Roland Kaminski, Torsten Schaub |
Search |
|
Synthetic |
|
|
O22 |
Knight Tour with Holes |
Francesco Calimeri, Neng-Fa Zhou* |
Search |
NP |
Puzzle |
|
|
O23 |
Maximal Clique Problem |
Guenther Charwat, Martin Kronegger, Johan Wittocx* |
Optimization |
Beyond NP |
Graph |
|
|
O24 |
Labyrinth |
Carmine Dodaro, Giovambattista Ianni, Martin Gebser* |
Search |
NP |
Puzzle |
|
|
O25 |
Minimal Diagnosis |
Marcello Balduccini, Martin Gebser* |
Search |
Beyond NP |
Diagnosis |
|
|
O26 |
Hanoi Tower |
Gayathri Namasivayam, Miroslaw Truszczynski, Shaden Smith, Alex Westlund |
Search |
NP |
AI |
|
|
O27 |
Graph Colouring |
Johannes Wallner, Marcello Balduccini*, Yuliya Lierler* |
Search |
NP |
Graph |
|
Legend
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.
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.
Final Problem Description. Problem specifications in their official form, with latest notes and updates.
Sample Instances. A link to sample instances of the given problem.