Analyzing and exploiting the structure of the constraints in the ILP approach to the scheduling problem
- 1 December 1994
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Very Large Scale Integration (VLSI) Systems
- Vol. 2 (4) , 456-471
- https://doi.org/10.1109/92.335014
Abstract
In integer linear programming (ILP), formulating a "good" model is of crucial importance to solving that model. In this paper, we begin with a mathematical analysis of the structure of the assignment, timing, and resource constraints in high-level synthesis, and then evaluate the structure of the scheduling polytope described by these constraints. We then show how the structure of the constraints can be exploited to develop a well-structured ILP formulation, which can serve as a solid theoretical foundation for future improvement. As a start in that direction, we also present two methods to further tighten the formulation. The contribution of this paper is twofold: 1) it provides the first in-depth formal analysis of the structure of the constraints, and it shows how to exploit that structure in a well-designed ILP formulation, and 2) it shows how to further improve a well-structured formulation by adding new valid inequalities.Keywords
This publication has 23 references indexed in Scilit:
- An Integrated and Accelerated ILP Solution for Scheduling, Module Allocation, and Binding in Datapath SynthesisPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- A cost function based optimization technique for scheduling in data path synthesisPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Optimal scheduling and allocation of embedded VLSI chipsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Scheduling in Computer and Manufacturing SystemsPublished by Springer Nature ,1993
- Optimal synthesis of multichip architecturesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- Algorithmic and Register-Transfer Level Synthesis: The System Architect’s WorkbenchPublished by Springer Nature ,1990
- Integer and Combinatorial OptimizationPublished by Wiley ,1988
- A cutting plane algorithm for minimum perfect 2-matchingsComputing, 1987
- Solving Large-Scale Zero-One Linear Programming ProblemsOperations Research, 1983
- A Formal Method for the Specification, Analysis, and Design of Register-Transfer Level Digital LogicIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1983