A Mixed-Integer Linear Programming Problem which is Efficiently Solvable.

Abstract

Much research has centered on the problem of finding shortest paths in graphs. It is well known that there is a direct correspondence between the single source shortest-paths problem and the following simple linear programming problems: Let S be a set of linear inequalities of the form x sub j - x sub i < or = (a sub ij, where the x sub i are unknowns and the a sub ij are given real constants. Determine a set of values for the x sub i such that the inequalities in S are satisfied, or determine that no such values exist. This paper considers the mixed-integer linear programming variant of this problem in which some (but not necessarily all) of the x sub i are required to be integers. The problem arises in the context of synchronous circuit optimization but it has applications to PERT scheduling and VLSI layout compaction as well. Keywords: Algorithms, Combinatorial optimization.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1987
Accession Number
ADA191028

Entities

People

  • Charles Leiserson
  • James B. Saxe

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Computer Programming
  • Computer Science
  • Computers
  • Evolutionary Algorithms
  • Graph Theory
  • Inequalities
  • Information Processing
  • Integer Programming
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • Numbers
  • Optimization
  • Pert
  • Real Numbers

Fields of Study

  • Mathematics

Readers

  • Analytical Mechanics
  • Operations Research