AN OPTIMAL BOUND-AND-SCAN ALGORITHM FOR INTEGER LINEAR PROGRAMMING.

Abstract

A new algorithm for solving the pure integer linear programming problem is presented and evaluated. Roughly speaking this algorithm proceeds by obtaining tight bounds or conditional bounds on the relevant values of the respective variables, and then identifying a sequence of constantly improving feasible solutions by scanning the relevant solutions. Encouraging computational experience is reported that suggests that this algorithm should compare favorably in efficiency with existing algorithms. Plans for investigating ways of further increasing the efficiency of the algorithm and of extending it to more general problems also are outlined. (Author)

Document Details

Document Type
Technical Report
Publication Date
Aug 19, 1966
Accession Number
AD0640215

Entities

People

  • Frederick Stanton Hillier

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Efficiency
  • Evolutionary Algorithms
  • Heuristic Methods
  • Integer Programming
  • Linear Programming
  • Mathematics
  • Scanning
  • Sequences

Readers

  • Operations Research
  • Systems Analysis and Design