Accession Number:

ADA106027

Title:

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

Descriptive Note:

Technical rept.,

Corporate Author:

STANFORD UNIV CA SYSTEMS OPTIMIZATION LAB

Personal Author(s):

Report Date:

1981-08-01

Pagination or Media Count:

66.0

Abstract:

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 authors Bound-and-Scan algorithm and Faaland and Hilliers 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 latters efficiency in locating solutions whose objective function value is within a specified percentage of that for the optimal solution.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE