Combinatorial optimization and VLSI-design
Exemplifying the use of combinatorial optimization this paper treats the via minimization problem in VLSI-design. After describing the technical foundations, via minimization is formulated as a max cut problem. The complexity of this problem is discussed and several algorithms for its solution are described: construction heuristics like a greedy method, a tree heuristic and random cut generation. Further improvement methods are outlined like 1-opt and 2-opt methods and the Lin-Kernighan heuristic. These heuristics are evaluated by 12 test problems from practice. Finally, a branch and cut approach for solving the max cut problem is outlined as an exact solution method. A last table shows the optimum solution values of the 12 test problems. For the entire collection see [Zbl 0833.00027].
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- Via Minimization with Pin Preassignments and Layer Preference
- Some combinatorial optimization problems arising from VLSI circuit design
- Combinatorial optimization in VLSI design
- scientific article; zbMATH DE number 956793
- Multilevel optimization in VLSICAD
- A heuristic and an exact method for the gate matrix connection cost minimization problem
- Via Minimization with Pin Preassignments and Layer Preference
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- scientific article; zbMATH DE number 49142 (Why is no real title available?)
- Digital Circuit Optimization via Geometric Programming
- VLSI circuit performance optimization by geometric programming
- Efficient preprocessing for VLSI optimization problems
This page was built for publication: Combinatorial optimization and VLSI-design
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4353133)
