Disjunctive programs and sequences of cutting-planes

UNIVERSITY Of

ILLINOIS LIBRARY

^ URBANA-CHAMPAIGN

STACKS

Digitized by the Internet Archive

in 2011 with funding from

University of Illinois Urbana-Champaign

http://www.archive.org/details/disjunctiveprogr576blai

Faculty Working Papers

College of Commerce and Business Administration

Unlv.r.ity of Illinois at U rb a n a - C h a m p a i g n

Sharpe, Wxlliam TTW^^m^PfWIP^li

Equilibriurd Under Conditions of Risk," Journal of ^

Stigler, G. (1963). Capital and the Rate of Return in
Industries, Princeton: Princeton University Press.

Taylor, G.R. (1951). The Transportation Revolution 183
York; Holt, Rinehart and Winston.

U.S. Bureau of the Census, (1975). Historical Statistic
Washington, D.C.: Government Printing Office.

FACULTY UOPaCIilG PAPE?.S
College of Commerce and Business Administration
University of Illinois at Urbana-Champaign
June 6, 1975

DISJUliCTIVE PROGPJUiS Mo SEQUENCES OF
CUTTinC-PLAi^ES

Charles E. Blair, Assistant Professor,
Department of Business Administration

#576

Summary :

We continue work of Balas and Jeroslov; on cutting-planes algorithms
for disjunctive programs. VJe shov; that, in theory, finite conveiigence
can still be obtained even if the extreme point to be cut away and the
disjunction used to generate the cut are chosen arbitrarily. A more
computational variant of the same idea is also presented as well as a
small example illustrating non-convergence.

Disjunctive Programs and Sequences of Cutting-Planes

by
Charles E. Blair

Introduction

Many discrete optimization problems can be viewed as systems of
linear inequalities together with restrictions of an "either-or" type,
e.g., either x^ = 0 or x^ = 0 or x^ = 0. Balae [1, 2] introduced
disjunctive programs to develop the general theory of such problems.
P = {x|Ax 2. ^^ C ^ is a polytope given by the usual inequality constraints,
A disjunctive constraint is a requirement that the feasible set satisfy
at least one of the Ineqxxalities d.x >^ e. , i = l,,,.k; where
PA d.x 2. ^4 is a face of P. The constraints of a disjunctive program
consist of the inequalities defining P, together with t disjunctive
constraints, each of the form

(1) xf (J (PAdx^e) j = l,...t

ifD^

Disjunctive programs include as special cases zero-one integer programs
.-and linear complementarity problems.

We consider cutting-plane methods of obtaining the feasible set S.
For QC P the inequality ax >^ 3 is said to be valid for Q if az >_ B for
all z € Q. For 1 £ j £ t define

(2) E(j,Q) = \J (Q/^d x^ e )

^^j
Hence

t

(3) S = r\ E(j,P)

j=l

-2-

No method of obtaining valid inequalities for S directly is known.
However, Balas [1, sea also 3] has shown how valid inequalities for
E(j ,Q) may be obtained by solving certain linear programs. It is also
shown in [1] that S = E(t, E(t-1, E(t-2, . ..E(2, E(1,P) )...)• In
principle, the feasible set may be obtained by adding all the inequalities
generated by the first disjunctive constraint, then adding all cuts generated
by the second constraint (applied to E(1,P)), and so forth. Since the num-
ber of facets of E(1,P) is typically exponential, other methods are needed.

Jeroslow [5] considered schemes in which cutting-planes are added
one at a time. One started with Q_ = P. At the kth step one has Q^.^ Qi^^-.
and an extreme point z, of Q, . If z, ^ S the algorithm stops. Otherwise
j is determined such that z, ^ ECjjQ, ). An inquality ax >_ 3 is obtained
(using the Unear program techniques mentioned above) which is valid for
E(J>Qi,) Slid such that c", < 3, i.e., the point z, is cut away. Then
Q. ,^ = Q.Y°\ciX >^ 3, an extrime point z, _^^ of Q, ■•, is located, and so forth.

Jeroslow shov/ed rhat if j, ct, 3 are suitably chosen at each step, then
conv(S) will be obtaireil in finitely many steps, regardless of the choice
of extreme point z, at each step. The finiteness proof is non-trivial. We
give a small example at the end of this paper to show that finiteness may
fail if one simply chooees at each step an arbitrary facet of E(j,Q ) which
cuts away z ,

The problem is posed In [5] whethar one can still obtain finite
convergence if one is allowed to choose z, and also the j, such that

\

tf E(j, J Q. ) at each step (i.e.j one chooses both the extreme point
and the disjunctive constraint to be used to cut it away arbitrarily). We
will show that this can ba done, although the cuts used may be difficult

-3-

to confute. We thee present a related algorithm In which the cuts are
generated via linear programs. Finally we present the example mentioned
previously and discuss finiteness proofs in general.

Preliminary Analysis

We begin with a formal description of cutting-plane procedures in
general. Let W be the set of all finite sequences of quadruples
(z^* a^* 6^, jj)

(4) W " {<(2^, a^, 6^. jj^)>Q < i < K^ [z^. a^ ^ R^*; S^, f. R; 1 1 j^ 1 t]

such that (i) a^ = 0, £« = 0 (ii) z is an extreme point of

(5) %,-^Q^\-th

(lii) z^^ E(j^. Q^) (iv) a^z^^ < 6^, and (v) Q^ ^ S for all 0 < m < K.

We will denote those w ^ W of length k+1 [i.e., last term is (z, , a, , g. , j, )]

by W^. Thus, W = (J W^.

k ttfl

We identify a cutting-plane procedtore with a function A: W -♦• R

that assigns to each w f W^ A(w) = (a, ,, , 3^+.-.) such that (iv) and (v)

,are satisfied for m = k+1, A is finitely convergent if and only if

(6) there is no infinite sequence <(z. , a. , B,, J.)>

such that, for every m, w C W^ and (a , g ) = A(w ,) [w = first nri-1

m^ mm m-i m

members of the infinite sequence] .

In other words, regardless of the choice of z and jj at each step,

one eventiially reaches a situation in which every extreme point of Q is

t
in f\ E(j,P) » S, hence Q = conv(S).
j«l ^

_4-

A crucial role in our subsequent analysis is played by the fact
that E(j,P) is a union of faces of P. Let

(7) P(ni) - {x;|x^F for some face F of P of dimension _< m}

Suppose we have obtained a poly tope Q^S. Since the extreme points of
conv(S) are extreme points of P, S is contained in the convex hull of
those extreme points of P which are members of Q, i.e.,
conv(Q^ P(0)) ^ S. More generally.

Lemma; Let Q^ S and 0 _< m ^ n. Then conv(Q fj P(m)) ^ S.

Proof; Since P(t!i+1) "^ P(m) it suffices to show this for m=0. By
(2), (3), and de Morgan's law, we may write S as a union of intersec-
tions of faces of P. Since the intersection of faces is a face, this
establishes that S is a union of faces of P. Since a face of P is the
convex hull of certain extreme points of P, it follows that convCS) is
the convex hull of extreme points of P, as claimed above. Q.E.D.

We describe informally our cutting-plane scheme. At each step we
have 0*^5 and z an extreme point of Q . Let

(8) d = dimension of that face F of P such that

m m

z ^ interior (F )

m *• m

If d =0, i.e., z is an extreme point of P, we cut z away using any

m m n.

inequality valid for S. Since P has a finite number of extreme points
this only happens finitely often. If d > 0 then

m

C9) ^^'^onH^f^Hd^-D

)

-5-

(10) conv(F^f^Q^nP(d^- l)):?F^nEa^. V

(9) follows from the fact that z is an extreme point of Q . (10) holds
because F ^ E(j , Q ) is a union of proper faces of F .

We construct an inequality ot -x >^ g^, which is valid for E(j , Q )
and cuts away z . To ensure finite convergence we arrange that
F f\ '^■m+i^ " ^m+l ^® (roughly speaking) a facet of Conv (F /) Q ^P(d - 1)

The Convergence Theorem

k
For w f W and 1 f. d <^ n let

(11) L(d,w) ■■ largest m <^ k-1 such that d < d

For Q C^ s""^ ^ 3 d-dimensional face of P a finite set S(Q,F)C r'^
is defined to be a sharp set of inequalities if

(12) conv(Qn FA ^W-D) ^QO^H ax>.6

(a,JJ)f S(Q,F)

Sharp sets of inequalities exist, e.g., the facets of Q O F(d-l).

Theorem: Suppose that for every F, Q S(Q,F) is a sharp set^pf in-
equalities. Suppose A: W -> R is a cutting-plane procedure such that
for every w^ W if A(w) = (a, . , , &..■■) then

k+1' "k+1'

<^3> \4-l\ < Vl

(14) If \=o Qi,0\+i-^\+i> ^

(15) if d, > 0 then for some (a,3) ^ S(Q^ . . . ^, , F, )

-6-

(16) if \ > 0 QkA%+i- ^ ^+1 ^ \ri n^y-i) ,

Then A is a finitely convergent procedure, i.e., (6) holds.

Proof; With each w ^ w we associate C(w) = (a„, a^ , . . .a ), an
(n+1) -tuple of natural numbers measuring the complexity of Q, . a„ Is
the nxunber of extreme points of P in Q, . For 1 ^ d ^ n we define

(17) a^ = Z N(F)

F

where N(F) is the number of (a,e) C S((L ,, . .^ , F) such that

* Hcl,wJ+i

Q, /^ F f\ a-x. >_ a ^ Q, A i''» and the sum is over all d-dimensional faces

F of P. Let w ^ W^"^ be such that (a, .,, K^t) = A(w) and w = the

first (k+1) terms of w". Let C(w ) = (a„,... a ). If d, = 0 a„ < a^

u n K. u u

*
because z^Q - Q, j.-. • If d, > 0 and i _< d, then L(i,w) = L(i,w ).

Since Qu.i^ Qn» a ^a . Further a, < a, because, by (15),

N (F|^_t) ■* ^(^i,_-i)' Hence C(w ) is lexicographically smaller than

C(w). By well ordering, no infinite sequence is possible. Q.E.D.

Condition (16) is not used directly in the convergence proof. Its

purpose is to insure that, at each step of the algorithm, if d, > 0,

then there is some (a, 3) fi. S(Q^ ,, ^.,,F, ) such that az, < S. This follows

^ L(d, ,w)+l k k

from the fact that, for all d > 0, Q, ^ Q^ , , ,^, C\ P(d-l).

' ^k "^ ^L(d,w)+1

Solution of the Problem of Jeroslow [5]

/• k
We must construct a finitely convergent A such that, for w^ W

A(w) = (C|.,T. Pi.4.1) is such that

-7-

We require a variant of the separating hyperplane theorem, which can be
proved by the usual convex analysis methods.

Lemmfl. Let tC^P be a polytope, F a face of P, v f R , 5<» R,
z f F-T. If vz < 6 and F/^vx >. 6 p F f\ T, then there are (a, Is) such
that P^ ax >_ e 5 T and (F A cue = 3) ■=(? A vx = 6),

Now we specify the desired A. S(Q,F) consists of all the facets
of Q/\P(d-l). If d, = 0, \fe cut z, away using any valid Inequality
for E(j-, Q ). If d > 0, then by (9) and (10) there are
(v,6) ^ S(Qj^.^ J,, )+l»^^^ ^"'^^ ^^^^ ^\ < 5 and Q^/^ Fj^n vx >. 6 ^
conviqji ¥^f\ P(dj^-l) ) P Qk A ^k A EO . Q^) • We let T = conv((Qj^ /\ P(dj^-l)) [J
E(j» Qi^)) and apply the leimna to obtain a. ^ , g, - satisfying (13), (15),
(16), and (18).

An AlRorlthm Based on Cuts Generated by Linear Programs

The cutting-plane procedure described in the preceeding section '■'■
seems impractical because, among other things, each step depends on
locating a facet of conv(Q, /^ (d, -1) ) . In this section we describe an
algorithm based on similar ideas in which the cuts are generated at each
step by finding basic feasible solutions (not necessarily optimal) to
certain linear programs.

We convert the representation of P to equation form by adding slack
variables, so P = {y|B y = b , y ^ 0} where B has q rows and r columns.

At step k of the algorithm the next cut is added by introducing a new

(k)
row to the constraints and a Tie\-f non-negative variable v . In general

we have

(19) Qj^ = -CylBj^y + C^v - h^; y, v >. 0} where

-8-

B, is (q+k)xr and C^ is (q+k)=<k. B^^^ and C^^^ will denote the ith
columns of the m&trices, while y, , v will be components of vectors.
At each step (y, ,v, ) ^ R is an extreme point of Q, corresponding
to a choice of basic \7ariables in (19) . y, is in the interior of the
face of P

(20) F^ = {ylB^y = b^, y 1 0 y*^^^ = 0 if y^^^ = 0}

As before d, = dimension of F, and L(d,k) = the largest m <_ k-1 such

that d < d.

m

At step k+-l (y, »v" ) must be cut away. Let

(21) J = {l|y^^^ > 0}

(22) D, = U {(y,v)|(y,v)f Q, and y*^^^ = 0}

^ i^ J ^

Then D,^/\ ^^^ = \A P(di.-l)n Q^ ^^'^ conv(Dj^) ■> conv(Qj^/^ P(dj^-l). It
follows from results in [3] that every inequality ay + &v _> v valid
for Q^i/^^v (0 ^ "1 f. ^) call be obtained from a feasible solution to the
"disjunctive dual program"

(23) minimize ay, + gv, - v

subject to

'^j-^i^k'^^ J = 1»"«^; i ^ -^ - tj>
^- 1 ^.c5-^'^ j = l,..,m i £ J

Bj = ^i^^^ m < j <.k i^ J

V < u.b, i ^ J
— 1 k

(-1, . . . , -1) 1 u^ <^ (1, . . . , 1)

-9-

In (23) the variables are a f R^, g (« R^, v f R, and u f R^"*"^ for
all if> J. The inequalities ccrreeponding to basic faasible solutions
to (23) constitute a i,harp set of inequalities S(Q , F, ) .

If (y, , V, ) 1 S we cut it away by using an (a, 3, v) corresponding
to a basic feasible solution of (23), m = L(d^,k)+1, with negative
objective function value Clt is not necessary to find the optimal solu-
tion, although this will produce a deeper cut) . Then the new row added
to the tableau is

(24) -ay - B,f + v^^"*""*-^ = -v

pivot operations are perfonned to locate the next extreme point

^k+1' \+l^ ^^^ ®° forth.

This algorithm is similar to that in [5] in that it is finitely

convergent, cuts away .?.n arbitrarily chosen extreme point at each step,

and uses disjunctive, duel progreois to generate the cuts. The main

difference is tliat ths algorithm of Jeroslcv generates a valid inequality

for E(j, » Q, ) at each Rtep, while our algorithm generates a valid in-

eqtiality for conv(0 /*^ P(d, -1)) . I.-idead, the only use we make «>- the

sets E(J,P) is to test whether the current point is i^- the feasible

set S. The linear piopram (23) comparas unfa" rably with the analogous

program in [5, (7ft-7b)j if the sets ^\,J$ are simple, i.e., the union

of small' numbers of faces, " ..uo case of complex E(j,fi) our program

(23), which f^'—-- .^y avoids the E-sete, may be superior. In both

cases the LPs are not as large as they look, and computational tricks

and simplifications will he investigated later.

-10-

An Example of Non-Convergence;

The finiteness proofs here and in [5] are surprisingly messy.
We offer an example of a non-convergent cutting-plane procedure, which

suggests that some delicacy is required to insure finiteness.

3
Let P R be the polytope whose extreme points are

(25) (3,3,0) (3,3,5)

(0,8,0) (0,8.,e) [8 and <f> to be specified later]

(8,0,0) (B,o,e)

(3,10,0) (3,10,$)

(10,3,0) (10, 3, f)
• (8,8,0)

Geometrically P has a hexagon base and an upper surface that is a
"creased hexagon." The two are joined at the point (8,8,0).
There are two disjunctive constraints

(26) E(1,P) = {(x,y,z)ix =0 or y = 0 or z = 0}

E(2,P) = {(x,y,x)lx + y = 6 or x = 10 or y = 10 or z = 0}
S = P E(1,P) E(2,P) = {(x,y,z) PJz = 0}
Let 9,<j) satisfy

(27) 4<9<5 iji=|-e

o

Then the extreme point (0,8,9) can be cut away by the inequality

(28) (5-(J>)x + (5-<J;)y + 7z _< 63 - 6$

(28) is a facet of E(2,P) which goes through C3,3,5); Ci,10,<j)); and
(10,3,*).

-11-

Q = P (28) has the same extreme points as Q = P except that
(0,8,9) and (8,0,6) are replaced by (0,8,9'); (8,0,9') such that

(29) <!. >| 6' 9' =-|4' +7^

The extreme point (3,10,({;) can be cut away by the inequality

(30) 9'x + e'y + 8z _< 166'

(30) is a facet of P(1,Q ) which goes through (0,8,9'); (8,0,9') and
(8,8,0).

^2 '^ ^1 ^^^^ ^^® ^^^ extreme points (10,3,$) (3,10,<|>) replaced ^•'
by (10,3,<(.') and (3,10,<j)') where

(31) 4 < 9' < 5 <|)' = I 9'

O r

Since (31) is the same as (27) the process can be continued indefi-~
nltely.

Two remarks should be made about this example. At each step there
is only one j such that the present extreme point is not in E(j,Q,).
This is not a case of choosing the wrong disjunction but rather the wrong
facet, which keeps creating undesirable new extreme points. Secondly,
it should be noted that the sequence of extreme points does not approach
a member of S in any limiting sense.

Concluding Remarks

There are two areas in need of investigation. Firstly, the behavior
of computer implementations of these ideas needs to be studied (as pre-
viously stated, this paper concentrates on theoretical issues and an

-12-

actual Implementation would depend on further tricks) . Secondly, the
finiteness questions are still rather mysterious. Both the methods
described here and in [5] have the irritating property that the finite-
ness proof may fail if deeper cuts than the ones specified are used
(this is related to the creation of unwanted extreme points in our ex-
ample) . The author feels that present convergence proofs are more
cumbersome than they should be, and that a theory unifying the various
techniques is needed. The idea behind all convergence proofs for
cutting-plane methods is that the polytope after a cut is "simpler" than
the polytope before the cut. We lack a thorough understanding of what
constitutes appropriate definitions of "simpler."

Finally, we wish to mention a question related to Gomory's method
of integer forms. Gomory [4], after showing that certain row selec-
tion rules guaranteed finite convergence, observed that he knew of no
example of non-convergence arising from an arbitrary selection of rows
at each step. Twenty years later, no such example has been constructed.

M/C/139 „

-*»5-

References

1. Balas, Egon. "Dlsjxuictive Programming; Properties of the Convex
Hull of the Feasible Points," MSRR No. 348, GSIA, Carnegie-Mellon
University. (1974)

2. Balas, Egon. "Disjunctive Programuing," MSRR No. 415. Presented
at Discrete Optimization Conference in Vancouver, 1977.

3. Blair, Charles and Jeroslow, Robert. "A Converse for Disjunctive
Constraints." Journal of Optimization Theory 25 (1978), pp. 195-206.

4. Gomory, Ralph. "An Algorithm for Integer Solutions to Linear
Programming." lUM Technical Report 1958.

5. Jeroslow, Robert. "A Cutting-Plane Game and Its Applications,"
CORE discussion paper no. 7724. (1977)

nOOfJDfi^

3-9*