Heuristic Procedures for 0-1 Integer Programming.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1987
Accession Number
ADA181431

Entities

People

  • Frederick Stanton Hillier
  • Kadriye A. Ercikan

Organizations

  • Stanford University

Tags

Communities of Interest

  • Air Platforms
  • C4I
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Command And Control
  • Computer Programming
  • Evolutionary Algorithms
  • Heuristic Methods
  • Integer Programming
  • Linear Programming
  • Mathematical Programming
  • Operations Research
  • Optimization
  • Parametric Programming
  • Plastic Explosives
  • Simplex Method

Fields of Study

  • Mathematics

Readers

  • Operations Research