Differences between revisions 3 and 74 (spanning 71 versions)

Official Problem Suite

Contents

Official Problem Suite

Changelog

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.

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	view	get	get	Permutation Pattern Matching
N02	Valves Location Problem	Andrea Peano	Optimization	Beyond NP	Combinatorial	view	get	get	Valves Location Problem
N04	Connected Maximum-density Still Life	Christian Drescher	Optimization	Beyond NP	AI	view	get	get	Connected Maximum-density Still Life
N05	Graceful Graphs	Christian Drescher	Search	NP	Graph	view	get	get	Graceful Graphs
N06	Bottle Filling Problem	Wolfgang Faber	Search		Combinatorial	view	get	get	Bottle Filling Problem
N07	Nomystery	Giovambattista Ianni, Carlos Linares López, Hootan Nakhost	Search		Planning	view	get	get	Nomystery
N08	Sokoban	Giovambattista Ianni, Wolfgang Faber, Carlos Linares López	Search		Planning	view	get	get	Sokoban
N09	Ricochet Robots	Julius Höfler, Martin Gebser, Philipp Obermeier, Roland Kaminski, Torsten Schaub	Search		Puzzle	view	get	get	Ricochet Robot
O10	Crossing Minimization	Carmine Dodaro, Graeme Gange, Peter Stuckey	Optimization	Beyond NP	Graph	view	get	get	Crossing Minimization
N11*	Reachability	Carmine Dodaro, Giorgio Terracina*	Query	P	Graph	view	get	get	Reachability
N12*	Strategic Companies	Mario Alviano, Marco Maratea, Francesco Ricca	Query	Beyond NP	AI	view	get	get	Strategic Companies
O13	Solitaire	Marcello Balduccini, Yuliya Lierler*	Search	NP	Puzzle	view	get	get	Solitaire
O14	Weighted-Sequence Problem	Marcello Balduccini, Yuliya Lierlier, Shaden Smith	Search	NP	Database	view	get	get	Weighted-Sequence Problem
O15	Stable Marriage	Mario Alviano, Carmine Dodaro, Francesco Ricca	Search	P	Graph	view	get	get	Stable Marriage
O16	Incremental Scheduling	Marcello Balduccini, Yuliya Lierler*	Search	NP	Scheduling	view	get	get	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		view	get	get	Qualitative Spatial Reasoning
N18	Chemical Classification	Despoina Magka	Search	P	Natural Sciences		view	get	get	Chemical Classification (60+ MB)
N19	Abstract Dialectical Frameworks Well-founded Model	Stefan Ellmauthaler, Johannes Wallner	Optimization		Formal logic		view	get	get	Abstract Dialectical Frameworks Well-founded Model
N20	Visit-all	Giovambattista Ianni,Nir Lipovetzky, Carlos Linares López	Search		Planning		view	get	get	Visit-all
N21	Complex Optimization of Answer Sets	Martin Gebser, Roland Kaminski, Torsten Schaub	Search	Beyond NP	Synthetic		view	get	get	Complex Optimization of Answer Sets
N22*	Knight Tour with Holes	Francesco Calimeri, Neng-Fa Zhou*	Search	NP	Puzzle		view	get	get	Knight Tour with Holes
O23	Maximal Clique Problem	Guenther Charwat, Martin Kronegger, Johan Wittocx*	Optimization	Beyond NP	Graph		view	get	get	Maximal Clique Problem
O24	Labyrinth	Carmine Dodaro, Giovambattista Ianni, Martin Gebser*	Search	NP	Puzzle		view	get	get	Labyrinth
O25	Minimal Diagnosis	Marcello Balduccini, Martin Gebser*	Search	Beyond NP	Diagnosis		view	get	get	Minimal Diagnosis
O26	Hanoi Tower	Gayathri Namasivayam, Miroslaw Truszczynski, Shaden Smith, Alex Westlund	Search	NP	AI		view	get	get	Hanoi Tower
O27	Graph Colouring	Johannes Wallner, Marcello Balduccini, Yuliya Lierler	Search	NP	Graph		view	get	get	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. New 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 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 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 this. Note, the archive is password protected, credentials to be disclosed after the competition.
How we will select instances is specified here.

ASP Competition 2013: OfficialProblemSuite (last edited 2020-10-05 10:54:33 by FrancescoCalimeri)

-  ⇤ ← Revision 3 as of 2012-06-01 14:06:04 → 
  Size: 20536
  Editor: GiovambattistaIanni
  Comment:
+   ← Revision 74 as of 2013-03-02 11:30:10 → ⇥
  Size: 17627
  Editor: GiovambattistaIanni
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 1:
-#acl EditorsGroup:read,write All:
= Problem Suite Selection Table =
+#acl EditorsGroup:read,write All:read
= Official Problem Suite =
 Line 4:
+{{{#!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

}}}

== Changelog ==
 * 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.


== Problem List - Domains included in BOTH Model & Solve and System Track ==
<<BR>>
||<tablewidth="1024px" tableheight="421px">'''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/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|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/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|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/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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/09-Graceful-Graphs.tar.gz|get]] ||[[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|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/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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/26-Nomystery.tar.gz|get]] ||[[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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/27-Sokoban.tar.gz|get]] ||[[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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/14-Ricochet-Robot.tar.gz|get]] ||[[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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/29-Crossing-Minimization.tar.gz|get]] ||[[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|get]] || [[https://www.mat.unical.it/aspcomp2013/files/links/checkers/32-Reachability.tar.gz|get]] ||[[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|get]] || [[https://www.mat.unical.it/aspcomp2013/files/links/checkers/35-Strategic-Companies.tar.gz|get]] ||[[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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/22-Solitaire.tar.gz|get]] ||[[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|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/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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/33-StableMarriage.tar.gz|get]] ||[[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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/24-Incremental-Scheduling.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/incremental_scheduling-encoding.txt|Incremental Scheduling]] ||




== Problem List - Domains included in the System Track ONLY ==
<<BR>>
||<tablewidth="1024px" tableheight="421px">'''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/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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/02-Chemical-Classification.tar.gz|get]] ||[[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|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/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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/28-Visit-all.tar.gz|get]] ||[[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|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/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|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/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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/20-Maximal-Clique.tar.gz|get]] ||[[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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/17-Labyrinth.tar.gz|get]] ||[[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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/23-Minimal-Diagnosis.tar.gz|get]] ||[[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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/31-Hanoi-Tower.tar.gz|get]] ||[[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|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/checkers/19-GraphColouring.tar.gz|get]] ||[[https://www.mat.unical.it/aspcomp2013/files/links/encodings/graph_colouring-encoding.txt|Graph Colouring]] ||
-Line 8:
+Line 87:
- * '''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. '''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.
-Line 12:
+Line 90:
- * '''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.
 * '''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").
+ * '''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
-Line 24:
+Line 92:
-== Full Problem List ==
<<BR>>
||<tablewidth="1272px" tableheight="2821px" tablestyle="">'''#''' ||'''Problem Name''' ||'''Author(s)''' ||Suitable for 2013 '''System Track''' (YES/NO , 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<<BR>>''' ||'''System Competition 2011<<BR>>''' ||'''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]] ||
+in non-deterministic polynomial time in the size of input. '''Beyond-NP''': any other problem.
-Line 63:
+Line 94:
+ * '''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.
-Line 64:
+Line 100:
+== 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]].

ASP Competition 2013

Quick Links

Search Wiki

Page Tools