RECENT COMPUTATIONAL EXPERIENCE WITH THREE CLASSES OF INTEGER LINEAR PROGRAMS,
Abstract
In AD-655 444 the author presented an implicitly enumerative algorithm for integer linear programming that involves the repeated solution of smaller continuous linear programs. Both primal and dual interpretations of the continuous programs are used in an essential way. The computational experience reported there shows that use of the imbedded linear program dramatically improves a 'bare bones' implicit enumeration procedure, and suggests that the resulting algorithm is significantly more efficient than the previously reported enumerative algorithms for which comparable computational experience is available. This note presents further computational results concerning how fast solution time increases with the number of variables. This question has been investigated in the range of 30-90 variables for three important classes of problems: set covering, optimal routing in networks, and knapsack with several constraints.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1967
- Accession Number
- AD0660116
Entities
People
- A. M. Geoffrion
Organizations
- RAND Corporation