EFFICIENT SUBOPTIMAL ALGORITHMS FOR INTEGER LINEAR PROGRAMMING WITH AN INTERIOR.

Abstract

The paper presents and evaluates some new suboptimal algorithms for the pure integer linear programming problem having only inequality constraints. The computation time required by these algorithms (after obtaining the optimal noninteger solution) has been only a small fraction of that required by the simplex method. Furthermore, the solution obtained by the better algorithms consistently has been close to optimal and frequently has actually been optimal. Plans for generalizing these algorithms also are outlines. A companion paper presents an optimal 'bound-and-scan' algorithm that would be used in conjuection with these suboptimal algorithms. (Author)

Document Details

Document Type
Technical Report
Publication Date
Aug 12, 1966
Accession Number
AD0640382

Entities

People

  • Frederick Stanton Hillier

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computational Complexity
  • Computations
  • Computer Programming
  • Evolutionary Algorithms
  • Heuristic Methods
  • Inequalities
  • Integer Programming
  • Linear Programming
  • Mathematical Analysis
  • Mathematics
  • Simplex Method

Readers

  • Operations Research