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