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*