Official Problem Suite

Problem List - Domains included in BOTH Model & Solve and System Track

Problem List - Domains included in the System Track ONLY

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.

Changelog

• Mar 19th, 2013:
  • Update definition of Incremental Scheduling by means of some clarifications.
• Mar 16th, 2013:
  • Included check for multiple parallel moves in Nomystery checker;
  • The Visitall checker has now static binaries inside;
  • Removed the checkers for Reachability and Strategic Companies: query problems have a special treatment which makes checkers useless for participants;
  • Fixed the Labyrinth checker.
• Mar 15th, 2013:
  • A number of fixes in Sokoban aspcore-2 encoding and in the corresponding checker.
• Mar 14th, 2013:
  • Fixed directory in checker scripts of Graceful Graphs and Ricochet Robots.
  • Fixed encoding and checker for Knight Tour with Holes.
• Mar 3rd, 2013:
  • Fix example in Solitaire domain description page.
• Mar 2nd, 2013:
  • Fix in the syntax of weak contraints for all the ASPCore-2 encodings of optimization problems (Abstract Dialectical Frameworks, Crossing Minimization, Maximal Clique, Connected Maximum-Density Still Life, Valves Location)
• Mar 1st, 2013:

  • Fix semantics for pushtogoal and pushtonongoal in the Sokoban domain.

  • Add sample instances for Qualitative Spatial Reasoning domain.
  • Fix encoding for Graceful Graphs domain.
  • Fix encoding for Connected Maximum-density Still Life domain.
• Feb. 25th, 2013:
  • Updated Valves Location Problem and Abstract Dialectical Frameworks Well-founded Model Problem checkers to additionally output the costs of the provided solution.
• Feb. 22nd, 2013:
  • Updated Knight Tour with Holes description
• Feb. 18th, 2013:
  • Updated Bottle Filling sample instances
• Feb. 14th, 2013:

  • Updated ASP-Core-2 encoding for Valves Location

• Feb. 13th, 2013:

  • Updated ASP-Core-2 encoding for Ricochet Robot

  • Removed Rotating workforce scheduling from the problem list.

• Feb. 11th, 2013:

  • Marked with * codes of 2011's problems with slight different specification.

  • Updated Crossing Minimization and Maximal Clique Problem checkers to additionally output the costs of the provided solution.

  • A fix in the Valves Location encoding.

• Feb. 10th, 2013:
  • Fix, update and clarify specs for Rotating Workforce Scheduling.
• Feb. 9th, 2013:
  • Specified that trucks can carry more than one package in Nomystery.
  • Added sample instances for Reachability.
  • Update specs for Strategic Companies.
  • Fix specs for Reachability.