Jacob Akoka.

Rounded [i.e. Bounded] branch and bound method for mixed integer nonlinear programming problems online

. (page 1 of 2)
Font size LIBRARY

OF THE

MASSACHUSETTS INSTITUTE

OF TECHNOLOGY

FtB2 3 1977

DEWEY LIBRARY

WORKING PAPER
ALFRED P. SLOAN SCHOOL OF MANAGEMENT

ROUNDED BRANCH AND BOUND METHOD FOR

MIXED INTEGER NONLINEAR PROGRAMMING PROBLEMS

Jacob Akoka

WP 904-77

January 1977

MASSACHUSETTS

INSTITUTE OF TECHNOLOGY

50 MEMORIAL DRIVE

CAMBRIDGE, MASSACHUSETTS 02139

u

Dew»y

MASS. INST. TECH.

FEB 2 3 1977

DEWEY LIBRARY

ROUNDED BRANCH AND BOUND METHOD FOR

MIXED INTEGER NONLINEAR PROGRAMMING PROBLEMS

Jacob Akoka

WP 904-77

January 1977

r-i 2L r-. U-.'^'=Rn

M.I.T. LID;1ARIES

FEB 2 4 1977

ABSTRACT

Most of the research in the field of integer programming has
been devoted to the case of integer linear prograiraning.When one
has to deal with non-lineraties, linearization techniques are used.
But these techniques are not general enough to be applied to
all the varieties of non-linearities. Besides, the techniques
add more variables to the original problem, making large-scale
problems very difficult to solve.

In this paper, a method is described to solve integer nonlinear
programming problems . In this "bounded Branch and Bound" method,
the arborescence has only N nodes, where N is the number of variables
of the problem. Therefore, we store in the main memory of the
computer only the informations relative to the N nodes. We can
therefore solve large-scale integer nonlinear programming problems.

When the objective function and the constraints are convex, a
procedure is given, which enables us to alleviate the arborescence.
For non-convex problems, a specific method is described. While
optimizing a problem of the arborescence, some "fortuitous integer
variables" may appear. A procedure is described to schedule these
variables. Our method is also specialized to the case of Boolean
variables.

Five different criteria which enable us to chose the "separation
variable" are described and ordered. Finally, a programming code
was written in Fortran IV. We report the results obtained using this
code. The CPU times necessary to solve the problems are very small.
We can therefore expect to solve large-scale integer nonlinear programming
problems in reasonable time.

I'^OH^isn

-2-

INTRODUCTION

In this paper, we describe a method, called Bounded Branch
and Bound method, which enables us to solve mixed (or pure)
Integer Nonlinear Prograimning problems. The formulation of the
problem is:

Max (x) XER

Subject to
h^(x) < 0- 1=1,2, ... ,m

(c-1)

a < x < b j eJ= 1,2, ... ,n
J - J- J (c-2)

X integer j eEcj {c-3)

J

In (I-l) , we give a brief outline of the Bounded Branch and Bound
method .

A procedure to construct an oriented graph associated with the
problems is described in (1-2). In (1-3), we develop a sepcific
graphical language for the arborescence, and in (1-4) we describe
6 different rules which are to be used in the arborescence.
Depending on the ruXe used, each node change from one state to
another one. The transformation table is given in (1-5) .

A detailed procedure describing the passage from node s to node
t is given in (1-6). If the problem is convex (i.e. the objective
function and the constraints are convex) , two properties are
developed. The first one allows us to refuse a node of the arborescence
without investigation. The second one enables us to stop the
optimization process of a problem before the end. These techniques
are described in (1-7) .

In (1-8) , we relax the assumption that the problem is convex.
Therefore, we develop a specific algorithm for the non-convex
case. Some modifications are indicated in (1-9) , in order to solve
the case where all the variables are boolean.

At each node of the arborescence, we will have to solve a con-
tinuous nonlinear programming problem. When solving this problem
some variables may become integer. Such variables are called
"fortuitous integer variables" (fiV) . A procedure to schedule these
variable is developed in (I-IO) . At each node, we will have to
choose a variable to become integer. Such variable is called the
"separation variable". Five different criteria are given, in order
to choose this variable (I-ll) . A proof of the convergence of the
algorithm is given in (1-12) and in (1-13) we indicate the number

of nodes to be stored in the main memory of the computer. In (1-14) we give a
complete example.

In chapter II, we describe the numerical computations. Ten

different problems have been solved using BBB and the five different

criteria developed precedently (II-l) . In (II-2) , we describe

three different methods which enable us to order the five criteria.

In (II-3), we present a flowchart of the computer code that has been

written. A very brief description of the most important modules

is given.

-4-

In Appendix 1, we give the listings of the subroutines described in
(II-3).

The Problem

Let us consider the following problem:

Max (fi (x) xeR

Subject to:

(P)

h (x) £0 £= 1,2, ...,m (c-1)

a [x ] (respectively x < [x ] + 1) we can conclude

that a solution that has x„ = [x„] (respectively [Xp]+1)

will be infeasible for P (T) . Therefore, we don't have to

solve P (T) . We can refuse node T without solving P (T) .
(b) if Xg = [Xg] (respectively Xg = [Xg]+1) the solution
X of P. (respectively x of P ) is infeasible for P (T)

-16-

1-7. Case where (|) (x) and h. (x) are convex

Let's assume that the problem is convex and dif ferentiable. These
two properties will allow us:

(i) to refuse a node without solving its corresponding problem,
(ii) to interrupt the iterations in the process of optimization.

(A) Refusal of a node without investigation

Let T be an accepted node at the level t. Assume that T is in a
wing originated by a node S at the level t-1. Let's call U the successor
of T at this wing (Fig. 1).

t-1

T
-O-

U

Fig. 1

Let S = (A, X )

= (B, Xg) ^Bi Xg j

where :

B = A^ (B) with 6 e E-E{S)

■v • -

X. =x.=x. V. EA

: 3 D ' D

^g = [Xg(S)]+l

^^6 = ^8^ '

with £ = {

+1 for a right wing
-1 for a left wing

-17-

Let's write down Kuhn-Tucker conditions for problem P(T):
^ A . (T) , y, (T) such that

A. (T) > {4-a)

1 —

yj^(T) ^ if Xj^{T) = a^^ (4-b)

Vi^(T) 1 if x^CV) = h^ (4-c)

\l^(T) =0 if aj^ < x^(T) < h^ (4-d)

7^+ i ^■(T)|-H') =y,(T),k J-B (4-e)

OX, >, 1 I ox, / k

k 1=1 > k/

x=x(T)

m

y A. (T) h. (x(T)) = {4-f)

i=l ^

m

}
1 i

()) = (}) + J] A.h. is convex. Therefore:
i=l

-^'-(f!)

(t)[x{W)] > (t)[x(T)] + [x{U) ^ . ..^.

— '^"/x = x (T)

m „ ^ m ^

^[xCU) + E A.{T) h.{x(T)) ;> [x(T)] + E A . (T) h. (x (T) )
1=1 1=1

+Z pi^^ + Z X.(T) - ^^ [ ^ [x(U) - x(T)]

KeJ-B[ 3x^ i=l ^ 3x^ Jx=x(T)

i - ^ + E A.(T) — ^^

t 9x 1=1 K -'

"" \ -• x=x(T) , {4-g)

Using (1-1) and (4-a), we have:

ilh A

E X. (T) h. (x{T))£
i=l ^ ^

Using (4-f), we obtain:

m

E X. (T)h. (X(T))=0
i=l " ^

-18-

Using {4-b) , (4-c) , (4-d) and (4-e) , we have:

E [ -?^- + ^ ^.(T)-.-^ - ] [x(U)-x {T)]>

dx . , 1 ax,, —

KeJ-B K 1=1 K T

M
-^r. (U)] > Hx (T) . e[-|i- . E A.(T) 1^ ]^^;^^^ ^^_^^

p 1-1 p

Let J^=* U (T) . ^[|^ +.^ ^i(T) ^^] . (4_i)

3 1=1 B x = x{T)

and ((.y = (t.[x(U)] (4-j)

Therefore, we obtain:

\ 1 ^ =^ y

Therefore, we can refuse node U.

B. Interruption of the Iterations while Optimizing

(i) When solving problem P(S), at each iteration, the
inequalities give us a lower bound of ^ .

Let ( X be the current variable at the iteration 1 ,
) be the best integer solution found.

ij) be the lower bound associated with x

when l->«> ,• , we can stop the iterations
of P(S) when (}). We can obtain the lower bound using A. and

-19-

y defined in the precedent paragraph.

make

(ii) When we solve problem P. (respectively P ) , we try to

X equal to [x. ] (respectively [x.] +1].
p p p

- in P. we minimixe x^. If x^ could not be reached, we will know
1 p p

it when the lower bound associated to x will be greater than

p

[ x J+1 . We therefore add the following rule to our algorithm:
p

Rule 3bis : In moving up in the arborescence , if we are in
0RA3 or RRA3 (respectively AR03 or ARR3) , then:
(i) if we have an evaluation ((> for T, the

successor of S in its wing and

% A

(ii) if (}) > (j)

Refuse the wing corresponding to S .

If, while optimizing, we obtain for the problem P. (respectively P )

1 s

a solution close to x (i.e. x ie) , accept the node and stop the

6 p

iterations.

-20-

1-8. Case where (})(x) and h.(x) are non-convex

In this paragraph, we don't assiame convexity for fxinctions (|) (x) and

h.(x). In this case, two cases of refusal of a node exist.

first case : Refuse any node which does not improve the objective

function (i.e. when (()). Therefore, refuse all

s

its descendants.
second case ; If a variable, already integer , is at one of its

bounds, refuse the successor corresponding to its
wing.
Therefore, the rules to use are:

Rule ; If t=0, investigate node S , (i.e., solve the continuous

nonlinear programming) and let (() = +

1