A Mixed Integer Linear Programming Problem Which is Efficiently Solvable
Efficient algorithms are known for the simple linear programming problem where each inequality is of the form xj-xi<=aij. Furthermore, these techniques extend to the integer linear programming variant of the problem. This paper gives an efficient solution to the mixed-integer linear programming v...
| Main Authors: | , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149093 |
| _version_ | 1826197331045777408 |
|---|---|
| author | Leiserson, Charles E. Saxe, James B. |
| author_facet | Leiserson, Charles E. Saxe, James B. |
| author_sort | Leiserson, Charles E. |
| collection | MIT |
| description | Efficient algorithms are known for the simple linear programming problem where each inequality is of the form xj-xi<=aij. Furthermore, these techniques extend to the integer linear programming variant of the problem. This paper gives an efficient solution to the mixed-integer linear programming variant where some, but not necessarily all, of the unknowns are required to be integers. The algorithm we develop is based on a graph representation of the constraint system and runs in O(|V||E|+|V|62lh|V|) time. It has several applications including optimal retiming of synchronous circuitry, VLSI layout compaction in the presence of power and ground buses, and PERT scheduling with periodic constraints. |
| first_indexed | 2024-09-23T10:46:22Z |
| id | mit-1721.1/149093 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T10:46:22Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1490932023-03-30T03:59:27Z A Mixed Integer Linear Programming Problem Which is Efficiently Solvable Leiserson, Charles E. Saxe, James B. Efficient algorithms are known for the simple linear programming problem where each inequality is of the form xj-xi<=aij. Furthermore, these techniques extend to the integer linear programming variant of the problem. This paper gives an efficient solution to the mixed-integer linear programming variant where some, but not necessarily all, of the unknowns are required to be integers. The algorithm we develop is based on a graph representation of the constraint system and runs in O(|V||E|+|V|62lh|V|) time. It has several applications including optimal retiming of synchronous circuitry, VLSI layout compaction in the presence of power and ground buses, and PERT scheduling with periodic constraints. 2023-03-29T14:26:45Z 2023-03-29T14:26:45Z 1985-07 https://hdl.handle.net/1721.1/149093 MIT-LCS-TM-284 application/pdf |
| spellingShingle | Leiserson, Charles E. Saxe, James B. A Mixed Integer Linear Programming Problem Which is Efficiently Solvable |
| title | A Mixed Integer Linear Programming Problem Which is Efficiently Solvable |
| title_full | A Mixed Integer Linear Programming Problem Which is Efficiently Solvable |
| title_fullStr | A Mixed Integer Linear Programming Problem Which is Efficiently Solvable |
| title_full_unstemmed | A Mixed Integer Linear Programming Problem Which is Efficiently Solvable |
| title_short | A Mixed Integer Linear Programming Problem Which is Efficiently Solvable |
| title_sort | mixed integer linear programming problem which is efficiently solvable |
| url | https://hdl.handle.net/1721.1/149093 |
| work_keys_str_mv | AT leisersoncharlese amixedintegerlinearprogrammingproblemwhichisefficientlysolvable AT saxejamesb amixedintegerlinearprogrammingproblemwhichisefficientlysolvable AT leisersoncharlese mixedintegerlinearprogrammingproblemwhichisefficientlysolvable AT saxejamesb mixedintegerlinearprogrammingproblemwhichisefficientlysolvable |