Computational Considerations in ILP

Computational Considerations in ILP

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 subproblem.

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 possible.

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.