Integer Linear Programming Models for Global Routing

References

• Aarts E. H. L., Laarhoven P. J. M. V. Statistical cooling: A general approach to combinatorial optimization problems. Phillips J. Res. (1985) 4:193–226Google Scholar
• Alpert C. J., Hrkic M., Hu J., Kahng A. B., Lillis J., Liu B., Quay S. T., Sapatnekar S. S., Sullivan A. J., Villarrubia P. Buffered Steiner trees for difficult instances. Proc. Internat. Sympos. Physical Design (2001) (ACM Press, New York) 4–9Crossref, Google Scholar
• Andersen E. D., Gondzio J., Meszaros C., Xu X.Implementation of Interior-Point Methods for Large Scale Linear Programming (1996) (Kluwer Academics Publishers, Dordrecht, The Netherlands) Google Scholar
• Areibi S., Xie M., Vannelli A. An efficient Steiner tree algorithm for VLSI global routing. Proc. Canadian Conf. Electrical and Comput. Engrg. (2001) (IEEE Press, Toronto, Ontario, Canada) 1067–1072Crossref, Google Scholar
• Behjat L., Kucar D., Vannelli A. A novel eigenvector technique for large scale combinatorial problems in VLSI layout. J. Combin. Optim. (2002) 6:271–286Crossref, Google Scholar
• Bertsekas D. P.Nonlinear Programming (1995) (Athena Scientific, Belmont, MA) Google Scholar
• Chiang C., Wong C. K., Sarrafzadeh M. A weighted Steiner tree-based global router with simultaneous length and density minimization. IEEE Trans. Comput.-Aided Design Integrated Circuits Systems (1994) 13:1461–1469Crossref, Google Scholar
• Cong J., Madden P. H. Performance driven routing with multiple sources. IEEE Trans. Comput.-Aided Design Integrated Circuits Systems (1997) 16:410–419Crossref, Google Scholar
• Cong J., Kahng A. B., Leung K. Efficient algorithms for minimum shortest path Steiner arborescence problem with application to VLSI physical design. IEEE Trans. Comput.-Aided Design Integrated Circuits Systems (1998) 17:24–39Crossref, Google Scholar
• Dees W. A., Karger P. G. Automated rip-up and reroute techniques. Proc. 19th IEEE/ACM Design Automation Conf. (1982) (IEEE Press, Piscataway, NJ) 432–439Crossref, Google Scholar
• Etawil H., Areibi S., Vannelli A. Attractor-repeller approach for global placement. IEEE/ACM Internat. Conf. Comput.-Aided Design (1999) (IEEE Press, Piscataway, NJ) 7–11Crossref, Google Scholar
• Floundas C. A.Nonlinear and Mixed-Integer Optimization (1995) (Oxford University Press, Oxford, UK) Crossref, Google Scholar
• Hadlock F. Finding a maximum cut of a planar graph in polynomial time. SIAM J. Comput. (1975) 4:221–225Crossref, Google Scholar
• Hanan M. Steiner’s problem with rectilinear distance. SIAM J. Appl. Math. (1966) 14:255–265Crossref, Google Scholar
• Hu J., Sapatnekar S. S. A timing-constrained simultaneous global routing algorithm. IEEE Trans. Comput.-Aided Design Integrated Circuits Systems (2002) 21:1025–1036Crossref, Google Scholar
• Hu T. C., Shing M. T. A decomposition algorithm for circuit routing. (1985) (IEEE Press, New York) 144–152Crossref, Google Scholar
• Karmarkar N. A new polynomial-time algorithm for linear programming. Combinatorica (1984) 4:373–395Crossref, Google Scholar
• Karp R. M.Reducibility Among Combinatorial Problems (1972) (Plenum Press, New York) Crossref, Google Scholar
• Kastner R., Bozorgzadeh E., Sarrafzadeh M. An exact algorithm for coupling-free routing. Proc. Internat. Sympos. Physical Design (2001) (ACM Press, New York) 10–15Crossref, Google Scholar
• Kozminski K. Benchmarks for layout synthesis-evaluation and current status. Proc. 28th ACM/IEEE Design Automation Conf. (1991) (IEEE Press, Piscataway, NJ) 265–270Crossref, Google Scholar
• Kozminski K. Benchmarks for layout synthesis—Evolution and current status. (2004) (ACM Sigda, New York) . http://www.sigda.org/Archives/ProceedingArchives/Dac/Dac91/papers/1991/dac91/17_3/17_3.htmGoogle Scholar
• Lee C. Y. An algorithm for path connection and its application. IRE Trans. Electronic Comput. (1961) 10:346–365Crossref, Google Scholar
• Lengauer T.Combinatorial Algorithms for Integrated Circuit Layout (1990) (Wiley, New York) Crossref, Google Scholar
• Lengauer T., Lungering M. Provably good global routing of integrated circuits. SIAM J. Optim. (2000) 11:1–30Crossref, Google Scholar
• Lundy M. Convergence of an annealing algorithm. Math. Programming (1986) 34:111–124Crossref, Google Scholar
• Madden P. Standard cell benchmark circuits. BLAC CAD Binghamton Laboratory for Algorithms, Circuits, and Computer-Aided Design (2004) (Binghamton University, Binghamton, NY) . http://vlsicad.cs.binghamton.edu/benchmarks.htmlGoogle Scholar
• Mehrotra S. On the implementation of a primal-dual interior-point method. SIAM J. Optim. (1992) 2:575–601Crossref, Google Scholar
• Ng A. P., Raghavan P., Thompson C. D. Experimental results for a linear program global router. Comput. Artificial Intelligence (1987) 6:130–143Google Scholar
• Raghavan P. Probabilistic construction of deterministic algorithms: Approximating packing integer programs. J. Comput. Sci. (1988) 37:130–143Google Scholar
• Raghavan P., Thompson C. D. Multi-terminal global routing: A deterministic approximation scheme. Algorithmica (1991) 6:73–82Crossref, Google Scholar
• Sherwani N.Algorithms for VLSI Physical Design Automation (1999) (Kluwer Academic Publishers, Dordrecht, The Netherlands) Google Scholar
• Shragowitz E., Keel S. A global router on a multi-commodity flow model. Interaction (1987) 5:3–16Google Scholar
• Soukup J. Fast maze router. Proc. 15th Design Automation Conf. (1978) (IEEE Press, Piscataway, NJ) 100–102Crossref, Google Scholar
• Vanderbei R. LOQO: An interior point code for quadratic programming. (1998) . Technical report, Department of Operations Research and Financial Engineering, Princeton University, Princeton, NJGoogle Scholar
• Vanderbei R., Shanno D. F. An interior point algorithm for non-convex nonlinear programming. (1997) . Technical Report SOR-97-21, School of Engineering and Operational Research, Princeton University, Princeton, NJGoogle Scholar
• Vannelli A. An adaptation of the interior point method for solving the global routing problem. IEEE Trans. Comput.-Aided Design Integrated Circuits Systems (1991) 10:193–203Crossref, Google Scholar
• Vecchi M. P., Kirkpatrick A. Global wiring by simulated annealing. IEEE Trans. Comput.-Aided Design Integrated Circuits Systems (1983) 2:215–222Crossref, Google Scholar