= Official Problem Suite = {{{#!wiki comment ATTENZIONE, mettere encoding solo per problemi che partecipano alla SYSTEM Competition. AGGIORNARE SEMPRE IL CHANGELOG, PENA UCCISIONE. }}} <
> Subscribe for updates in this page [[https://www.mat.unical.it/aspcomp2011/OfficialProblemSuite?action=subscribe|here]] (needs opening an user account). <
> {{{#!wiki comment }}} == Changelog == * Date: Feb 1st, 2011. * Maximal Clique: updated "Output format" section in specification. * Added a note on Weight Tree Assignment. * Date: Jan 31th, 2011 * Strategic Companies: Training Instances updated; * Removed Fastfood Optimization (#9) and Incremental Scheduling (#35) from the System Competition (they will stay in the M&S Competition only). * Date: 28/01/2011 * Added Table legenda; * Reverse Folding: added clarification; * Reachability: updated training instances; * Airport Pickup: Specification updated; * Incremental Scheduling: Specification updated. * Date: 27/01/2011 - Company Controls: Specification updated; * Date: 26/01/2011 - Weight-Tree Assignment: Training Instances updated; * Date: 26/01/2011 - Disjunctive Scheduling added; * Date: 26/01/2011 - Knight Tour: Training Instances,Encoding and Specification updated; * Date: 25/01/2011 - Hydraulic Leaking added; * Date: 25/01/2011 - Hydraulic Planning added; <
> == Legenda == Columns in the table below are to be read as following: * '''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. * '''Type'''. One of ''Search'', ''Optimization'', ''Query''. See the problem [[BenchmarkProblems|classification]] page. * '''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. * '''Final Problem Description'''. Problem specifications in their official form, with latest notes and updates. * '''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. <
> ||'''#'''||'''Problem Name'''||'''Author(s)'''||'''Present at the 2nd ASP Competition (2009)'''||'''Model & Solve Competition'''||'''System Competition'''||'''Type'''||'''Class'''||'''Language for System Competition'''||'''Final Problem Description'''||'''Training Instances'''||'''ASP-Core/ASP-RfC encoding'''|| ||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]]||-|| ||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]]|| ||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]]|| ||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/CompanyControl/company_controls-trainInstances.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/CompanyControlOptimize/company_controls_optimize-trainInstances.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]]|| ||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]]||-|| ||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]]|| ||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]]||-|| ||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]]|| ||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]]||-|| ||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]]|| ||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]]|| ||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]]|| ||15||Tomography (Graph set covering)||Neng-Fa Zhou||No||Yes||No||Optimization||NP||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/FinalProblemDescriptions/Tomography|view]]||[[http://www.mat.unical.it/aspcomp2011/files/Tomography/tomography-trainInstances.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]]||-|| ||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]]|| ||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]]|| ||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]]|| ||20||Numberlink||Naoyuki Tamura and Neng-Fa Zhou||Yes||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]]|| ||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]]||-|| ||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]]|| ||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]]|| ||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]]||-|| ||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]]|| ||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]]|| ||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]]||-|| ||28||Weight-Assignment Tree||Yuliya Lierler||No||Yes||No||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]]||-|| ||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]]|| ||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]]|| ||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]]|| ||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]]|| ||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]]|| ||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]]||-|| ||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]]||-||