Cutting Planes in Constraint Logic Programming

Alexander Bockmayr

MPI–I–94–207 February 1994 Author’s Address

Alexander Bockmayr, Max-Planck-Institut für Informatik, Im Stadtwald, D-66123 Saarbrücken, bockmayr@mpi-sb.mpg.de

Publication Notes

The present report has been submitted for publication elsewhere and will be copyrighted if accepted.

Acknowledgements

This work benefited from discussions with P. Barth and S. Ceria. It was supported by the German Ministry for Research and Technology (BMFT) (contract ITS 9103), the ESPRIT Basic Research Project ACCLAIM (contract EP 7195) and the ESPRIT Working Group CCL (contract EP 6028).

Abstract

In this paper, we show how recently developed techniques from combinatorial optimization can be embedded into constraint logic programming. We develop a constraint solver for the constraint logic programming language CLP(PB) for logic programming with pseudo-Boolean constraints. Our approach is based on the generation of polyhedral cutting planes and the concept of branch-and-cut. In the case of 0-1 constraints, this can improve or replace the finite domain techniques used in existing constraint logic programming systems.

Contents

1 Introduction 2 2 Constraint Logic Programming with 0-1 Constraints 3

2.1 Main problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Pseudo-Boolean and finite domain constraints . . . . . . . . . . . . . . . . . . . . . . 6

3 Solving 0-1 Constraints 6 3.1 Equality descriptions of the solution set . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.2 Inequality descriptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.3 Size of the representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.4 Strength of the representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.5 Defining a solved form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4 Computing the Solved Form 12 5 Branch and Cut 15 6 Conclusion and Further Research 17 A Correctness and Completeness of the Specialized Cutting Plane Algorithm 20 B Cut Lifting 22

1 Introduction

Constraint logic programming has been one of the major developments in declarative programming in recent years [JM94]. The idea is to combine logic programming with constraint solving over some domain of computation such as linear arithmetic, Boolean algebra, finite domains or lists. Various constraint logic programming systems have been developed so far, for example Prolog III [Col87], CLP(R) [JL87], CHIP [DvHS^{+}88], and CAL [ASS^{+}88]. Constraint logic programming has been very successful in many practical applications, in particular in problems from artificial intelligence and operations research. The combination of logic programming and constraint solving has benefits for both sides. From the viewpoint of logic programming, constraint solving techniques enhance the expressive power and the efficiency of logic programs. Efficient algorithms from mathematics, artificial intelligence or operations research can be embedded directly into the logic programming language and need not be coded on the level of unification and resolution using primitive system predicates. From the viewpoint of constraint solving, a high-level declarative programming language is available in addition to a pure constraint solver. This means that the problem to be solved can be represented in a natural and declarative way. The logic language not only can be used to generate the constraint formulas. It also allows us to handle those problem features that do not fit into the given constraint solving framework.

The general idea of constraint solving is to compute a solved form which represents all the solutions of a given constraint set. In many practical applications, however, one is interested in a solution which is optimal with respect to some objective function. Although optimization is not part of the original constraint logic programming framework, it is present in many existing constraint logic programming systems. In this paper, we show how recently developed techniques from combinatorial optimization can be embedded into constraint logic programming. We develop a constraint solver for our constraint logic programming language CLP(PB) for logic programming with pseudo-Boolean constraints. Originally, pseudo-Boolean constraints were seen as a generalization of Boolean constraints that combines Boolean algebra with a restricted form of arithmetic [Boc93]. Accordingly, our first approach to handle pseudo-Boolean constraints was to extend Boolean unification to the pseudo-Boolean case. In this paper, we describe a new constraint solver for linear pseudo-Boolean constraints which is based on cutting plane techniques from polyhedral combinatorics. Concerning 0-1 constraints, the generation of cutting planes and the concept of branch-and-cut can improve or replace the finite domain techniques and the branch-and-bound approach adopted in existing constraint logic programming systems.

The organization of the paper is as follows. In Section 2, we recall briefly some basic concepts of constraint logic programming and the language CLP(PB) for logic programming with pseudo-Boolean constraints. We also present the main problems which have to be solved by a constraint solver for this language. In Section 3, we discuss how a solved form for pseudo-Boolean constraints should look like. We define a solved form which is based on the notion of strong valid inequalities for the convex hull of the 0-1 solution set. A constraint set C is simplified by computing polyhedral cutting planes for the linear relaxation of C. In Section 4, we consider the question how this solved form can be computed in practice. To generate strong cutting planes, we propose to use the new lift-and-project method [BCC93b, BCC93a] recently developed in the context of mixed 0-1 optimization. On the one hand, this method has very nice theoretical properties. In particular, we can prove a correctness and completeness theorem for the constraint solver. On the other hand, the lift-and-project algorithm has also produced a number of impressive results on hard practical problems. In Section 5, we show how the cutting plane algorithm can be embedded into the more efficient branch-and-cut framework, without loosing the basic properties required in the context of constraint solving. Finally, in Section 6, we discuss briefly a possible extension of this work to the case of mixed 0-1 constraints.

2 Constraint Logic Programming with 0-1 Constraints

In its classical form [JL87], a constraint logic program over an algebra A consists of a finite set of rules of the form

p_{0}(t⃗_{0}) :− c_{1}(u⃗_{1}), …, c_{m}(u⃗_{m}), p_{1}(t⃗_{1}), …, p_{n}(t⃗_{n})

where p_{i} are predicate symbols different from the relation symbols in A, c_{j} are symbols denoting relations in A, and t⃗_{i}, u⃗_{j} are tuples of terms of A with additional undefined function symbols. The declarative semantics of such a rule is that the head p_{0}(t⃗_{0}) is logically implied by the conjunction c_{1}(u⃗_{1}) ∧ … ∧ c_{m}(u⃗_{m}) ∧ p_{1}(t⃗_{1}) ∧ … ∧ p_{n}(t⃗_{n}) of all constraints c_{j}(u⃗_{j}) and atoms p_{i}(t⃗_{i}) in the body.

Given a constraint logic program one has to choose a goal, which has the same form as the body of a rule. The operational semantics is based on two components: a constraint solver for A-relations and an adaptation of the resolution method from classical logic programming. For example, from the goal ?− c(t_{1}), p(t_{2}) and the rule p(t_{3}) :− d(t_{4}), q(t_{5}) we may derive the new goal ?− S(c(t_{1}), t_{2} ≐ t_{3}, d(t_{4})), q(t_{5}) provided that the constraint c(t_{1}), t_{2} ≐ t_{3}, d(t_{4}) is solvable in A and S(c(t_{1}), t_{2} ≐ t_{3}, d(t_{4})) is its solved form. A derivation sequence consists of goals with solvable constraints. It is successful when the last goal contains only constraints. These are called answer constraints and constitute the output of the program. A derivation sequence is finitely failed if the last goal cannot be expanded.

In [Boc93] we introduced a new constraint logic programming language CLP(PB) for logic programming with pseudo-Boolean constraints. The language CLP(PB) is an instance of the constraint logic programming language scheme CLP(X) [JL87]. Pseudo-Boolean constraints or 0-1 constraints combine Boolean algebra with arithmetic. A pseudo-Boolean function is an integervalued function f : {0, 1}^{n} → ZZ of 0-1 variables [HR68] and thus generalizes the notion of a Boolean function f : {0, 1}^{n} → {0, 1}. Any such function can be represented as a multilinear polynomial in its variables. A pseudo-Boolean constraint is an equation or inequality between pseudo-Boolean functions. A simple example is the inequality 3x_{1} + 2x_{2} + x_{3} + x_{4} ≤ 4 which has the solutions (0,0,0,0), (0,0,0,1), (0,0,1,0), (0,0,1,1), (0,1,0,0), (0,1,0,1), (0,1,1,0), (0,1,1,1), (1,0,0,0), (1,0,0,1), (1,0,1,0). Any Boolean constraint can be translated into a pseudo-Boolean constraint using the identities

¬x = 1 − x, x ∧ y = x ∗ y, x ∨ y = x + y − x ∗ y.

The following example illustrates some typical aspects of logic programming with pseudo-Boolean constraints.

Example 2.1 Suppose we want to compute the Hamming distance of two 0-1 vectors x, y ∈ {0, 1}^{n}. A naive program for solving this problem is

    hamming1([], [], 0).

hamming1([X|Xs],[Y|Ys], N) :-
      X = Y, hamming1(Xs,Ys,N).
hamming1([X|Xs],[Y|Ys], N + 1) :-
      X = 1 - Y, hamming1(Xs,Ys,N).

Here N is a real or integer variable and X, Y are 0-1 variables. If we ask the query ?- hamming1([A,B,C],[0,1,0],2), backtracking will generate the answers

A = 0, B = 0, C = 1;
A = 1, B = 1, C = 1;
A = 1, B = 0, C = 0;
No.

To avoid enumerating a possibly exponential number of 0-1 tuples we may use the program

hamming2([], [], 0).
hamming2([X|Xs], [Y|Ys], N + (X + Y - 2*X*Y)) :-
      hamming2(Xs,Ys,N).

Note that X + Y − 2 ∗ X ∗ Y evaluates to 0 if X = Y and to 1 if X ≠ Y. Linearization of the nonlinear term X ∗ Y using a new 0-1 variable Z yields

hamming3([], [], 0).
hamming3([X|Xs], [Y|Ys], N + (X + Y - 2*Z)) :-
      Z <= X, Z <= Y, X + Y <= 1 + Z,
      hamming3(Xs,Ys,N).

Here, the pseudo-Boolean constraints Z ≤ X, Z ≤ Y, X + Y ≤ 1 + Z express that Z = X ∗ Y. Now consider again the query ?- hamming3([A,B,C],[0,1,0],2). A successful derivation is

?- hamming3([A,B,C],[0,1,0],2).
?- X = A, Xs = [B,C], Y = 0, Ys = [1,0], N + (X + Y - 2*Z) = 2,
   Z <= X, Z <= Y, X + Y <= 1 + Z, hamming3([B,C],[1,0],N).
?- X = A, Xs = [B,C], Y = 0, Ys = [1,0], N + (X + Y - 2*Z) = 2,
   Z <= X, Z <= Y, X + Y <= 1 + Z,
   X1 = B, X1s = [C], Y1 = 1, Y1s = [0], N1 + (X1 + Y1 - 2*Z1) = N,
   Z1 <= X1, Z1 <= Y1, X1 + Y1 <= 1 + Z1, hamming3([C],[0],N1).
?- X = A, Xs = [B,C], Y = 0, Ys = [1,0], N + (X + Y - 2*Z) = 2,
   Z <= X, Z <= Y, X + Y <= 1 + Z,
   X1 = B, X1s = [C], Y1 = 1, Y1s = [0], N1 + (X1 + Y1 - 2*Z1) = N,
   Z1 <= X1, Z1 <= Y1, X1 + Y1 <= 1 + Z1,
   X2 = C, X2s = [], Y2 = 0, Y2s = [], N2 + (X2 + Y2 - 2*Z2) = N1,
   Z2 <= X2, Z2 <= Y2, X2 + Y2 <= 1 + Z2, hamming3([],[],N2).
?- X = A, Xs = [B,C], Y = 0, Ys = [1,0], N + (X + Y - 2*Z) = 2,
   Z <= X, Z <= Y, X + Y <= 1 + Z,
   X1 = B, X1s = [C], Y1 = 1, Y1s = [0], N1 + (X1 + Y1 - 2*Z1) = N,
   Z1 <= X1, Z1 <= Y1, X1 + Y1 <= 1 + Z1,
   X2 = C, X2s = [], Y2 = 0, Y2s = [], N2 + (X2 + Y2 - 2*Z2) = N1,
   Z2 <= X2, Z2 <= Y2, X2 + Y2 <= 1 + Z2, N2 = 0.

which can be simplified to A = 1 + B - C. This example shows how new variables and constraints are generated during program execution and how symbolic answers to a given query can be obtained.

One of the most important features of the language CLP(PB) is that it allows us to handle combinatorial optimization problems within the constraint logic programming framework [Boc93].

Example 2.2 Consider for example a knapsack problem. Suppose there is a vessel with capacity w and goods g_{i} with weight w_{i} and value v_{i} for i = 1, …, n. We introduce 0-1 variables X_{i} which indicate whether or not g_{i} is loaded on the vessel. The possible cargos not exceeding the capacity can be determined by a constraint rule involving a pseudo-Boolean constraint.

       cargo(X_{1}, . . . , X_{n}) :-

w_{1} ∗ X_{1} + ⋯ + w_{n} ∗ X_{n} ≤ w.

If we want to find a most valuable cargo, this can be done using a meta-predicate max that maximizes a pseudo-Boolean function subject to some pseudo-Boolean constraints.

       most-valuable-cargo(X_{1}, . . . , X_{n}) :-

max(v_{1}∗X_{1} + ⋯ + v_{n}∗X_{n}, cargo(X_{1}, …, X_{n})).

Other applications of CLP(PB), in particular in artificial intelligence, are described in [BB93].

2.1 Main problems

In [Boc93] we showed how Boolean unification [MN89] which is a standard approach for solving Boolean constraints can be generalized to the pseudo-Boolean case. In particular, we gave variable elimination algorithms for pseudo-Boolean unification and unconstrained pseudo-Boolean optimization. Both algorithms generalize the well-known Boolean unification algorithm of [BS87].

The aim of this paper is to present a new constraint solver for linear pseudo-Boolean constraints of the form a_{1}x_{1} + ⋯ + a_{n}x_{n} ≤ b, with a_{1}, …, a_{n}, b ∈ ZZ and 0-1 variables x_{1}, …, x_{n}.

The constraint solver has to provide solutions to the following typical problems in constraint logic programming:

Solvability: Decide whether a constraint set C has a solution.

Simplification: Simplify a constraint set C to a solved form S(C).

Entailment: Decide whether a constraint c is implied by a constraint set C.

Since in every resolution step new constraints are added to the current constraint set, the constraint solver has to be incremental.

In many applications, as is illustrated for example by the knapsack problem given before, it is not sufficient to compute an arbitrary solution of the constraint set C but one wishes to find a solution which is optimal with respect to some pseudo-Boolean function f [Boc93, BB93]. Therefore we have also the problem

Optimization: Optimize a pseudo-Boolean function f subject to a constraint set C.

The problem of optimization has recently received a lot of attention within the constraint logic programming community (see e.g. [Fag93, MT93]).

2.2 Pseudo-Boolean and finite domain constraints

Pseudo-Boolean constraints generalize Boolean constraints. At the same time, they are a special form of finite domain constraints (see for example [Mac92]). In principle, we could apply finite domain techniques to solve pseudo-Boolean constraints. Finite domain constraints have been used very successfully in constraint logic programming [vH89]. However, these methods, which are based on local consistency techniques for constraint satisfaction, cannot exploit the special structure of 0-1 problems. Another problem is that standard finite domain constraint solvers are not complete. A set of constraints may be locally consistent although it does not admit a global solution. In order to achieve completeness the values in the domains have to be enumerated by a backtracking mechanism (labeling procedure).

Our approach to solve 0-1 constraints is based on polyhedral cutting plane techniques from operations research. In general, polyhedral cutting planes are used in combination with traditional branch-and-bound, which is then called branch-and-cut. The idea, however, is to avoid branching as much as possible. The generation of polyhedral cutting planes may reduce the search space for branch-and-bound algorithms in a dramatic way. There exist non-trivial examples which could be solved even without any branching [Boy93]. For many hard combinatorial optimization problems, branch-and-cut algorithms yield the best methods currently available in order to find optimal or at least provably good solutions. The most prominent example is the traveling salesman problem [PR91, JRT92] where instances with up to 3000 cities, which roughly corresponds to 4500000 0-1 variables, could be solved in a reasonable time.

3 Solving 0-1 Constraints

When executing a constraint logic program, the main problem is to simplify a given constraint set C and to compute a solved form S(C). Our first question is how this solved form should look like. There are the following basic requirements:

• S(C) should be equivalent to C, i.e. C and S(C) should have the same set of 0-1 solutions.

• S(C) should be “simpler” than C.

• S(C) should be false if C is unsolvable.

3.1 Equality descriptions of the solution set

The most natural approach to solve a set of 0-1 constraints is to compute families of solutions like

\begin{matrix}X_{1} & X_{2} & X_{3} & X_{4} & X_{5} \\ 0 & 0 & − & − & − \\ 0 & 1 & 1 & − & − \\ 0 & 1 & 0 & 1 & − \\ 1 & 0 & 1 & − & − \end{matrix}

Logically, this corresponds to a disjunction of conjunctions of equalities. In logic programming, which is based on Horn logic, disjunction is normally provided by the possibility of defining a predicate by more than one rule. Backtracking is used to apply these rules sequentially top-down

[figure: .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; P]

Figure 1: Polyhedron P defined by six linear inequalities containing three 0-1 points

from left-to-right in order to find a solution to the given goal. Disjunction in the solved form of a constraint set would mean that we introduce an additional level of indeterminism during program execution. Backtracking would have to occur also within the constraint solving procedure. This leads to an enormous blow-up of the search space which we want to avoid.

A second approach is therefore to compute a parametric solution or a most general pseudo-Boolean unifier [Boc93]

X_{1} ≐ t_{1}[Y_{1}, …, Y_{k}] ; ⋮ ; X_{n} ≐ t_{n}[Y_{1}, …, Y_{k}],  (1)

where t_{1}, …, t_{n} are pseudo-Boolean terms containing new variables Y_{1}, …, Y_{k}. This corresponds to one of the most common approaches in Boolean constraint solving [BS87]. The advantage of this approach is that we capture all the solutions of the constraint set by a conjunctive formula which in addition can be seen as an idempotent substitution. However, practical experience already in the Boolean case has shown that these most general unifiers involve very complex pseudo-Boolean terms. Therefore, they seem to be useful only for special problem classes, for example in circuit verification [SND88].

3.2 Inequality descriptions

Instead of computing an explicit representation of the solution set using equalities we may also compute an implicit representation based on inequalities. As we will see, this is particularly useful in the context of optimization because it allows us to use powerful methods from operations research.

From a mathematical point of view, a set C of linear 0-1 constraints is the same as a system of linear inequalities in 0-1 variables

\begin{aligned}a_{11}x_{1} & + ⋯ + & a_{1n}x_{n} & ≤ b_{1} \\ ⋮ & & ⋮ & ⋮ \\ a_{m1}x_{1} & + ⋯ + & a_{mn}x_{n} & ≤ b_{m} \end{aligned} ⇔ Ax ≤ b,  (2)

with A ∈ ZZ^{m×n}, x ∈ {0, 1}^{n} and b ∈ ZZ^{m}. Such a system defines a possibly empty set S of 0-1 points in IR^{n}. If we drop the condition x ∈ {0, 1}^{n} then the system of linear 0-1 constraints (2) becomes a system of linear arithmetic constraints over the real numbers, which defines a polyhedron

[figure: 0 1; _{0  1}; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; x_{2} = \frac{1}{2}; 2x_{1} + 2x_{2} = 3; 2x_{2} − 2x_{1} = 1; x_{2} = 0]

Figure 2: Linear inequality descriptions of S = {(0, 0), (1, 0)}

P in IR^{n} (see Fig. 1). The set of 0-1 solutions S = P ∩ {0, 1}^{n} corresponds to the set of 0-1 points lying within P.

There is an important difference between linear inequality descriptions of the real polyhedron P and the 0-1 set S. Let us call a system Ax ≤ b over IR^{n} (resp. {0, 1}^{n}) irredundant if no constraint αx ≤ β can be removed without changing the solution set P (resp. S). For a full-dimensional polyhedron P there is up to multiplication of inequalities by a positive real number a unique representation of P by an irredundant system of inequalities Ax ≤ b. The inequalities in Ax ≤ b are in a 1-1 correspondence with the facets of P [Sch86]. Remember that an inequality defines a facet of P if it is satisfied by all points in P and if moreover there are n affinely independent points in P for which it is satisfied at equality.

For a 0-1 set S, however, there are many different representations by irredundant systems Ax ≤ b. For example, the irredundant constraint sets {x_{2} ≤ 0}, {2x_{2} ≤ 1}, and {2x_{1} + 2x_{2} ≤ 3, 2x_{2} − 2x_{1} ≤ 1} all define the same 0-1 set S = {(0, 0), (1, 0)} ⊆ IR^{2} (see Fig. 2).

If we use inequalities then the solved form of a constraint system C : Ax ≤ b is again a system of inequalities C̄ : Āx ≤ b̄. Since we want to simplify our problem, C̄ should be “simpler” than C. However, it is not clear what this should mean. There are many possibilities to compare linear inequality descriptions Ax ≤ b of a 0-1 set S. In particular we may consider

• the size of the system Ax ≤ b depending on the number of inequalities and the size of their coefficients.

• the strength of the inequalities in the system Ax ≤ b.

3.3 Size of the representation

Given a linear inequality in 0-1 variables, there are many other inequalities having the same set S of 0-1 solutions. The set S^{∗} of all (α, β) ∈ IR^{n+1} such that αx ≤ β has the 0-1 solution set S defines a polyhedron in IR^{n+1}. To find an equivalent inequality with minimal coefficients one can solve a linear optimization problem as described in [BHW74].

Concerning the size of the coefficients, a recent result of Schmitt [Sch92] (improving a classical theorem from threshold logic [Mur71]) says that any linear 0-1 inequality αx ≤ β, (α, β) ∈ IR^{n+1}, is equivalent to a 0-1 inequality γ_{1}x_{1} + ⋯ + γ_{n}x_{n} ≤ δ with integer coefficients γ_{1}, …, γ_{n}, δ such that

|γ_{i}| ≤ 2^{−n}(n + 1)^{(n+1)/2} and |δ| ≤ 2^{−(n+1)}(n + 1)^{(n+3)/2} + 1/2.

By a result of Jeroslow [Jer75], at most 2^{n−1} linear 0-1 inequalities are needed to define a 0-1 set S ⊆ {0, 1}^{n}. For any k in the range 1 ≤ k ≤ 2^{n−1}, there exists S ⊆ {0, 1}^{n}, such that at least k linear 0-1 inequalities are needed to define S. Lipkin [Lip87] showed that in order to define a set S ⊆ {0, 1}^{n} of cardinality m, at most m linear 0-1 inequalities are needed. The problem of deciding whether an arbitrary 0-1 set S can be defined by a single linear 0-1 inequality is NP-complete [PS85].

3.4 Strength of the representation

Linear inequality descriptions Ax ≤ b of a 0-1 set S can also be compared with respect to the strength of the inequalities that are used. When comparing the strength of linear inequalities we have to specify in which kind of solutions we are interested.

Definition 3.1 Let Q, R ⊆ IR^{n}. An inequality αx ≤ β is valid for Q iff αx_{0} ≤ β, for all x_{0} ∈ Q. αx ≤ β is stronger than γx ≤ δ with respect to R iff {x ∈ R | αx ≤ β} ⊆ {x ∈ R | γx ≤ δ}. The inequality is strictly stronger iff the inclusion is strict.

If {x ∈ IR_{+}^{n} | αx ≤ β} ≠ ∅, then αx ≤ β is stronger than γx ≤ δ with respect to IR_{+}^{n} iff there exists λ ≥ 0 such that λα_{i} ≥ γ_{i}, for i = 1, …, n and λβ ≤ δ.

A facet-defining inequality of a polyhedron P ⊆ IR^{n} is a strongest valid inequality for P with respect to IR^{n}. A strongest valid inequality for a 0-1 set S with respect to {0, 1}^{n} is called a prime inequality [Hoo92]. Note that these two notions of strongest valid inequality are not equivalent. A facet-defining inequality of the convex hull conv(S) of S need not be a prime inequality for S and vice versa.

Example 3.2 Let S = {(1, 0, 0), (1, 0, 1), (0, 1, 1), (1, 1, 0), (1, 1, 1)}. The inequality x_{1} + x_{2} ≥ 1 defines a facet of conv(S) but it is not prime. The inequality 2x_{1} + x_{2} + x_{3} ≥ 2, which is valid for S, is stronger than x_{1} + x_{2} ≥ 1 with respect to {0, 1}^{3} because it is not satisfied by the point (0, 1, 0). However, 2x_{1} + x_{2} + x_{3} ≥ 2 does not define a facet of conv(S).

The notion of prime inequality can also be defined relative to a given class T of linear 0-1 inequalities. A prime inequality for S relative to T is a strongest valid inequality for S in the class T with respect to {0, 1}^{n}.

3.5 Defining a solved form

Unfortunately, the various possibilities that we have considered so far to compare two constraint sets C_{1} and C_{2} are not compatible.

Example 3.3 The constraint sets

C_{1} = {3x_{1} + 2x_{2} + x_{3} + x_{4} + x_{5} ≥ 5}  (3)

and

\begin{matrix}C_{2} = \{ x_{1} + x_{2} ≥ 1, x_{1} + x_{3} ≥ 1, x_{1} + x_{4} ≥ 1, x_{1} + x_{5} ≥ 1, \\ x_{1} + x_{2} + x_{3} + x_{4} ≥ 2, x_{1} + x_{2} + x_{3} + x_{5} ≥ 2, x_{1} + x_{2} + x_{4} + x_{5} ≥ 2 \} \end{matrix}  (4)

have the same 0-1 solution set S.

The first description contains only one inequality, but some coefficients of the left-hand side are different from 0 and 1. The second description consists of seven extended clauses, that is inequalities of the form L_{1} + ⋯ + L_{m} ≥ k, which express that at least k out of m literals L_{1}, …, L_{m} have to be true [Hoo92].

In [Bar93a, Bar93b], a constraint solver for 0-1 constraints is presented that computes for a given linear 0-1 inequality an equivalent set of prime extended clauses. Given a set of prime extended clauses π(S) for a 0-1 set S, testing solvability and entailment becomes very easy. The set π(S), however, may be very large. The members of π(S) are strongest valid inequalities for S with respect to {0, 1}^{n} (relative to the class T of extended clauses), but they need not be strongest valid inequalities for the convex hull conv(S) with respect to IR^{n}.

Example 3.4 The extended clause {y_{1} + y_{2} + y_{3} + y_{4} ≥ 2} is equivalent to the set of classical clauses {y_{1} + y_{2} + y_{3} ≥ 1, y_{1} + y_{2} + y_{4} ≥ 1, y_{1} + y_{3} + y_{4} ≥ 1, y_{2} + y_{3} + y_{4} ≥ 1}. Therefore another description of S by classical clauses would be

\begin{matrix}C_{3} = \{ x_{1} + x_{2} ≥ 1, x_{1} + x_{3} ≥ 1, x_{1} + x_{4} ≥ 1, x_{1} + x_{5} ≥ 1, \\ x_{2} + x_{3} + x_{4} ≥ 1, x_{2} + x_{3} + x_{5} ≥ 1, x_{2} + x_{4} + x_{5} ≥ 1 \}. \end{matrix}  (5)

While all these representations define the same 0-1 set S, their strength is quite different. The set of all nontrivial facets of conv(S) is

\begin{matrix}C_{4} = \{ x_{1} + x_{2} ≥ 1, x_{1} + x_{3} ≥ 1, x_{1} + x_{4} ≥ 1, x_{1} + x_{5} ≥ 1, \\ 2x_{1} + x_{2} + x_{3} + x_{4} ≥ 3, 2x_{1} + x_{2} + x_{3} + x_{5} ≥ 3, 2x_{1} + x_{2} + x_{4} + x_{5} ≥ 3, \\ 3x_{1} + 2x_{2} + x_{3} + x_{4} + x_{5} ≥ 5 \}. \end{matrix}  (6)

For example, the facet-defining inequality 2x_{1} + x_{2} + x_{3} + x_{4} ≥ 3 is strictly stronger than the prime extended clause x_{1} +x_{2} +x_{3} +x_{4} ≥ 2, which again is strictly stronger than than the classical clause x_{2}+x_{3}+x_{4} ≥ 1 (with respect to both {0, 1}^{n} and [0, 1]^{n}). The inequality 3x_{1}+2x_{2}+x_{3}+x_{4}+x_{5} ≥ 5 is strictly stronger than 2x_{1} + x_{2} + x_{3} + x_{4} ≥ 3 with respect to {0, 1}^{n}, but not with respect to [0, 1]^{n}. Note that a set C of facet-defining inequalities for conv(S) need not contain all facets of conv(S) in order to define the 0-1 set S, consider for example C = {3x_{1} + 2x_{2} + x_{3} + x_{4} + x_{5} ≥ 5}.

Given all these possibilities, how should we define the solved form? In order to answer this question we have to take into account one more point that we have not considered so far. Since we are interested not only in constraint solving but also in constrained optimization we need a solved form that supports optimization.

One of the most powerful techniques to obtain provably good solutions of combinatorial optimization problems is linear optimization combined with the generation of polyhedral cutting planes [HP85]. A discrete optimization problem over the 0-1 set S

[figure: 0 1; _{0  1}; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; Cutting Planes; Fractional Vertex; conv(S)]

Figure 3: Approximating the convex hull of S by cutting planes

Maximize z = cx subject to x ∈ S = {x ∈ {0, 1}^{n} | Ax ≤ b}

is equivalent to the linear optimization problem

Maximize z = cx subject to x ∈ conv(S) ⊆ IR^{n}

over the convex hull conv(S) of S. This means that 0-1 optimization problems can be solved by linear optimization techniques provided that a linear inequality description of conv(S) is known.

First we should point out that it is not necessary to have a complete description of conv(S) which might be very complex [KP82]. It is enough to have a sufficiently good approximation of conv(S), which can be computed by the generation of cutting planes. A first approximation P of conv(S) is obtained by the linear relaxation Ax ≤ b, 0 ≤ x ≤ 1 of the original problem. Then new inequalities are added which are satisfied by all points in S but which cut off at least one fractional vertex of P. These are called cutting planes. This is repeated until a 0-1 vertex is obtained, which then automatically belongs to S (see Fig. 3).

It is crucial for this approach that the cutting planes which are generated are strong with respect to IR^{n} (cf. Definition 3.1). In the best case, they should define facets of conv(S) or at least faces of sufficiently high dimension. Traditional Chvàtal-Gomory-Cuts [Gom58] do not have this property. They converge much too slowly in order to be practically useful. In order to compute strong cutting planes with a reasonable effort, advanced techniques from polyhedral combinatorics are necessary, which will be described in the next section. Our paradigm for solving 0-1 constraints is therefore the following:

A constraint set C is solved by computing polyhedral cutting planes for the convex hull conv(S), where S denotes the set of 0-1 solutions of C.

This is also reflected in the next definition.

Definition 3.5 Given two constraint sets C : Ax ≤ b and C′ : A′x ≤ b′ with the same set of 0-1 solutions S, we say that C is simpler than C′ iff {x ∈ IR^{n} | Ax ≤ b} ⊆ {x ∈ IR^{n} | A′x ≤ b′}.

The ideal solved form of C is a constraint set C̄ : Āx ≤ b̄ with conv(S) = {x ∈ IR^{n} | Āx ≤ b̄} such that there is a 1-1 correspondence between the inequalities in Āx ≤ b̄ and the facets of conv(S).

In practice, this ideal solved form cannot be computed, because an exponential number of inequalities may be needed. However, the idea is not to compute the ideal solved form. On the contrary, we want to avoid the exponential blow-up as much as possible. Therefore constraint solving is done in a lazy way. We compute only as many cutting planes as are needed in order to answer the basic questions presented in Section 2.1. The solved form that is actually computed is defined implicitly by the cut generation process.

4 Computing the Solved Form

In the previous section, we have defined a solved form for a given set of 0-1 constraints. The main question now is how to compute this solved form. In other words the problem is to find strong cutting planes for a given set of 0-1 constraints. For special problems (knapsack, set covering, traveling salesman etc.) strong valid inequalities have been found by analyzing the specific problem structure. For general 0-1 problems, strong valid inequalities are very hard to obtain. An early strong cutting plane approach for general 0-1 problems was presented in [CJP83]. The cutting planes used there are facet-defining inequalities for the knapsack polytope generated by an individual 0-1 constraint. This approach has been particularly successful in the case of large-scale 0-1 problems with a sparse coefficient matrix and with no apparent special structure. In this case, the constraints do not interact very much, so that one can expect that strong valid inequalities for the knapsack polytope of an individual 0-1 constraint will also be strong for the 0-1 polytope of the full problem. The mixed integer optimizer MINTO [SN93] is based on these ideas. Another interesting recent approach for solving hard 0-1 programs, which uses knapsack and enumeration cutting planes combined with preprocessing, is described in [Boy93].

In our context, however, the most promising way to find strong cutting planes for general 0-1 problems, seems to be the new lift-and-project method for mixed 0-1 optimization due to [BCC93b, BCC93a]. This method not only has very nice theoretical properties, such as finite convergence. It has also been applied very successfully in practice. The approach was able to solve several previously unsolved problems and in many cases seems to obtain better results than other procedures available like CPLEXMIP 2.0 or OSL 2.0 [Cer93]. In several cases, the procedure even outperformed specialized algorithms on the class of problems for which these algorithms were designed. Extensive empirical results documenting this can be found in [BCC93b, BCC93a, Cer93].

The starting point of the lift-and-project method is a sequential convexification theorem. Suppose

P = {x ∈ IR^{n} | Ax ≥ b, 0 ≤ x ≤ 1} =^{def} {x ∈ IR^{n} | Ãx ≥ b̃},  (7)

with A ∈ IR^{m×n}, b ∈ IR^{m}, is a polyhedron in IR^{n}. If

R_{j}(P) = conv(P ∩ {x ∈ IR^{n} | x_{j} ∈ {0, 1}}), for j = 1, …, n,  (8)

is the convex hull of those points in P for which x_{j} = 0 or x_{j} = 1, then

R_{1}(R_{2}(… R_{n}(P))) = conv(S),  (9)

where as usual S = P ∩ {0, 1}^{n}.

The idea of [BCC93b, BCC93a] is to use facets of R_{j}(P) as strong cutting planes for S. By lifting the problem into a higher-dimensional space one can show that

R_{j}(P) = {x ∈ IR^{n} | αx ≥ β for all (α, β) ∈ R_{j}^{∗}(P)}

where R_{j}^{∗}(P) is the set of those (α, β) ∈ IR^{n+1} for which there exist vectors u, v ∈ IR^{m+2n} and u_{0}, v_{0} ∈ IR satisfying

\begin{aligned}α & −uÃ & −u_{0}e_{j} & & & = 0 \\ α & & & −vÃ & −v_{0}e_{j} & = 0 \\ & ub̃ & & & & = β \\ & & & vb̃ & +v_{0} & = β \\ & & & & u, v & ≥ 0, \end{aligned}  (10)

where e_{j} is the j-th unit vector in IR^{n}.

If P is full-dimensional, P ∩ {x | x_{j} = 0} ≠ ∅ and P ∩ {x | x_{j} = 1} ≠ ∅, then for any constant β ≠ 0, αx ≥ β defines a facet of R_{j}(P) iff (α, β) is an extreme ray of R_{j}^{∗}(P). To compute such extreme rays one can solve a linear program of the form

max{aα + bβ | (α, β) ∈ R_{j}^{∗}(P) ∩ T }  (11)

where (a, b) ∈ IR^{n+1} is a vector that determines the direction of the cut and T a normalization set that truncates the cone R_{j}^{∗}(P). This linear program has roughly twice the size of the current problem. Several choices of (a, b) and T are possible. Usually, one uses (a, b) = (−x, 1), where x is the fractional vertex of P which should be cut off, and T = {(α, β) | −1 ≤ α_{i} ≤ 1, i = 1, …, n} or T = {(α, β) | ∑_{i=1}^{n} |α_{i}| ≤ 1}. In some cases, one can also choose the truncation β = 1 or β = −1.

Example 4.1 Consider the set of 0-1 constraints

C = {−2x_{1} − 2x_{2} ≥ −3, 2x_{1} − 2x_{2} ≥ −1}.

The linear relaxation P is given by the system of linear inequalities Ãx ≥ b̃, where

Ã^{T} = ( \begin{matrix}−2 & 2 & 1 & 0 & −1 & 0 \\ −2 & −2 & 0 & 1 & 0 & −1 \end{matrix} )

and

b̃^{T} = ( −3 −1 0 0 −1 −1 ) .

To cut off the fractional vertex (\frac{1}{2}, 1) of P we solve the linear program

Maximize −\frac{1}{2}α_{1} − α_{2} + β subject to
α_{1}  +2u_{1} −2u_{2} −u_{3}  +u_{5}  −u_{0} = 0
α_{2} +2u_{1} +2u_{2}  −u_{4}  +u_{6}  = 0
α_{1}  +2v_{1} −2v_{2} −v_{3}  +v_{5}  −v_{0} = 0
α_{2} +2v_{1} +2v_{2}  −v_{4}  +v_{6}  = 0
−3u_{1} −u_{2}  −u_{5} −u_{6}  = β
−3v_{1} −v_{2}  −v_{5} −v_{6} +v_{0} = β
−1 ≤ α_{1}, α_{2} ≤ 1
u_{1}, u_{2}, u_{3}, u_{4}, u_{5}, u_{6}, v_{1}, v_{2}, v_{3}, v_{4}, v_{5}, v_{6} ≥ 0.

0 1 _{0  1}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.} P  0 1 _{0  1}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.} R_{1}(P)  0 1 _{0  1}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.} R_{2}(P)  0 1 _{0  1} R_{1}(R_{2}(P))

Figure 4: Sequential convexification for P = {x ∈ [0, 1]^{2} | −2x_{1} − 2x_{2} ≥ −3, 2x_{1} − 2x_{2} ≥ −1}

We get the optimal solution α_{1} = 0, α_{2} = −1, β = −\frac{1}{2}, which corresponds to the facet x_{2} ≤ \frac{1}{2} of R_{1}(P). In the same way, we can compute the facets x_{1} + \frac{1}{2}x_{2} ≤ 1 and x_{1} − \frac{1}{2}x_{2} ≥ 0 of R_{2}(P), which cut off the vertices (1, \frac{1}{2}) and (0, \frac{1}{2}) respectively (see Fig. 4). In this example, we really compute facets of R_{j}(P). Note however that, due to the truncation T, this need not always be the case.

We give now our strong cutting plane algorithm for solving 0-1 constraints. Implicitly, it computes a solved form of a constraint set C.

Strong Cutting Plane Algorithm for Solving 0-1 Constraints

Initialization: Let t := 1; C^{1} := C = {Ax ≥ b, 0 ≤ x ≤ 1},

Iteration t: 1. Solution of the linear relaxation: Optimize a linear function g^{t}

over the relaxation P^{t} = {x ∈ IR^{n} | x is a solution of C^{t}}.

2. Infeasibility test: If P^{t} = ∅, stop, C is unsolvable.

Otherwise let the vertex x^{t} ∈ P^{t} be an optimal solution.

3. Feasible 0-1 solution: If x_{j}^{t} ∈ {0, 1}, for j = 1, …, n, stop, x^{t} is a feasible 0-1 solution of C, C^{t} is the solved form of C.

4. Cut generation: For j ∈ {1, …, n} with 0 < x_{j}^{t} < 1 generate a j-cut α^{j}x ≥

β^{j} by solving

max{β − αx^{t} | (α, β) ∈ R_{j}^{∗}(P^{t}) ∩ T }.

Define C^{t+1} by adding the j-cuts α^{j}x ≥ β^{j} to the constraint set C^{t} and simplify C^{t} considered as a set of linear arithmetic constraints.

5. Let t := t + 1 and goto 1.

Example 4.2 Consider again the linear 0-1 inequality

3x_{1} + 2x_{2} + x_{3} + x_{4} + x_{5} ≥ 5.

For most objective functions, linear optimization over the corresponding linear relaxation yields immediately a 0-1 solution. Minimizing the objective function x_{1} + x_{4} + x_{5} yields the fractional solution x_{1} = 2/3, x_{2} = x_{3} = 1, x_{4} = x_{5} = 0. Now, the cutting plane procedure generates the 1-cut x_{1} + x_{4} + x_{5} ≥ 1. Adding this cut to the linear relaxation and re-optimizing yields the optimal 0-1 solution x_{1} = x_{2} = x_{3} = 1, x_{4} = x_{5} = 0.

For a specialized version of this algorithm we can prove the following correctness and completeness theorem (see Appendix A).

Theorem 4.3 Given a constraint set C : {Ax ≥ b, x ∈ {0, 1}} the specialized strong cutting plane algorithm finds a feasible 0-1 solution if one exists or detects that C is unsolvable.

The same algorithm can also be used for optimization and entailment. If we want to compute an optimal solution to the linear 0-1 optimization problem

Minimize g(x) subject to the constraints Ax ≥ b, x ∈ {0, 1}^{n}.

we choose g^{t} = g, for all t = 1, 2, . . .. If the algorithm stops with a solution x^{∗} ∈ {0, 1}^{n}, then this solution is optimal. In order to check whether a constraint cx ≥ d is entailed by a constraint set Ax ≥ b, we can minimize the objective function cx subject to Ax ≥ b, x ∈ {0, 1}^{n}. As soon as we find an optimal solution x^{t} for the linear relaxation P^{t} such that cx^{t} ≥ d, the constraint is entailed. If cx^{∗} < d, for an optimal solution x^{∗} of the 0-1 problem, the constraint is not entailed.

We close this section with a remark on incrementality. Suppose we have computed a solved form for the constraint set C and a new constraint has to be added. If we have used the simplex algorithm to solve the linear relaxation P then there is a straightforward way to use the current optimal solution to solve the new problem. If the new constraint is satisfied by the current optimal solution, nothing has to be done. If the constraint is not satisfied, it can be converted to an equality by the addition of a nonnegative slack variable and added to the constraint set. The optimal basis for the original problem and the new slack variable provide a basis for the expanded problem. This new basis is dual feasible and primal feasible in all but the last row. In order to reoptimize, we can therefore use the dual simplex algorithm which was designed to deal with just this kind of situation. Since the current solution is “nearly” primal feasible, it is likely that only a few iterations will be required [NW88].

5 Branch and Cut

It is a general experience with cutting plane algorithms that the effect of the cutting planes on the objective function value is more significant at the beginning than at the end [Cer93]. In order to move away from the current optimal solution when the cuts become shallow, the cutting plane algorithm can be combined with classical branch-and bound. The idea of branch-and-bound is to divide the set of feasible solutions into subsets, to compute bounds for the objective function on these subsets, and to use these bounds to discard some of the subsets from further consideration. In the case of 0-1 optimization, the splitting of the set of feasible solutions is usually done by fixing a variable to the values 0 and 1 (for more details see for example [NW88]).

Example 5.1 Consider the linear 0-1 optimization problem

Maximize z = x_{1} + x_{2} + x_{3} subject to
x ∈ S = {x ∈ {0, 1}^{3} | x_{1} − x_{2} ≥ 0, x_{1} − x_{3} ≥ 0, x_{1} + x_{2} + x_{3} ≥ 1}.

The branch-and-bound tree is given in Fig. 5. It contains only 7 instead of possibly 15 nodes.

The linear relaxation of S^{0} is infeasible. The sets S^{110} resp. S^{111} contain only one point with value 2 resp. 3. For S^{10} we get the upper bound 2 which is smaller than 3. Therefore this node need not be expanded and (1, 1, 1) is the optimal solution with optimal value 3.

[figure: \begin{aligned}& S \\ S_{0} & & S_{1} \\ & S_{10} & & S_{11} \\ & & S_{110} & & S_{111} \end{aligned}; x_{1}=1; x_{1}=0; x_{2}=1; x_{2}=0; x_{3}=1; x_{3}=0]

Figure 5: Branch-and-bound tree

Branch-and-bound is the standard technique used in finite domain constraint solvers in case an optimal solution of the given constraint set has to be found. It was also very popular in operations research until it became clear that bounds computed by solving the linear relaxation could be considerably improved by generating suitable cutting planes. Better bounds in turn reduce the size of the branch-and-bound search tree. In a first period, cutting planes were generated only at the root node of the branch-and-bound tree in order to improve the initial formulation given by the linear relaxation.

This had already remarkable effects as is illustrated for example by the standard benchmark p0033 of the mixed integer programming library MIPLIB [BBI92]. This is a linear 0-1 minimization problem consisting of 33 0-1 variables and 15 constraints. If standard branch-and-bound is applied without adding cuts, the best solution found after 1000 nodes has value 3095, and the tree still contains 163 active nodes. If branch-and-bound is applied after generating 20 cuts (in 6 iterations), then a solution of value 3095 is found at node 17, and an optimal solution of value 3089 is found at node 65. Optimality is proved at node 77 [NW88].

In a second step, cutting planes were used not only at the root node of the branch-and-bound tree but also for the rest of the tree [PR91]. The crucial point here is that the cutting planes that are generated are not only valid for the descendants of the current node but for the whole tree. This means that one has to compute coefficients for the variables that have been fixed before. Padberg and Rinaldi called their method, which they developed in the context of solving large instances of the traveling-salesman-problem, branch-and-cut.

The cutting planes generated by the lift-and-project method have this crucial property. They can be lifted from one node in the branch-and-bound tree to all other nodes (see Appendix B). Therefore, our strong cutting plane algorithm for 0-1 constraint solving can be embedded into a branch-and-cut procedure, which in many cases converges much faster.

Here is a sketch of a full branch-and-cut procedure [BCC93b, PR91, JRT92]. For F_{0}, F_{1} ⊆ {1, …, n}, F_{0} ∩ F_{1} = ∅ let LP (z, C, F_{0}, F_{1}) denote the linear optimization problem

Minimize z = cx subject to Ax ≥ b, 0 ≤ x ≤ 1, x_{i} = 0, for i ∈ F_{0}, x_{i} = 1, for i ∈ F_{1}.

Branch-and-Cut Procedure

1. Initialization: Let L = {(∅, ∅)}, C = {Ax ≥ b, 0 ≤ x ≤ 1}, UB = ∞.

2. Node Selection: If L = ∅, then stop.

Otherwise choose an ordered pair (F_{0}, F_{1}) and remove it from L.

3. Lower Bound: Solve the linear optimization problem LP (z, C, F_{0}, F_{1}). If the problem is infeasible, goto Step 2, otherwise let x̄ denote its optimal solution. If cx̄ ≥ UB goto Step 2. If x̄ is integer let x^{∗} = x̄, UB = cx̄ and goto Step 2.

4. Branching-Cutting-Decision: Should cutting planes being generated? If yes, goto Step 5, else goto Step 6.

5. Cut Generation: Generate lift-and-project cutting planes αx ≥ β violated by x̄. Lift the cuts so that they are valid for the whole branch-and-cut tree. Add the resulting cuts to C and goto Step 3.

6. Branching: Pick an index j ∈ {1, …, n} such that 0 < x̄_{j} < 1.

Generate the subproblems corresponding to (F_{0} ∪ {j}, F_{1}) and (F_{0}, F_{1} ∪ {j}) and add them to L. Goto Step 2.

When the algorithm stops, the problem is either infeasible or x^{∗} is an optimal solution. C is the solved form of the constraint set Ax ≥ b. Note that in spite of branching the solved form does not involve disjunction. This important property is obtained by lifting the cuts.

Several other improvements are possible, which we mention only briefly. First of all, we should apply the various preprocessing techniques for 0-1 programs which are described in the literature [HP91]. There is a computationally inexpensive method of strengthening the cuts computed by the lift-and-project method which also improves convergence. Finally, in an actual implementation of the branch-and-cut procedure various choices have to be made. For example, we have to decide which normalization T should be chosen, how many cuts should be generated in one iteration, when a branching step should be performed etc.

6 Conclusion and Further Research

In this paper we have presented a new approach for 0-1 constraint solving based on cutting plane techniques from combinatorial optimization. The generation of strong cutting planes may dramatically reduce the search tree of classical branch-and-bound algorithms. It thus provides an interesting alternative to the finite domain techniques used in existing constraint logic programming systems.

When solving linear 0-1 constraints by cutting plane techniques, we have to use linear arithmetic constraints and linear optimization. A natural extension of our approach would be to use linear arithmetic already from the beginning. This leads to a new kind of constraints, mixed 0-1 constraints

∑_{i∈I} a_{i}x_{i} + ∑_{j∈J} b_{j}y_{j} ≤ c,

with real variables x_{i} and 0-1 variables y_{j}.

Mixed 0-1 constraints are particularly interesting because they integrate two of the most important domains in constraint logic programming, Boolean algebra and linear arithmetic. The strong cutting plane method presented in this paper works also for the mixed 0-1 case. Therefore this approach could also provide the basis for a constraint logic programming language for mixed 0-1 constraints.

References

[ASS^{+}88] A. Aiba, K. Sakai, Y. Sato, D.J. Kawley, and R. Hasegawa. Constraint logic programming language CAL. In Fifth Generation Computer Systems, Tokyo, 1988. Springer, 1988.

[Bar93a] P. Barth. A complete symbolic 0-1 constraint solver. In 3rd Workshop on Constraint Logic Programming, WCLP’93, Marseille, March 1993.

[Bar93b] P. Barth. Linear 0-1 inequalities and extended clauses. In Logic Programming and Automated Reasoning, LPAR’93, St. Petersburg, Springer, LNCS 698, 1993.

[BB93] P. Barth and A. Bockmayr. Solving 0-1 problems in CLP(PB). In Proc. 9th Conf. Artificial Intelligence for Applications CAIA, Orlando, Florida, 263 - 269. IEEE, 1993.

[BBI92] R. E. Bixby, E. A. Boyd, and R. Indovina. MIPLIB: A test set for mixed integer programming problems. SIAM News 25, page 16, 1992.

[BCC93a] E. Balas, S. Ceria, and G. Cornuéjols. A lift-and-project cutting plane algorithm for mixed 0-1 programs. Mathematical Programming, 58:295 – 324, 1993.

[BCC93b] E. Balas, S. Ceria, and G. Cornuéjols. Solving mixed 0-1 programs by a lift-and-project method. In Symposium on Discrete Algorithms SODA, Austin, Texas. ACM - SIAM, 1993.

[BHW74] G. H. Bradley, P. L. Hammer, and L. Wolsey. Coefficient reduction for inequalities in 0-1 variables. Mathematical Programming, 7:263 –282, 1974.

[Bla80] C. E. Blair. Facial disjunctive programs and sequences of cutting planes. Discrete Applied Mathematics, 2:173 – 179, 1980.

[Boc93] A. Bockmayr. Logic programming with pseudo-Boolean constraints. In F. Benhamou and A. Colmerauer, editors, Constraint Logic Programming - Selected Research, chapter 18, pages 327 – 350. MIT Press, 1993.

[Boy93] E. A. Boyd. Solving integer programs with Fenchel cutting planes and preprocessing. In G. Rinaldi and L. Wolsey, editors, Integer Programming and Combinatorial Optimization IPCO’93, Erice, 1993.

[BS87] W. Büttner and H. Simonis. Embedding Boolean expressions in logic programming. Journal of Symbolic Computation, 4(2):191–205, 1987.

[Cer93] S. Ceria. Lift-and-project methods for mixed 0-1 programs. PhD thesis, GSIA, Carnegie Mellon University, 1993.

[CJP83] H. Crowder, E. J. Johnson, and M. Padberg. Solving large-scale 0-1 linear programming problems. Operations Research, 31(5):803–834, 1983.

[Col87] A. Colmerauer. Introduction to PROLOG III. In 4th Annual ESPRIT Conference, Bruxelles. North Holland, 1987.

[DvHS^{+}88] M. Dincbas, P. van Hentenryck, H. Simonis, A. Aggoun, and T. Graf. The constraint logic programming language CHIP. In Fifth Generation Computer Systems, Tokyo, 1988. Springer, 1988.

[Fag93] F. Fages. On the semantics of optimization predicates in CLP languages. In Principles and Practice of Constraint Programming PPCP’93, Newport, RI, 1993.

[Gom58] R. E. Gomory. Outline of an algorithm for integer solutions to linear programs. Bull. AMS, 64:275 – 278, 1958.

[Hoo92] J. N. Hooker. Generalized resolution for 0-1 linear inequalities. Annals of Mathematics and Artificial Intelligence, 6:271–286, 1992.

[HP85] K. Hoffman and M. Padberg. LP-based combinatorial problem solving. Annals of Operations Research, 4:145 – 194, 1985.

[HP91] K. Hoffman and M. Padberg. Improving LP-representations of zero-one linear programs for branch-and-cut. ORSA Journal on Computing, 3(2):121 – 134, 1991.

[HR68] P.L. Hammer and S. Rudeanu. Boolean Methods in Operations Research and Related Areas. Springer, 1968.

[Jer75] R. G. Jeroslow. On defining sets of vertices of the hypercube by linear inequalities. Discrete Mathematics, 11:119 – 124, 1975.

[Jer80] R. G. Jeroslow. A cutting-plane game for facial disjunctive programs. SIAM J. Control and Optimization, 18(3):264 – 281, 1980.

[JL87] J. Jaffar and J.-L. Lassez. Constraint logic programming. In Proc. 14th ACM Symp. Principles of Programming Languages, Munich, 1987.

[JM94] J. Jaffar and M. J. Maher. Constraint logic programming: A survey. Journal of Logic Programming, 1994. (to appear).

[JRT92] M. Jünger, G. Reinelt, and S. Thienel. Provably good solutions for the traveling salesman problem. Preprint 92-31, Interdisziplinäres Zentrum für wissenschaftliches Rechnen der Univ. Heidelberg, 1992.

[KP82] R. M. Karp and C. H. Papadimitriou. On linear characterizations of combinatorial optimization problems. SIAM J. Comput., 11(4):620 – 632, 1982.

[Lip87] L. I. Lipkin. Representation of boolean functions with a predetermined number of zeros by systems of linear inequalities. U.S.S.R. Comput. Maths. Math. Phys., 27(3):204 – 206, 1987.

[Mac92] A. K. Mackworth. Constraint satisfaction. In S.C. Shapiro, editor, Encyclopedia of artificial intelligence, volume 1, pages 285–293. Wiley, 1992.

[MN89] U. Martin and T. Nipkow. Boolean unification - the story so far. Journal of Symbolic Computation, 7:275–293, 1989.

[MT93] K. McAloon and C. Tretkoff. 2lp: Linear programming and logic programming. In Principles and Practice of Constraint Programming PPCP’93, Newport, RI, 1993.

[Mur71] S. Muroga. Threshold Logic and Its Applications. Wiley-Interscience, 1971.

[NW88] G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial Optimization. John Wiley, 1988.

[PR91] M. Padberg and G. Rinaldi. A branch-and-cut algorithm for the resolution of largescale symmetric traveling salesman problems. SIAM Review, 33(1):60 –100, 1991.

[PS85] U. N. Peled and B. Simeone. Polynomial-time algorithms for regular set-covering and threshold synthesis. Discrete Applied Mathematics, 12:57 – 69, 1985.

[Sch86] A. Schrijver. Theory of Linear and Integer Programming. John Wiley, 1986.

[Sch92] M. Schmitt. A slightly improved upper bound on the size of weights sufficient to represent any linearly separable Boolean function. Ulmer-Informatik-Bericht 92-10, Univ. Ulm, November 1992.

[SN93] M. W. P. Savelsbergh and G. L. Nemhauser. Functional description of MINTO, a mixed integer optimizer, version 1.5. Technical report, Computational Optimization Center, Georgia Institute of Technology, November 1993.

[SND88] H. Simonis, H. N. Nguyen, and M. Dincbas. Verification of digital circuits using CHIP. In Proc. IFIP WG 10.2 Intern. Conf. Fusion of Hardware Design and Verification, Glasgow, 1988.

[vH89] P. van Hentenryck. Constraint satisfaction in logic programming. MIT Press, 1989.

A Correctness and Completeness of the Specialized Cutting Plane Algorithm

In our strong cutting plane algorithm the current polyhedron P^{t} is defined by the original constraint set C = {Ax ≥ b, 0 ≤ x ≤ 1} and a set of cuts C^{t} = ⋃_{j=1}^{n} C_{j}^{t}, where C_{j}^{t} is the set of j-cuts which have been generated so far. If P_{j}^{t} is the polyhedron defined by C ∪ ⋃_{i=1}^{j} C_{i}^{t}, then P_{0}^{t} = P, P_{n}^{t} = P^{t} and P_{j}^{t} ⊆ P_{i}^{t}, if i ≤ j.

The special version of the strong cutting plane algorithm is obtained by replacing the polyhedron P^{t} for which a j-cut is generated by the relaxation P_{j−1}^{t} ⊃ P^{t} and by computing only one cut per iteration.

Remark A.1 For all t = 1, 2, … and for all j = 1, …, n: R_{j}(P_{j−1}^{t}) ⊆ P_{j}^{t}.

Proof: P_{j}^{t} is obtained from P_{j−1}^{t} by adding some j-cuts. Any of these j-cuts is valid for R_{j}(P_{j−1}^{s}), for some s < t. Since R_{j}(P_{j−1}^{s}) ⊇ R_{j}(P_{j−1}^{t}), these cuts are also valid for R_{j}(P_{j−1}^{t}). □

Specialized Strong Cutting Plane Algorithm

Initialization: Let t := 1; C^{1} := C = {Ax ≥ b, 0 ≤ x ≤ 1},

Iteration t: 1. Solution of the linear relaxation: Optimize a linear function g^{t}

over the relaxation P^{t} = {x ∈ IR^{n} | x is a solution of C^{t}}.

2. Infeasibility test: If P^{t} = ∅, stop, C is unsolvable.

Otherwise let the vertex x^{t} ∈ P^{t} be an optimal solution.

3. Feasible 0-1 solution: If x_{j}^{t} ∈ {0, 1}, for j = 1, …, n, stop, x^{t} is a feasible 0-1 solution of C, C^{t} is the solved form of C.

4. Cut generation: Let j ∈ {1, …, n} be the largest index with 0 < x_{j}^{t} < 1. Generate a j-cut α^{j}x ≥ β^{j} by solving

max{β − αx^{t} | (α, β) ∈ R_{j}^{∗}(P_{j−1}^{t}) ∩ T }.

Define C^{t+1} by adding the j-cut α^{j}x ≥ β^{j} to the constraint set C^{t}.

5. Let t := t + 1 and goto 1.

Theorem A.2 Given a constraint set C : {Ax ≥ b, x ∈ {0, 1}} the specialized strong cutting plane algorithm either finds a feasible 0-1 solution or detects that C is unsolvable.

Proof: a) First we prove that the inequality α^{j}x ≥ β^{j} generated in Step 4 cuts off x^{t}.

To prove this, we show by induction that x^{t} is a vertex of P_{k}^{t}, for k = n, …, j. The case k = n is trivial, because x^{t} is a vertex of P^{t} = P_{n}^{t}. Suppose that x^{t} is a vertex of P_{k}^{t} ⊆ P_{k−1}^{t}, for some k ∈ {n, …, j + 1}. Since x_{k}^{t} ∈ {0, 1}, we get by Remark A.1 that x^{t} ∈ P_{k−1}^{t} ∩ {x ∈ IR^{n} | x_{k} = x_{k}^{t}} ⊆ R_{k}(P_{k−1}^{t}) ⊆ P_{k}^{t}. This implies that x^{t} is a vertex of P_{k−1}^{t} ∩ {x ∈ IR^{n} | x_{k} = x_{k}^{t}}. Since this is a face of P_{k−1}^{t}, x^{t} is also a vertex of P_{k−1}^{t}.

Next we show that x^{t} ∉ R_{j}(P_{j−1}^{t}). Since R_{j}(P_{j−1}^{t}) ⊆ P_{j}^{t} by Remark A.1, the assumption x^{t} ∈ R_{j}(P_{j−1}^{t}) would imply that x^{t} is a vertex of R_{j}(P_{j−1}^{t}). But all vertices of R_{j}(P_{j−1}^{t}) have a j-th component equal to 0 or 1 in contradiction to 0 < x_{j}^{t} < 1.

Since x^{t} ∉ R_{j}(P_{j−1}^{t}) there exists a valid inequality αx ≥ β for R_{j}(P_{j−1}^{t}) that is violated by x^{t}, i.e. β − αx^{t} > 0. We may assume that (α, β) ∈ R_{j}^{∗}(P_{j−1}^{t}) ∩ T. Therefore β^{j} − α^{j}x^{t} = max{β − αx^{t} | (α, β) ∈ R_{j}^{∗}(P_{j−1}^{t}) ∩ T } > 0, i.e. α^{j}x ≥ β^{j} cuts off x^{t}.

b) Next we prove by induction that for j = 1, …, n the set C_{j} of all j-cuts generated by the algorithm is finite.

For j = 1, this holds because every 1-cut corresponds to a vertex of R_{1}^{∗}(P_{0}^{t}) ∩ T = R_{1}^{∗}(P) ∩ T, of which there are only finitely many. Furthermore, every 1-cut cuts off some x^{t} that satisfies all 1-cuts generated earlier.

Suppose that C_{i} is finite for all i = 1, …, j −1 and consider the case i = j. Since P_{j−1}^{t} is defined by C ∪ ⋃_{i=1}^{j−1} C_{i}^{t} and C_{i}^{t} ⊆ C_{i}, there exist only finitely many different polyhedra P_{j−1}^{t}, t = 1, 2, . . .. Every j-cut corresponds to some vertex of some R_{j}^{∗}(P_{j−1}^{t})∩T, of which there are only finitely many, and it cuts off some x^{t} which satisfies all j-cuts generated earlier. Therefore the set C_{j} of j-cuts is finite, too.

c) Since only finitely many cutting planes can be generated by the algorithm, for some t ≥ 1 either P^{t} = ∅ or x^{t} ∈ {0, 1}^{n}. □

We used the proof technique of [BCC93a], which in turn is based on the convergence proof in [Jer80]. Note that cutting plane algorithms have the surprising property that choosing the wrong facets or generating deeper cuts than those specified may destroy finite convergence [Bla80].

B Cut Lifting

Given a fractional vertex x^{t} of the linear relaxation P^{t}, let F = {i ∈ {1, …, n} | 0 < x_{i}^{t} < 1} denote the index set of the fractional components of x^{t} and let |F | = r. By complementing variables if necessary, we can assume that x_{i}^{t} = 0, for all i ∉ F.

We now show how a lift-and-project cutting plane separating x^{t} can also be obtained by working on the subspace defined by F. This means that the size of the linear optimization problem that has to be solved in order to find a cut can be substantially reduced. Let Ã^{F} denote the (m + 2r) × rmatrix obtained from the (m+2n)×n-matrix Ã by removing column i and rows m+i, m+n+i, for all i ∉ F. Similarly, denote by α^{F} , (x^{t})^{F} , e_{j}^{F} ∈ IR^{r} resp. b̃^{F} , u^{F} , v^{F} ∈ IR^{m+2r} the vectors obtained from α, x^{t}, e_{j} ∈ IR^{n} resp. b̃, u, v ∈ IR^{m+2n} by removing the components i resp. m + i, m + n + i, for all i ∉ F. Note that m + i, m + n + i correspond to the constraints x_{i} ≥ 0, −x_{i} ≥ −1.

Consider the linear optimization problem

Maximize β − (x^{t})^{F} α^{F} subject to

\begin{aligned}α^{F} & −u^{F} Ã^{F} & −u_{0}e_{j}^{F} & & & = 0 \\ α^{F} & & & −v^{F} Ã^{F} & −v_{0}e_{j}^{F} & = 0 \\ & u^{F} b̃^{F} & & & & = β \\ & & & v^{F} b̃^{F} & +v_{0} & = β \\ & & & & u^{F} , v^{F} & ≥ 0 \\ & & & & ∑_{i∈F} |α_{i}| & ≤ 1 \end{aligned}  (12)

If (α^{F} , β, u^{F} , u_{0}, v^{F} , v_{0}) is an optimal solution to (12), then (α, β, u, u_{0}, v, v_{0}), with

α_{i}  = α_{i}^{F} , for i ∈ F
α_{i}  = \{ \begin{matrix}v^{F} Ã_{i}^{F} , & if v^{F} Ã_{i}^{F} ≥ u^{F} Ã_{i}^{F} \\ u^{F} Ã_{i}^{F} , & if u^{F} Ã_{i}^{F} ≥ v^{F} Ã_{i}^{F} \end{matrix} for i ∉ F,

u_{i}  = u_{i}^{F} , for i = 1, …, m
v_{i}  = v_{i}^{F} , for i = 1, …, m
u_{m+i}  = \{ \begin{matrix}(v^{F} − u^{F})Ã_{i}^{F} , & if v^{F} Ã_{i}^{F} > u^{F} Ã_{i}^{F} \\ 0, & otherwise \end{matrix} for i ∉ F,
v_{m+i}  = \{ \begin{matrix}(u^{F} − v^{F})Ã_{i}^{F} , & if u^{F} Ã_{i}^{F} > v^{F} Ã_{i}^{F} \\ 0, & otherwise \end{matrix} for i ∉ F,
u_{m+n+i} = 0, for i ∉ F
v_{m+n+i} = 0, for i ∉ F

(13) is a basic feasible optimal solution to the linear optimization problem

max{β − αx^{t} | (α, β) ∈ R_{j}^{∗}(P^{t}) ∩ T },  (14)

with the truncation T = {(α, β) | ∑_{i∈F} |α_{i}| ≤ 1}. Here Ã_{i} denotes the i-th column of Ã.

The proof of a similar result for the truncation β = 1 or β = −1 can be found in [BCC93a].

Example B.1 Consider again the 0-1 constraint set

C = {−2x_{1} − 2x_{2} ≥ −3, 2x_{1} − 2x_{2} ≥ −1}.

The linear relaxation P was given by the system of linear inequalities Ãx ≥ b̃, where

Ã^{T} = ( \begin{matrix}−2 & 2 & 1 & 0 & −1 & 0 \\ −2 & −2 & 0 & 1 & 0 & −1 \end{matrix} )

and

b̃^{T} = ( −3 −1 0 0 −1 −1 ) .

Suppose we want to generate a cutting plane for the fractional vertex (0, \frac{1}{2}) of P. This means that that F = {2} and r = 1. We remove from Ã the column 1 and the rows corresponding to x_{1} ≥ 0 and x_{1} ≤ 1. This yields

(Ã^{F})^{T} = ( −2 −2 . 1 . −1 )

and

(b̃^{F})^{T} = ( −3 −1 . 0 . −1 ) .

The corresponding linear optimization problem is

Maximize −\frac{1}{2}α_{2} + β subject to
α_{2} +2u_{1} +2u_{2} −u_{4} +u_{6} −u_{0} = 0
α_{2} +2v_{1} +2v_{2} −v_{4} +v_{6} −v_{0} = 0
−3u_{1} −u_{2} −u_{6} = β
−3v_{1} −v_{2}  −v_{6} +v_{0} = β
−1 ≤ α_{2} ≤ 1
u_{1}, u_{2}, u_{4}, u_{6}, v_{1}, v_{2}, v_{4}, v_{6} ≥ 0,

which has the optimal solution α_{2} = −1, u_{0} = −1, v_{0} = 1, v_{2} = 1 and all other variables are 0. Lifting gives us the values u_{3} = 2, v_{3} = 0, u_{5} = v_{5} = 0, and α_{1} = 2. Altogether, we have computed again the cutting plane x_{1} − \frac{1}{2}x_{2} ≥ 0 of R_{2}(P).