Accession Number : ADA181431

Title :   Heuristic Procedures for 0-1 Integer Programming.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CA SYSTEMS OPTIMIZATION LAB

Personal Author(s) : Ercikan,Kadriye A ; Hillier,Frederick S

PDF Url : ADA181431

Report Date : Mar 1987

Pagination or Media Count : 81

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 Hillier's 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.

Descriptors :   *HEURISTIC METHODS, *INTEGER PROGRAMMING, SOLUTIONS(GENERAL), ALGORITHMS, COMPUTER PROGRAMMING, PROBLEM SOLVING

Subject Categories : Operations Research
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE