Accession Number:

ADA159496

Title:

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

Descriptive Note:

Interim research rept.,

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

Report Date:

1985-07-01

Pagination or Media Count:

16.0

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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE