Call for Benchmark Problems

The Third Answer Set Programming Competition will start with the the collection of benchmarks problems and instances. All participants and researchers are encouraged to provide their help by proposing and/or devising new challenging benchmark problems, and providing support for them.

Benchmark problems will be collected, selected and (possibly) refined with the help of the ASP community. Problems and instances will be eventually published on the competition web site.

Any kind of problem can be submitted; however, 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.

Schedule

• Problem Proposal and Discussion

  • November 22th, 2010 - EasyChair submission site is open

  • December 25th, 2010 - Problem Proposal and Discussion is closed

• Problem Validation and Final Submission

  • January 3rd, 2011 - Notification of acceptance, list of candidate problems is out

  • January 3rd, 2011 - Problem finalization starts

  • January 10th, 2011 - Final Acceptance, problems selection is out

Problem categories

Problems will be selected and classified according to this Problem Classification.

In order to guarantee a fair balance between several factors (relative importance of the various complexity categories, modeling difficulty and expressiveness, standard vs open language) problems will be roughly (as far as possible) selected according to the following quotas:

• System competition:

  • Language: ASP-Core (90%) and ASP-RFC (10%)

    Type: search and query

    Complexity: P (30%), NP (50%), Beyond NP (20%)

• Model & Solve competition:

  • Language: open

    Type: search (60%) and optimization (40%) problems

    Complexity: P (30%), NP (50%), Beyond NP (20%)

Problem submission procedure

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. The community is invited to discuss and improve the proposals. At the second stage, the organizing committee will validate a selection of benchmarks (see Final acceptance of problems); each selected problem will be completed by original contributor(s).

Submission, discussion and selection of benchmark problems is handled via the EasyChair system. Instructions for submitting a benchmark problem and participating to the discussion follow.

Problem submission

To submit a new problem just login the EasyChair system taking the Author role.

A problem submission is handled just like a paper submission. The system will require to fill a form, in which title (conventional problem name), abstract (problem specification), and problem classification (see Section Benchmark problem classification) have to be provided by checking appropriate form items; EasyChair will require also to fill the keyword fields, please provide us with some.

Problem specifications can be either partial (problem specification only) or detailed. A submission can be uploaded in EasyChair (as a paper submission) enclosed in a a single compressed package (zip and {tar.gz are allowed formats), containing:

1. a textual problem description (same as the abstract) where both names and arguments of input and output predicates are clearly specified;
2. a problem encoding;

3. some sample instances, that is some instances for the problem, which comply with the Input specification (see Problem I/O and Instance Specification), added in order to help evaluating the specification (sample instances should not be used for the competition).

4. a correctness checker (optional), that is, a program 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 (and in case of an optimization problem, the program should be able to compute the "quality" of the answer).

The above information shall be provided according to the Problem Package Format information.

Abstract only submissions

Abstract-only submission are accepted in the proposal stage. For abstract-only submissions, check the corresponding box at the end of the submission page, and just provide the problem statement in the abstract textfield. The problem statement must be anyway unambiguous and include the description of input and output predicates according to the problem description format described above.

In this stage, the submission of correctness checkers, as well as problem encodings and sample instances, are optional and left up to participants; nonetheless, we are grateful if you can already provide us with some. Especially, the submission of problems encodings often helps in disambiguating blurred specifications, so its provision is greatly appreciated.

Problem discussion

Benchmarks can be discussed by accessing Easychair taking the PC Member role.

The usual comment tools provided by EasyChair will be used to post comments and discuss the submissions. Unlike the usual conference "submit, then discuss" procedure, the discussion will be ongoing while problems are being submitted.

Researchers interested in discussing/improving problem proposals can ask for the virtual program committee member role in the EasyChair system. In particular, authors will be added as participants to the discussion by default; people interested only in discussing problems can send an e-mail to mailto:aspcomp2011__AT__mat.unical.it with subject:

• DISCUSSION: First Name - Second Name - Email

for obtaining access to the discussion. The organizing committee will take into account comments in order to select problems in the second stage.

• 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. Benchmark problems that are accepted by the organizing committee (see Final acceptance of problems) will be then finalized by the authors.

Finalized submission shall be uploaded to EasyChair enclosed in a single compressed package (zip, rar, and tar.gz are allowed formats), containing:

1. the textual problem description (same as the abstract) where both names and arguments of input and output predicates are clearly specified;
2. the problem encoding;
3. a correctness checker;

4. either an instance generator or at least 30 hard instances of the problem (using only input predicates);

5. a "demonstration" that the benchmark problem can be effectively solved on the class of instances provided, e.g. a report about tests carried out on a system of choice.

The above information shall be provided according to the Problem Package Format information.

At least one among item 4 and 5 must be provided. 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 difficult in terms of expected evaluation time.

Programs with Function symbols and integers

Programs with function symbols and integers are in principle subject to no restriction. For the sake of Competition, and to facilitate implementors of ASP-RFC and ASP-Core it is prescribed that

• each selected problem encoding P must provably have finitely many finite answer sets for any of its benchmark instance I, that is AS(P U I) must be a finite set of finite elements. "Proofs" of finiteness can be given in terms of membership to a known decidable class of programs with functions and/or integers, or any other formal mean.

• a bound k_P on the maximum nesting level of terms, and a bound m_P on the maximum integer value appearing in answer sets originated from P must be known. That is, for any instance I and for any term t appearing in AS(P U I), the nesting level of t must not be greater than k_P and, if t is an integer it must not exceed m_P.

The values m_P and k_P will be provided in input to participant systems, when invoked on P: problem designers are thus invited to provide such values accordingly.

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 Section Problem I/O and Instance Specification);

2. The set of provided instances counts less than 25 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;