# 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.

# Descriptors:

# Subject Categories:

- Theoretical Mathematics