
RANDOMLY GENERATED INSTANCES OF BOOLEAN OPTIMIZATION PROBLEMS

By : Thomas DAVOINE, Peter L. HAMMER, Bela VIZVARI
At: RUTCOR, Rutgers University
On: 2000


PART 1   PURPOSE :

Those randomly generated Boolean Optimization Problems (BOOP) have been used to assess
the efficiency of BOOP Heuristics. The results of the Heuristic runs have been compared
to either the optimal solution, or the best solution found by a common and efficient branch-and-bound
method within a certain amount of time.


PART 2   OVERVIEW :

Instances with the same characteristics belong to the same so-called  'Class' of problems:
- same number of variables
- same number of terms
- same percentage of variables that are complemented
- same max and min lengths of terms

The name and definitions of each class are taken from the paper
[1] ' A Heuristic for Boolean Optimization Problems ', by T.Davoine, P.L.Hammer, B.Vizvari


PART 3  DATA STRUCTURE FOR PROBLEMS :

There are two possible data structures for an instance:

Format 1: the first line contains the number of variables $n$, and
then the number of terms $m$. Lines 2-$m$ contains the terms. For instance,
if the first term is $x_1x_3\bar{x}_4$, and $n=8$, then line 2 is
$ 1 0 1 -1 0 0 0 0 $. The last line contains the objective function
coefficients, in a decreasing order. That means that variables are
numbered so that the first variable has highest objective function coefficient,
 and so on.

Example:

 8 4
 1 0 1 -1 0 0 0 0
 0 0 1 1 1 0 0 -1
 1 0 0 0 1 1 0 0
 0 0 0 0 1 1 1 -1
 25 25 23 20 20 12 10 2


Format 2:  the first line contains the number of variables $n$, and
then the number of terms $m$. The second line {\bf must} have a $-2$.
 Lines 3-$m+1$ contains the terms. For instance,
if the first term is $x_1x_3\bar{x}_4$, and $n=8$, then line 2 is
$ 3 1 3 -4 $, where the first element is the length of the term.
 The last line contains the objective functions
coefficients, in a decreasing order. That means that variables are
numbered so that the first variable has highest objective function coefficient,
 and so on.

Same example:
 8 4
 -2
 3 1 3 -4
 4 3 4 5 -8
 3 1 5 6
 4 5 6 7 -8
 25 25 23 20 20 12 10 2

For large problems, the format 2 saves a lot of space, when the problems have
some short terms.


PART 4   SOLUTIONS:

For each class of file, there is an associated file that records the best solutions found
by the BOOP Heuristics described in the paper [1], and by CPLEX 6.0 within a
certain amount of time, as specified in the paper [1].

In this report file are also contained other measurements of performance for the Heuristics
of the paper [1].

Please note the following abuse of language: the solution found by CPLEX 6.0 is
recorded under the 'Optimal value' entry.  