Contents: ========= This package contains the C++-Sources of an implicit enumeration algorithm "opbdp" for solving linear 0-1 (or pseudo-Boolean) optimization problems with integer coefficients. The package is available via anonymous ftp: ftp.mpi-sb.mpg.de:pub/guide/staff/barth/opbdp/opbdp.tar.Z or www: http://www.mpi-sb.mpg.de/~barth/opbdp/opbdp.html See "Installation:" in this file for installing the package. Compressed binary files of the executable opbdp are provided for some architectures as: opbdp.arch.Z 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 last solution then is the 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 (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: % opbdp -pc < p0033.opb opbdp 1.0 #0 Copyright (C) 1995 Peter Barth 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.06 Value Nodes / Fixed / Time New Local Minimum: 3966 84 / 177 / 0.01 New Local Minimum: 3716 87 / 182 / 0.01 New Local Minimum: 3457 93 / 189 / 0.01 New Local Minimum: 3302 98 / 200 / 0.01 New Local Minimum: 3188 209 / 529 / 0.02 New Local Minimum: 3164 308 / 820 / 0.02 New Local Minimum: 3089 311 / 828 / 0.02 Global Minimum: ****** 3089 ****** Explored Nodes : 897 Fixed Literals : 2698 Time (secs) : init(0.01) prepro(0.06) solve(0.06) 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.02 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 is not yet implemented. 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: ============== 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. twinpeaks [12:22] 486 PBIneq -> opbdp -nf -p < taha1c.npb opbdp 1.1 #0 Copyright (C) 1995-96 Peter Barth Max-Planck-Institut f. Informatik type opbdp -H for help problem consists of 13 inequalities and 25 variables Preprocessingtime (secs) : 0 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) solve(0.01) twinpeaks [12:23] 487 PBIneq -> opbdp -np -p < taha1c.npb opbdp 1.1 #0 Copyright (C) 1995-96 Peter Barth Max-Planck-Institut f. Informatik type opbdp -H for help problem consists of 301 inequalities and 25 variables Preprocessingtime (secs) : 0 Value Nodes / Fixed / Time New Local Minimum: 7 16 / 32 / 0.00 New Local Minimum: 5 20 / 62 / 0.01 Global Minimum: ****** 5 ****** Explored Nodes: 68 Max. Depth: 12 Fixed Literals: 284 Time (secs) : init(0.19) prepro(0) solve(0.04) Often preprocessing does a lot for linearized problems. twinpeaks [12:23] 488 PBIneq -> opbdp -np -pFfccffecf < taha1c.npb opbdp 1.1 #0 Copyright (C) 1995-96 Peter Barth 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.14 Value Nodes / Fixed / Time New Local Minimum: 5 17 / 44 / 0.00 Global Minimum: ****** 5 ****** Explored Nodes: 45 Max. Depth: 10 Fixed Literals: 151 Time (secs) : init(0.18) prepro(1.14) solve(0.02) Interactive mode: ================= The whole functionality of opbdp can be used interactively. Start opbdp with "opbdp -i" and type help. The interface is very! simple but should work. 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. Installation: ============= Create a directory (e.g. opbdp) and unpack the package in that directory. Change the Makefile to suit your needs, i.e. choose a C++-compiler that handles templates correctly. lcc (Lucid SPARC C/C++ Compiler) and CC (SC3.0 15 Dec 1993 or newer) do the job. g++ (2.7.2) seems to work, best is SUN's CC. 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.C contains calls to almost all functions a user might need in an application. The software is developed on a SUN-SPARC running Solaris 2.4. 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. or 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)). Please send comments and bug reports to: 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 is a coefficient-literal pair of the form [* ], where coeff is a non zero integer number and 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_]+. ~ is an abbreviation for 1-. is a valid abbreviation for 1*. A is sum of s of the form | [+-] | [+-] The objective function is a , 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 where is an arbitrary integer number and 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 A*B*C and not as A + B + C). In nonlinear format you can use brackets + - and * freely. Remark: The reader is not very fast... (I hate I/O :-) Remark: opbdp should accept files that are generated by mps2eq (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