Accession Number : AD0660116
Title : RECENT COMPUTATIONAL EXPERIENCE WITH THREE CLASSES OF INTEGER LINEAR PROGRAMS,
Corporate Author : RAND CORP SANTA MONICA CALIF
Personal Author(s) : Geoffrion,A. M.
Report Date : OCT 1967
Pagination or Media Count : 10
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.
Descriptors : (*LINEAR PROGRAMMING, MATHEMATICAL MODELS), NETWORKS, OPTIMIZATION, SCHEDULING, ALGORITHMS
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE