Selection of benchmarks

Selection of CSP instances

Step 1

The jury asked Deepak Mehta to select the instances for the CSP competition. Here is the mail containing his selection sent to the jury on June, 10. Notice that this email was not revealed to the organizers before July, 1st.

Date: Tue, 10 Jun 2008 14:31:00 +0100 (IST)
From: Deepak Mehta 
To: Pierre Flener 
Cc: cspcomp-jury@cril.univ-artois.fr
Subject: Selected Instances

Dear Pierre,

Please find the excel file attached with this message.
In addition to the original worksheet that mentions all the instances of
all types, I have added five worksheets for the purpose of simplicity.
Each worksheet corresponds to  instances of only one type  (B-EXT, B-INT,
N-EXT, N-INT  and GLB), which is mentioned in  CELL A1:1.
The distribution of the number of selected instances for each
type is  mentioned in their respective worksheet.

In total I have selected 3258 instances, their distribution is as follows:
B-EXT -> 635
B-INT -> 700
N-EXT -> 700
N-INT -> 710
GLB   -> 553

For instances of type B-EXT it was not possible to respect the proportion
of random instances under 30%, since there are 1100 random instances out
of 1435. Even if I select all the non-random instances, the proportion of
random instances  will still be at least be 47% in order to reach the target of
700. For B-EXT, therefore, I have selected 365 random instances and 270
non-random instances.

For instances of type GLB, I have selected all the instances of all but
one series. This is because there  are 200 instances of the hidden series
pseudoSeries-glb of type GLB and I have selected only 100 of them.

Overall, I think I have given more priority to new and hidden instances,
and I have tried to keep diversity by selecting  instances from all  series as
suggested in one of the emails of Christophe.
I'm not sure if 3258 instances are enough. If not I can select some more
instances of either type  B-INt or N-Int category.

Regarding the seed that is required for selecting $k$ instances  of any
given series, I propose to use "2008" as a seed.

Regards,
Deepak.

[-- Attachment #2: descriptionInstances07_June.xls --]
[-- Type: application/VND.MS-EXCEL, Encoding: base64, Size: 621K --]

Here is the attached file: descriptionInstances07_June.xls

Step 2

The number of selected instances per serie was encoded in this file "data" and the "select.cc" program generated the following selection "selected".

An important point to notice is that Deepak has specified a precise number of satisfiable and unsatisfiable instances to select for several series. However the "data" file above doesn't distinguish between SAT and UNSAT instances. Indeed, Olivier Roussel has given up selecting specifically a number of SAT/UNSAT instances because he didn't have an exact listing of the status of each instance for several series (and a selection based on incomplete information would be probably biased). Deepak and the judges were asked if it was a problem and they answered that it was fine to ignore the SAT/UNSAT status

Only two contestants provided a list of at most 25 instances to be selected. Instances in this list which were not already selected were added to the selection.

Neng-Fa Zhou sent the following list of instances

Please find below a list of instances I selected.

1-fullins-5-4
2-fullins-4-5
BlackHole-4-13-e-2_ext
BlackHole-4-13-e-3_ext
BlackHole-4-13-m-1_ext
BlackHole-4-13-m-2_ext
BlackHole-4-7-h-8_ext
BlackHole-4-7-h-9_ext
FISCHER6-4-fair
FISCHER6-5-fair
FISCHER7-3-fair
FISCHER7-4-fair
FISCHER8-3-fair
FISCHER9-4-fair
fpga-10-8
graceful--K4-P2
haystacks-10
haystacks-11
haystacks-12
patat-02-comp-18
pigeons-30
pigeons-35
pigeons-40
pigeons-45
pigeons-50

Christophe Lecoutre sent the following list of instances

here is the list of 17 instances that I would like to be selected:

* 5 instances in category B-INT from archive rlfapScens11.tgz
scen11-f5.xml
scen11-f4.xml
scen11-f3.xml
scen11-f2.xml
scen11-f1.xml

This way, we hope to show how automatic variable symmetry breaking can be
useful.

* 12 instances in category N-EXT from crossword archives
crossword-m1c-uk-vg6-7_ext.xml
crossword-m1c-uk-vg7-7_ext.xml
crossword-m1c-uk-vg7-8_ext.xml

crossword-m1c-words-vg6-7_ext.xml
crossword-m1c-words-vg7-7_ext.xml
crossword-m1c-words-vg7-8_ext.xml

crossword-m1c-ogd-vg6-7_ext.xml
crossword-m1c-ogd-vg7-7_ext.xml
crossword-m1c-ogd-vg7-8_ext.xml
crossword-m1c-ogd-vg8-8_ext.xml
crossword-m1c-ogd-vg10-14_ext.xml
crossword-m1c-ogd-vg11-13_ext.xml

We then hope to show how STR is an efficient technique for table
constraints.

Step 3

It eventually appeared that the Cabinet instances used during the competition incorrectly assumed that the index in the ELEMENT global constraint was counted from 0. These instances were modified by Christophe Lecoutre to use and index starting at 1 (CabinetStart1 serie).

Selection of MAXCSP instances

Instances of interest for the MAXCSP competition are unsatisfiable instances. Because optimization is much harder than satisfiability, only easy CSP instances should be retained.

Deepak was asked to select MAXCSP instances among

instances selected for the 2008 CSP competition and which were proved unsatisfiable by at least one solver in less than 5 minutes
the max-csp instances available from the CPAI06 MAXCSP competition

His selection can be found in file maxcsp-selectedlist.xls. This file was translated as maxcsp-data and the "select.cc" program generated the following selection "maxcsp-selected" (the random seed used was 2008).

When the Cabinet instances where changed to instances CabinetStart1 where the index used in the element constraint starts at 1 instead of 0, a new random selection, restricted to the CabinetStart1 serie, was performed. This generated a different list of Cabinet instances.