Accession Number:

ADA181431

Title:

Heuristic Procedures for 0-1 Integer Programming.

Descriptive Note:

Technical rept.,

Corporate Author:

STANFORD UNIV CA SYSTEMS OPTIMIZATION LAB

Report Date:

1987-03-01

Pagination or Media Count:

81.0

Abstract:

The limited success of exact algorithms for solving integer programming problems has encouraged the development of heuristic procedures for efficiently obtaining solutions that are at least close to optimal. This document presents three heuristic procedures for 0-1 integer programming problems having only inequality constraints. These procedures are based on Hilliers previous heuristic procedures for general integer linear programming. All three were successfully run on problems with up to 500 variables with only modest execution times. The quality of the solutions for these problems were, in general, very good and often were optimal. When the best of the solutions obtained by the three procedures was taken, the final solution was optimal for 24 of 45 randomly generated problems. These procedures can be used for problems that are too large to be computationally feasible for exact algorithms. In addition, they can be useful for smaller problems by quickly providing an advanced starting solution for an exact algorithm.

Subject Categories:

  • Operations Research
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE