A Further Investigation of Efficient Heuristic Procedures for Integer Linear Programming with an Interior

摘要

Some heuristic procedures for seeking a good approximate solution of any pure integer linear programming problem are evaluated. It was found that the procedures are extremely efficient, being computationally feasible for problems having hundreds of variables and constraints. Furthermore, they proved to be very effective in identifying good solutions, often obtaining optimal ones. Thus, the procedures provide a way of dealing with the frequently encountered integer programming problems that are beyond the computational capability of existing algorithms. For smaller problems, they also provide an advanced start for accelerating certain primal algorithms, including the author's Bound-and-Scan algorithm and Faaland and Hillier's Accelerated Bound-and-Scan algorithm. In addition, Jeroslow and Smith have found that imbedding the first part of one of these procedures inside the iterative step of a branch-and-bound algorithm can greatly improve the latter's efficiency in locating solutions whose objective function value is within a specified percentage of that for the optimal solution.