A MIXED-INTEGER LINEAR PROGRAMMING PROBLEM WHICH IS EFFICIENTLY SOLVABLE

FIELD GROUP SUB-GROUP Algorithms, linear programming, mathematical programming, graph theory, shortest paths, combinatorial optimization 19 ABSTRACT (Continue on reverse if necessary and identify by block number) Efficient algorithms are known for the simple linear programming problem where each in-equality is in the form xj-xi. a. Furthermore, these techniques extend to the integer linear programming variant of theiroblem. This paper gives an efficient solution to the mixed-integer linear programming variant where some, but not necessarily all, of the un-knoi.ls ire requiired to be integers. The algorithm we develop 2 is based on a graph repre-sentation of the constraint system and runs in O(IVIIEI + IVI 1SlV I) time. It has several aippli,iti ns including optimal retiming of synchronous circuitry, VLSI layout compactio