Efficient Heuristic Procedures for Integer Linear Programming with an Interior
Frederick S. Hillier · Operations Research · 1969
This paper presents and evaluates some new heuristic procedures for seeking an approximate solution of pure integer linear programming problems having only inequality constraints. The computation time required by these methods (after obtaining the optimal noninteger solution by the simplex method) has generally been only a small fraction of that used by the simplex method for the problems tested (which have 15 to 300 original variables). Furthermore, the solution obtained by the better procedures consistently has been close to optimal and frequently has actually been optimal. Plans for generalizing these methods also are outlined. A companion paper presents an optimal “bound-and-scan” algorithm that may be used in conjunction with these approximate procedures.
Cited by 118 works. doi:10.1287/opre.17.4.600
Authors
References
- Outline of an algorithm for integer solutions to linear programs
- An Algorithm for the Traveling Salesman Problem
- An Automatic Method for Solving Discrete Programming Problems
- Introduction to Operations Research
- An Additive Algorithm for Solving Linear Programs with Zero-One Variables
- Integer Programming: Methods, Uses, Computations
- A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
- AN ALL-INTEGER INTEGER PROGRAMMING ALGORITHM
- Approximate Solutions to the Three-Machine Scheduling Problem
- Plant Location Under Economies-of-Scale—Decentralization and Computation