Reducing the complexity of ILP formulations for synthesis
A. Mignotte, O. Peyran · 2002
Integer linear programming (ILP) is commonly used in high level and system level synthesis. It is an NP complete problem (in general cases). There exist some tool's that give an optimal solution for small ILP formulations. Nevertheless, these tools may not give solutions for complex formulations. We present a solution to overcome the problem of complexity in ILP formulations. We propose a partitioning methodology based on a constraint graph representing all the constraints included in any ILP formulation. To direct the partitioning, the constraint graph nodes are grouped to represent data flow graph (DFG) nodes. This reduced constraint graph can be used to partition any ILP formulation based on DFG. We illustrate this method on ILP formulation for scheduling. Results on ILP scheduling formulations are promising.