10.6 Branch-and-Bound Method 609
thekth term of the polynomial simply becomesckyk. However, we need to add the
following constraints to ensure thatyk= when all 1 xi= and zero otherwise: 1
yk≥
(n
∑k
i= 1
xi
)
−(nk− 1 ) (10.39)
yk≤
1
nk
(nk
∑
i= 1
xi
)
(10.40)
It can be seen that if allxi= , 1
∑nk
i= 1 xi=nk, and Eqs. (10.39) and (10.40) yield
yk≥ 1 (10.41)
yk≤ 1 (10.42)
which can be satisfied only ifyk=. If at least one 1 xi= , we have 0
∑nk
i= 1 xi< nk,
and Eqs. (10.39) and (10.40) give
yk≥ − (nk− 1 ) (10.43)
yk< 1 (10.44)
Sincenkis a positive integer, the only way to satisfy Eqs. (10.43) and(10.44) under
all circumstances is to haveyk=. 0
This procedure of converting an integer polynomial programming problem into an
equivalent zero–one LP problem can always be applied, at least in theory.
10.6 Branch-and-Bound Method
The branch-and-bound method is very effective in solving mixed-integer linear and
nonlinear programming problems. The method was originally developed by Land and
Doig [10.8] to solve integer linear programming problems and was later modified
by Dakin [10.23]. Subsequently, the method has been extended to solve nonlinear
mixed-integer programming problems. To see the basic solution procedure, consider
the following nonlinear mixed-integer programming problem:
Minimizef (X) (10.45)
subject to
gj( X)≥ 0 , j= 1 , 2 ,... , m (10.46)
hk( X)= 0 , k= 1 , 2 ,... , p (10.47)
xj= ntegeri , j= 1 , 2 ,... , n 0 (n 0 ≤ n) (10.48)
whereX= {x 1 , x 2 ,... , xn}T. Note that in the design vectorX,the firstn 0 variables
are identified as the integer variables. Ifn 0 = n,the problem becomes an all-integer
programming problem. A design vectorXis called acontinuous feasible solutionif
