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 problem. 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 rea 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1985
Accession Number
ADA159496

Entities

People

  • C. E. Leiserson
  • J. B. Saxe

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Computer Science
  • Computers
  • Evolutionary Algorithms
  • Graph Theory
  • Inequalities
  • Information Processing
  • Integer Programming
  • Integrated Circuits
  • Linear Programming
  • Massachusetts
  • Mathematical Programming
  • Military Research
  • Optimization
  • Real Numbers
  • Very Large Scale Integration

Fields of Study

  • Mathematics

Readers

  • Operations Research