Accession Number : ADA191028

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

Descriptive Note : Technical rept.,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s) : Leiserson, Charles ; Saxe, James B

PDF Url : ADA191028

Report Date : Oct 1987

Pagination or Media Count : 13

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.

Descriptors :   *ALGORITHMS, *LINEAR PROGRAMMING, COMBINATORIAL ANALYSIS, COMPACTING, CONSTANTS, GRAPHS, INEQUALITIES, LINEAR SYSTEMS, NUMBERS, OPTIMIZATION, PERT, SCHEDULING, PROBLEM SOLVING

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE