Building a Solver: Warnings
- Please make sure to include the step below in every solver before running search:
- Before doing any processing:
- Normalize the constrains (overlapping scopes)
- Enforce all unary constraints
- Decompose the problem into idependent components, and store them
in one data structure of subproblems.
- During the processing:
- Ensure that the parameters measure (denisty, number of variables,
number of constaints, widthm etc. ) are maxed or summed over all
- Replace each processing step with a iteration loop of the
processing over each of the subcomponents.
- Ensure that the measurements (CPU time, #NV, #CC) are summed over
all indenpendent components.
- After the processing:
- Run the solution of each subproblem through the solution checker.
- When you start writing your solver, please be watchful for the
traps listed on the online benchmark site under "Generating Instances in
As of May 19, 2010 There are some traps that must be avoided. Check that your solver has no problem with:
two constraints defined on the same scope (for example, the instance fapp01-0200-0).
- several constraints that share the same scope under permutations (for example, see constraints C0 and C13 in langford-2-4-ext).
- empty relations (for example, the instance bqwh-15-106-0_ext).
- unary constraints (for example, the instance zebra).
- the following instances: queens-12 and queens-12-ext. Do you find 14200 solutions?
- the following instances: crossword-m1-debug-05-01 and crossword-m1-debug-05-02. Do you find 48 solutions?
- Check the variety of tools available online for checking
solutions, instances, etc.
Acknowledgment: Christophe Lecoutre, Olivier Roussel, Shant Karakashian, Ken Bayer.
Last modified: Fri Feb 18 16:32:17 CST 2011