Computational Considerations in
To date, and despite over 40 years of research, there does not exist a
computer code that can solve ILP consistently. Nevertheless, of the two
solution algorithms presente~ in this
chapter,B&B is more reliable. Indeed, practically aU commercial ILP codes
are B&B based. Cutting-plane methods are generally difficult and uncertain,
and the roundoff error presents a serious problem. This is true because the
"accuracy" of the cut depends on the accuracy of a true
representation of its fractions on the computer. For instance, in Example
9.2-2, the fraction 1/7 cannot be represented exactly as
a floating point regardless of the level of precision that may be used. Though
attempts have been made to improve the cutting-plane computational efficacy,
the end results are not en-couraging. In most cases, the cutting-plane method
is used in a secondary capacity to improve B&B performance at each
subproblem by eliminating a portion of the solu-tion space associated with a
The most important factor affecting computations in integer programming
is the number of integer variables and the feasible range in which they apply.
Because avail-able algorithms are not consistent in producing a numeric ILP
solution, it may be ad-vantageous computationally to reduce the number of
integer variables in the ILP model as much as possible. The following suggestions
may prove helpful:
1. Approximate integer variables by continuous ones wherever possible.
2. For the integer variables, restrict their feasible ranges as much as
3. Avoid the use of nonlinearity in the model.
The importance of the integer problem in practice is not yet matched by
the de-velopment of reliable solution algorithms. The nature of discrete
mathematics and the fact that the integer solution space is a nonconvex set
make it unlikely that new theo-retical breakthroughs will be achieved in the area of
integer programming. Instead, new technological advances in computers (software
and hardware) remain the best hope for improving the efficiency of ILP codes.