Optimization

278 Optimization: Algorithms and Applications

where there are n variables to be determined out of which p are integers and

the remaining variables are continuous.

10.3.1 Branch-and-Bound Method

In this method (Land and Doig 1960), the optimization problem is solved

with continuous variables, and the integer constraints are relaxed. If the

solution obtained is integers, the algorithm is terminated as it represents the

optimal solution of the integer problem. If one of the integer variables x

k

is continuous, then one has to solve two additional subproblems with the

upper bound constraint

x

k

≤ [x

k

] (10.9)

and lower bound constraint

x

k

≥ [x

k

] + 1 (10.10)

This process of the branching ensures that feasible integer solutions are ...