Preliminary Call for Solvers

SAT Competition 2003

February - May, 2003

This is a draft version of the Call For Participation to the SAT2003 competition. Last modification: September 25, 2002.

A new SAT competition is going to start on February 2003 and continue until May 2003. The results of the competition will be given at the SAT 2003 conference (Italy). That competition follows the SAT Competition 2002 started on March 10, 2002 and continued until (and during) SAT 2002 Symposium (May 6-9, 2002, Cincinatti, Ohio, USA).

Contents:

Who can submit?

Everyone except Laurent Simon.

What can be submitted?

Any program that solves (some) instances of the Boolean satisfiability problem. I.e., a complete or incomplete, deterministic or randomized SAT solver. The program must confirm the requirements concerning input/output format. It must be submitted in source compilable by typing "make" under standard Linux/UNIX environment. There are no restrictions concerning whether this solver is new or old, published or not, took part in other competitions or not. Note that up to three variants (same algorithm, same authors, different parameters) of the same solver can be submitted to the competition but only the best one will be considered for the qualification to the final stage. The solvers awarded at the previous competition will be automatically submitted to the competition in their awarding category.

How to submit?

Go to the submission page!

Laurent Simon (and possibly system administrators: this is unavoidable!) will be the only person who will have an access to solver sources and compiled programs. The sources will not be published and will be removed from the competition computers after the competition finishes.

What are the benchmarks?

The solvers will be run on benchmarks chosen from the pool of submitted benchmarks plus the pool of benchmarks remained unsolved during the previous SAT competition. The variables and the clauses will be permuted randomly (but in the same way for all solvers). (During the testing stage, solvers may also be run on other benchmarks.) There will be three categories of benchmarks: randomly generated, handmade (crafted) and industrial (see Call for Benchmarks for their description). Each of the categories will be split into several series of similar benchmarks scaling from smaller to larger instances.

How the competition will proceed?

Before the actual competition starts, the solvers will be tested for bugs. Buggy solvers will be then returned to their authors who will take their chances to fix the bugs. After possible re-submission, the solvers are checked again, the still-buggy solvers are excluded, and the actual competition starts. (While if a solver is found buggy even at a later stage, it is excluded anyway.)

We will first run each solver on each applicable benchmark (i.e., we will not run incomplete solvers on the benchmarks known to be unsatisfiable); smaller benchmarks come earlier. If a solver does not answer within time limit (to be determined when we know the number of submissions), it is interrupted . Randomized solvers will be started several times and the median time will be taken into account ("time limit" is charged for the unsuccessful tries).

For the next stage of the competition we select top N solvers (determined from the first stage by the same method as will be used for determining the winners after the second stage, considering only the best variant of a given solver) in each of the 6 categories and run them on the M smallest unsolved benchmarks (again, separately in each category), smaller benchmarks come earlier. We suppose N= M =4 now, but Laurent may change it right after the deadline if the number of benchmarks and/or solvers and/or our computers will be far from what we predict. Clearly, at this stage the time limit will be substantially larger.

A special session with a time limit given for solving a sequence of benchmarks may be organized, depending on the number of people willing to participate to that session, and provided that we get a satisfying automated framework to do it.

Who are the winners?

There will be two categories of solvers: complete ones and incomplete ones. (Clearly, a complete solver can take part in the competition in both categories). There will be also three categories of benchmarks . Thus, there will be a total of 2*3=6 winners, the same amount of second place winners etc.

All solvers that fall within 1 sec. * number of benchmarks of the winner are also declared winners.

However, if a solver solves no (zero) benchmarks for given category, it cannot be declared a winner under any circumstances. Furthermore, if the winner in a category was already awarded for that category in the previous competition, then there will be no award given for that category.

What are the awards?

A beautiful certificate, unless some people are willing to provide prizes to motivate the competition (then please contact the organizers).

Important dates

Organizing Committee

Laurent Simon (simon@lri.fr) and Daniel Le Berre (leberre@cril.univ-artois.fr)

Contact: SATcompetition@satlive.org

Competition homepage

http://www.satlive.org/SATCompetition/


[SAT Competition 2003 ] [ SAT 2002 ] [ SAT-Ex] [ SATLIB] [ SAT Live!]