DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
Accession Number:
ADA191028
Title:
A Mixed-Integer Linear Programming Problem which is Efficiently Solvable.
Corporate Author:
MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE
Report Date:
1987-10-01
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.
Descriptive Note:
Technical rept.,
Pages:
0013
Contract Number:
N00014-80-C-0622
Contract Number 2:
N00014-76-C-0370
File Size:
0.91MB
