Call for Benchmark Problems

The 4th Open Answer Set Programming Competition is open to ASP systems and *any other system* based on a declarative specification paradigm.

Participants will compete on a selected collection of declarative specifications of benchmark problems, taken from a variety of domains as well as real world applications, and instances thereof.

These include but are not limited to:

• Deductive database tasks on large data-sets
• Sequential and Temporal Planning
• Classic and Applicative graph problems
• Puzzles and combinatorics
• Scheduling, timetabling and other resource allocation problems
• Combinatorial Optimization problems
• Ontology reasoning
• Automated Theorem Proving and model checking
• Reasoning tasks over large propositional instances
• Constraint Programming problems
• Other AI problems

We encourage to provide help by proposing and/or devising new challenging benchmark problems.

The submission of problems arising from applications having practical impact are strongly encouraged; problems used in the former ASP Competitions, or variants thereof, can be re-submitted (see Problem Submission).

Benchmark authors are expected to produce a problem specification and an instance set (or a generator thereof). Problems will be classified and selected in order to obtain a fair balance between several factors (including complexity category, modeling difficulty, expressiveness, application domain, etc).

Schedule

• Problem Proposal and Discussion

  • Aug 31th, 2012 - Problem submission deadline

• Problem Validation and Final Submission

  • Sep. 30th, 2012

Problem Submission

The problems submission procedure will consist of two stages:

1. Proposal and discussion;
2. Validation and final submission.

At the first stage, problem descriptions are submitted and made publicly available in the competition website. The community is invited to discuss and improve the proposals. At the second stage, the organizing committee will validate a selection of benchmarks; each selected problem will then be completed under the responsibility of the original contributor(s).

Submission, discussion and selection of benchmark problems is handled via email; details are reported below.

How To Submit a Problem

Problem specifications can be initially submitted in a preliminary form (abstract); authors will be then asked to provide a complete specification.

To submit a new problem just prepare a benchmark package (see Package Description) and send it by email to Benchmark Submission with subject:

• SUBMISSION: Benchmark Name

Package Description

• A preliminary submission (see the Examples) can be done by providing problem name and problem specification only. (We encourage to provide an ASP encoding and sample instances also.)

• A complete problem submission (see the Examples) has to be enclosed in a single compressed package (zip and tar.gz are allowed formats), containing:

  1. a textual problem description where both names and arguments of input and output predicates are clearly specified (see Problem I/O);

  2. a problem encoding in ASP (optional);

  3. some sample instances in the form of ASP facts (see Instance Specification), added in order to help evaluating the specification (sample instances should not be used for the competition).

  4. a correctness checker, that is, a program (better if written in ASP whenever possible) or a script able to decide whether the output predicates occurring in some answer set form a solution to a given instance of the problem at hand. In case of an optimization problem, the program should be able to compute the "quality" of the answer (see Checker Specification).

  5. a "demonstration" in which the author provides sufficient arguments showing that the benchmark problem can be effectively solved nor it is trivial.

Note that: The problem statement must be anyway unambiguous and include the description of input and output predicates according to the problem description format described above. We are grateful if you can already provide us with a declarative encoding and some sample instance. Especially, the submission of problems encodings often helps in disambiguating blurred specifications, so its provision is greatly appreciated.

Problem Discussion and Validation

Benchmarks will be published in a specific section of the competition website.

Researchers interested in discussing/improving problem proposals can send an e-mail to Benchmark Discussion with subject:

• DISCUSSION: Benchmark Name <subject>

The community is strongly encouraged to participate to this important moment in which problems are submitted and evaluated.

Validation and final submission stage

Benchmark problems submitted and discussed in the first stage are evaluated by the competition organizing committee. As for paper submissions in a conference, authors will be notified regarding the final acceptance decision.

In this phase the contribution of benchmarks authors is fundamental, submission which are incomplete at the end of this stage are unsuitable for usage in the final competition and will be rejected (see Section Final acceptance of problems). The organizing committee takes the right to exclude benchmark problems whose provided instance family turns out to be blatantly too easy or too difficult in terms of expected evaluation time.

Final acceptance of problems

The final inclusion of problems in the competition is subject to to the conclusive approval of the competition organizing committee. Among the collected problems, the committee takes the right to discard problems which are not compliant with one or more of the following criteria:

1. The instance set (or the instances generator output) does not comply with the competition input/output format (see Problem I/O and Instance Specification);

2. The set of provided instances counts less than 50 instances, or the provided generator is missing or failing;
3. The provided (or generated) instances are trivial or not provably solvable when run on the competition hardware;