Back to files

Contents

This package contains the C++-Sources of an implicit enumeration algorithm "opbdp" for solving 0-1 (or pseudo-Boolean) optimization problems with integer coefficients. Also included is as technical report describing the basic techniques used and some sample problems.

The package is available from

http://www.mpi-inf.mpg.de/units/ag2/software/opbdp See "Installation:" in this file for installing the package.

Description

For an in-depth treatment of logic-based constraint solving techniques see "Logic-Based 0-1 Constraint Programming, OR/CS Interface Series, 1996" published by Kluwer (http://www.wkap.nl).

A linear 0-1 term can either be maximized or minimized wrt. a set of linear constraints over 0-1 variables. All linear 0-1 constraints are transformed to >= inequalities. The optimization problem is solved by solving a sequence of satisfiability problems of a set of linear 0-1 constraints. The search tree is explored depth first. Each time a satisfiable solution is found, the value v of the objective function objf under this solution is calculated and the the constraint objf >= v+1 is added. Then enumeration is continued until unsatisfiability is detected.
The previous solution then was an optimal solution.

The implicit enumeration algorithm can be seen as a generalization of the Davis-Putnam enumeration algorithm for solving propositional satisfiability problems in clausal form to the pseudo-Boolean case.

A technical report is included as postscript-file "mpii952002.ps" describing the techniques used in opbdp.

The package can use different heuristics for selecting the variable on which to split next.
It should be fairly easy to write your own variable selection heuristics. Currently, five heuristics are available:

no heuristics, i.e. next free variable to 1
an adapted two-sided Jeroslow-Wang heuristics <default> (coming from propositional satisfiability problems)
one similar to h1; (probably not exceeding double range floating point precision)
selects a literal that yields maximal further fixings in the next step
randomly selects a literal (rand) Each heuristic can additionally be modified in that not a literal L_i that maximizes value(L_i) + value(~L_i) is chosen but a literal L_i which maximizes min(value(L_i),value(~L_i)). Furthermore, each heuristic can be combined with the strategy to choose first the literal with the maximal coefficient in the objective function if available.

One challenge is to provide better cheap variable selection heuristics. (Currently, most of the time is spent in the adapted Jeroslow-Wang heuristics).

A problem is read in via stdin and the results are reported on stdout. See "Problem-Format:" in this file for the format of the problem description expected by opbdp.

Example

Max-Planck-Institut f. Informatik type opbdp -H for help problem consists of 15 inequalities and 33 variables General coefficient reduction changed 6 coefficients Preprocessingtime (secs) : 0.07

Value Nodes / Fixed / Time New Local Minimum: 3966 84 / 177 / 0.00 New Local Minimum: 3716 87 / 182 / 0.00 New Local Minimum: 3457 93 / 189 / 0.00 New Local Minimum: 3302 98 / 200 / 0.00 New Local Minimum: 3188 209 / 543 / 0.00 New Local Minimum: 3164 308 / 834 / 0.00 New Local Minimum: 3089 311 / 842 / 0.00 Global Minimum: ****** 3089 ****** Explored Nodes: 897 Max. Depth: 16 Fixed Literals: 2729 Time (secs) : init(0.00) prepro(0.07) solve(0.02)

The first found feasible assignment yields the value 3966 for the objective function. 84 nodes have been explored and 177 variables have been fixed so far in 0.01 seconds cpu time. The maximal value of the objective function is 3089. We found it after exploring 31 nodes and fixing 828 variables in 0.00 seconds. We prove optimality after exploring 897 nodes, fixing 2698 variables in 0.06 seconds. The time for reading the problem and initializing the data structures was 0.02 seconds. 0.06 seconds have been spent in the preprocessing phase, which reduced 6 coefficients.

The problem read can also be written on a file readable for either opbdp, cplex, or lp_solve.

Preprocessing

opbdp 1.0 includes several kinds of preprocessing techniques for the constraints. In the following we mean by yields or implies 'happens or holds after pseudo-Boolean unit resolution has been applied'.

fixed literals: F -> If there exists a constraint cL >= d such that
cL >= d => L_i >= 1, then L_i is fixed to 1. f -> If fixing L_i yields an inconsistent problem,
then ~L_i is fixed to 1. If fixing L_i implies fixing of L_j and fixing of ~L_i implies fixing of L_j, then L_j is fixed to 1.
equation detection: If fixing L_i yields L_j >= 1 and fixing L_i yields ~L_j >= 1, then the equation L_i = ~L_j is established and applied.
coefficient reduction techniques: We know that if for a constraint
ciLi + cL >= d in a set of constraints S we have
S and Li=1 => cL >= b, then
(d-b)Li + cL >= d is valid wrt S. If 0 <= d-b < ci, we replace ci by d-b and thus have reduced the coefficient. For getting a bound for cL we generate 'minimal covers' for cL and sum up the smallest coefficients of these covers. (Maybe I will update the technical report on request). What is missing is coefficient and rhs increasing. The same technique but just not implemented yet.

The preprocessing techniques are quite effective for some problems, i.e., when solved with a LP-based solver afterwards. For example,

opbdp -pFfccf -wcp0548.cr.lp < p0548.opb yields the file p0548.cr.lp, which can be solved by cplex with standard options in about 19 hours and 580000 nodes, whereas the original problem p0548 was not solved by cplex within 110 hours and 1150000 million nodes. Even the optimal solution was not yet found and a gap of 100 (8739-8639) remains.

Linearization

In order to solve non-linear 0-1 problems the problem is first linearized. Either Fortet's linearization method or my own can be used to read in and linearize nonlinear 0-1 problems.
Fortet's method introduces new variables but is polynomial in the size of the problem. My linearization method does not introduce new variables, but problem size may possibly explode; try both. Some nonlinear problems from Hamdy A. Taha, 1972,"Management Science" "A Balasian-based algorithm for zero-one polynomial programming" are included as taha*.[on]pb. For them Fortet-linearization seems to be better.

% opbdp -nf -p < taha1c.npb
opbdp 1.1 #2 Copyright (C) 1995-2005 Peter Barth <barth@mpi-sb.mpg.de>

Max-Planck-Institut f. Informatik type opbdp -H for help
problem consists of 13 inequalities and 25 variables Preprocessingtime (secs) : 0.00

                       Value        Nodes /    Fixed /       Time 
New Local Minimum:                 5            3 /       16 /       0.00

Global Minimum: ****** 5 ******
Explored Nodes: 5 Max. Depth: 10 Fixed Literals: 30 Time (secs) : init(0.01) prepro(0.00) solve(0.00)

% opbdp -np -p < taha1c.npb
opbdp 1.1 #2 Copyright (C) 1995-2005 Peter Barth <barth@mpi-sb.mpg.de>

Max-Planck-Institut f. Informatik type opbdp -H for help
problem consists of 301 inequalities and 25 variables Preprocessingtime (secs) : 0.00

                       Value        Nodes /    Fixed /       Time 
New Local Minimum:                 7           16 /       32 /       0.01
New Local Minimum:                 5           20 /       62 /       0.01

Global Minimum: ****** 5 ******
Explored Nodes: 68 Max. Depth: 12 Fixed Literals: 284 Time (secs) : init(0.10) prepro(0.00) solve(0.02)

Often preprocessing does a lot for linearized problems.

% opbdp -np -pFfccffecf < taha1c.npb
opbdp 1.1 #2 Copyright (C) 1995-2005 Peter Barth <barth@mpi-sb.mpg.de>

Max-Planck-Institut f. Informatik type opbdp -H for help
problem consists of 301 inequalities and 25 variables Fixing : Y1
1 Literal has been fixed by 'fixing'
Fixingcheck : Y2 Y15
2 Literals have been fixed by 'fixingcheck' General coefficient reduction changed 189 coefficients Fixingcheck : Y3
1 Literal has been fixed by 'fixingcheck' General coefficient reduction changed 89 coefficients Preprocessingtime (secs) : 1.20

                       Value        Nodes /    Fixed /       Time 
New Local Minimum:                 5           17 /       44 /       0.0-1

Global Minimum: ****** 5 ******
Explored Nodes: 45 Max. Depth: 10 Fixed Literals: 151 Time (secs) : init(0.10) prepro(1.20) solve(0.00)

Interactive mode:

The whole functionality of opbdp can be used interactively. Start opbdp with "opbdp -i" and type help. The interface is quite simple and is best used within emacs, for example.

Logic Cuts:

Logic cuts (valid implications of the constraint set) can be generated and added to the problem. See book "Logic-based 0-1 constraint programming" for further details.

Portability: Porting opbdp to Unix systems should be a matter of running make. opbdp definitely works under SunOS, Solaris and Linux. The software was developed on a SUN-SPARC running Solaris 2.4 and now maintained under Linux. opbdp also compiles and runs on Windows with the native Microsoft C++ compiler. Just drop all files in a new console project, disable precompiled headers, define COEFFICIENT_int, do not include two_pow_table.cpp nor PBTermParse.cpp in the project files (as they are included in other cpp files) and build it.
Installation: Create a directory (e.g. opbdp) and unpack the files in that directory. Change the Makefile to suit your needs, i.e. choose a C++-compiler that handles templates correctly. Any recent gcc (3.x, 4.x) will do.

Then type "make opbdp", which should build the executable "opbdp".

Type "make libpbcs.a" if you want to have a library version of opbdp. Use "PBCS.h" as general include file.
The file pbcsia.cpp, which implements the interactive mode, contains calls to almost all functions a user might need in an application and may serve as a reference.

Please mail me whether or not you succeeded in installing the system. I'd be glad to incorporate any machine specific changes.

If you encounter any problems while using the package, please recompile it with the the compiler options

-DVERBOSE -DCHECK
and run the same problem again (it will run much slower!). Probably an error message indicates the kind of the problem.

Just send me the problem and I will have a look.

Memory requirements are relatively high depending on the size of the problem and on the number of Boolean variables in the problem due to the indexing data structures (although now they are dynamically allocated (10% performance)). As memory is being cheap nowadays this might not be a big problem.

Please send comments and bug reports to:

        Dr. Peter Barth
        barth@mpi-sb.mpg.de
        Max-Planck-Institut fuer Informatik
        Im Stadtwald
        66123 Saarbruecken, Germany

Problem-Format:

Files containing 0-1 optimization problems to be solved by opbdp have the following format.
The first nonempty noncomment line represents the objective function. Each of the other nonempty noncomment lines represents a constraint. An empty line is a line consisting of just tabs and blanks or comments. A comment line is a line starting with ''. A comment is a text in one line surrounded by '/' and '*/'. Comments are ignored while reading the problem.

A <product> is a coefficient-literal pair of the form <coeff>[* ]<literal>, where coeff is a non zero integer number and <literal> is either a name of a 0-1 variable of the form [A-Za-z_]+ or the negation of a name of a 0-1 variable of the form ~[A-Za-z_]+. ~<name> is an abbreviation for 1-<name>. <variable> is a valid abbreviation for 1*<variable>. A <term> is sum of <product>s of the form

<product> | <product> [+-] <term> | <constant> [+-] <term> The objective function is a <term>, optionally starting with "max:", resp. "min:", indicating that the objective function has to maximized, resp. minimized, wrt the set of constraints. A constraint is of the form

<term> <op> <integer>
where <integer> is an arbitrary integer number and <op> is either ">=", "<=" or "=".
Nonempty noncomment lines may contain ';', which is ignored. Furthermore, each constraint line may start with a constraint name of the form [A-Za-z_\t ]+:, which is ignored.

The files p0033.opb, bm23.opb, and stein27.opb are included as examples.

Nonlinear format is a bit different (i.e., A B C is parsed as ABC and not as A + B + C). In nonlinear format you can use brackets + - and * freely. Remark: The parser is not very fast... (I hate to write I/O routines :-)

Remark: opbdp should accept files that are generated by mps2eq (ftp ftp.es.ele.tue.nl as pub/lp_solve/mps2eq_0.2.tar.Z, Author: Michel Berkelaar michel@es.ele.tue.nl) if you delete the Bounds and int section. Furthermore, it should accept lp-format generated by CPLEX, if you delete the Bounds and Integer section and bring all constraints on one line (in emacs: replace "\n \([+-<>=]+\)" by " \1").

Have fun

Peter