Engineering Optimization: Theory and Practice, Fourth Edition

610 Integer Programming

Xsatisfies constraints (10.46) and (10.47). A design vectorXthat satisfies all the

constraints, Eqs. (10.46) to (10.48), is called aninteger feasible solution.

The simplest method of solving an integer optimization problem involves enumer-

ating all integer points, discarding infeasible ones, evaluating the objective function

at all integer feasible points, and identifying the point that has the best objective

function value. Although such an exhaustive search in the solution space is simple

to implement, it will be computationally expensive even for moderate-size problems.

The branch-and-bound method can be considered as a refined enumeration method in

which most of the nonpromising integer points are discarded without testing them. Also

note that the process of complete enumeration can be used only if the problem is an

all-integer programming problem. For mixed-integer problems in which one or more

variables may assume continuous values, the process of complete enumeration cannot

be used.

In the branch-and-bound method, the integer problem is not directly solved. Rather,

the method first solves a continuous problem obtained by relaxing the integer restric-

tions on the variables. If the solution of the continuous problem happens to be an

integer solution, it represents the optimum solution of the integer problem. Otherwise,

at least one of the integer variables, sayxi, must assume a nonintegral value. Ifxiis

not an integer, we can always find an integer [xi] such that

[xi] <xi<[xi]+ 1 (10.49)

Then two subproblems are formulated, one with the additional upper bound

constraint

xi≤[xi] (10.50)

and another with the lower bound constraint

xi≥[xi]+ 1 (10.51)

The process of finding these subproblems is calledbranching.

The branching process eliminates some portion of the continuous space that is not

feasible for the integer problem, while ensuring that none of the integer feasible solu-

tions are eliminated. Each of these two subproblems are solved again as a continuous

problem. It can be seen that the solution of a continuous problem forms anodeand

from each node two branches may originate.

The process of branching and solving a sequence of continuous problems discussed

above is continued until an integer feasible solution is found for one of the two con-

tinuous problems. When such a feasible integer solution is found, the corresponding

value of the objective function becomes an upper bound on the minimum value of the

objective function. At this stage we can eliminate from further consideration all the

continuous solutions (nodes) whose objective function values are larger than the upper

bound. The nodes that are eliminated are said to have beenfathomed because it is

not possible to find a better integer solution from these nodes (solution spaces) than

what we have now. The value of the upper bound on the objective function is updated

whenever a better bound is obtained.