A Mixed-Integer Linear Programming Problem which is Efficiently Solvable.
MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE
Pagination or Media Count:
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.
- Operations Research