nach oben

Erschienen in:

2012 | OriginalPaper | Buchkapitel

29. Global Approaches for Facility Layout and VLSI Floorplanning

verfasst von : Miguel F. Anjos, Frauke Liers

Erschienen in: Handbook on Semidefinite, Conic and Polynomial Optimization

Verlag: Springer US

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This chapter provides an overview of conic optimization models for facility layout and VLSI floorplanning problems. We focus on two classes of problems to which conic optimization approaches have been successfully applied, namely the single-row facility layout problem, and fixed-outline floorplanning in VLSI circuit design. For the former, a close connection to the cut polytope has been exploited in positive semidefinite and integer programming approaches. In particular, the semidefinite optimization approaches can provide global optimal solutions for instances with up to 40 facilities, and tight global bounds for instances with up to 100 facilities. For the floorplanning problem, a conic optimization model provided the first non-trivial lower bounds in the literature.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Computational Approaches to Max-Cut

Nächstes Kapitel Euclidean Distance Matrices and Applications

Adams, E.C.: A semidefinite programming model for the facility layout problem. Master’s thesis, University of Waterloo (2010)

Amaral, A.R.S.: On the exact solution of a facility layout problem. Eur. J. Oper. Res. 173(2), 508–518 (2006)

Amaral, A.R.S.: An exact approach for the one-dimensional facility layout problem. Oper. Res. 56(4), 1026–1033 (2008)

Amaral, A.R.S.: A new lower bound for the single row facility layout problem. Discrete Appl. Math. 157(1), 183–190 (2009)

Amaral, A.R.S.: On the exact solution of a facility layout problem. Discr. Appl. Math. 157(1), 183–190 (2009)

Amaral, A.R.S., Letchford, A.N.: A polyhedral approach to the single-row facility layout problem. Technical report, Department of Management Science, Lancaster University (March 2008)

Anjos, M.F., Kennings, A., Vannelli, A.: A semidefinite optimization approach for the single-row layout problem with unequal dimensions. Discrete Optim. 2(2), 113–122 (2005)

Anjos, M.F., Vannelli, A.: Globally optimal solutions for large single-row facility layout problems. Technical report, University of Waterloo (2006)

Anjos, M.F., Vannelli, A.: A new mathematical-programming framework for facility-layout design. INFORMS J. Comp. 18(1), 111–118 (2006)

10.

Anjos, M.F., Vannelli, A.: Computing globally optimal solutions for single-row layout problems using semidefinite programming and cutting planes. INFORMS J. Comp. 20(4), 611–617 (2008)

11.

Anjos, M.F., Yen, G.: Provably near-optimal solutions for very large single-row facility layout problems. Optim. Methods Softw. 24(4), 805–817 (2009)

12.

Barahona, F., Mahjoub, A.R.: On the cut polytope. Mathematical Programming 36, 157–173, 1986.

13.

Bernardi, S.: A three-stage mathematical-programming method for the multi-floor facility layout problem. Master’s thesis, University of Waterloo (2010)

14.

Borchers, B.: CSDP, a C library for semidefinite programming. Optim. Methods Softw. 11/12(1-4), 613–623 (1999)

15.

Buchheim, C., Liers, F., Oswald, M.: Speeding up IP-based algorithms for constrained quadratic 0-1 optimization. Mathematical Programming (Series B) 124(1-2), 513–535 (2010)

16.

Buchheim, C., Wiegele, A., Zheng, L.: Exact algorithms for the quadratic linear ordering problem. INFORMS J. on Computing 2(1), 168–177 (2010)

17.

Caprara, A., Oswald, M., Reinelt, G., Schwarz, R., Traversi, E.: Optimal linear arrangements using betweenness variables. Mathematical Programming (Series C) 3(3), 261–280 (2011)

18.

Castillo, I., Sim, T.: A spring-embedding approach for the facility layout problem. J. Oper. Res. Soc. 55, 73–81 (2004)

19.

Castillo, I., Westerlund, J., Emet, S., Westerlund, T.: Optimization of block layout design problems with unequal areas: A comparison of MILP and MINLP optimixation methods. Computers and Chemical Engineering 30(1), 54–69 (2005)

20.

Castillo, I., Westerlund, T.: An ε-accurate model for optimal unequal-area block layout design. Comput. Oper. Res. 32(3), 429–447 (2005)

21.

Çela, E.: The Quadratic Assignment Problem. In: Combinatorial Optimization, vol. 1. Kluwer Academic Publishers, Dordrecht (1998)

22.

Charon, I., Hudry, O.: An updated survey on the linear ordering problem for weighted or unweighted tournaments. Ann. Oper. Res. 175, 107–158 (2010)

23.

Christof, T., Oswald, M., Reinelt, G.: Consecutive ones and a betweenness problem in computational biology. In Proceedings of the 6th Conference on Integer Programming and Combinatorial Optimization, Springer-Verlag Lecture Notes in Computer Science 1412 (1998)

24.

de Alvarenga, A.G., Negreiros-Gomes, F.J., Mestria, M.: Metaheuristic methods for a class of the facility layout problem. J. Intell. Manuf. 11, 421–430 (2000)

25.

De Simone, C.: The cut polytope and the boolean quadric polytope. Discrete Mathematics 79, 71–75 (1989)

26.

Deza, M.M., Laurent, M.: Geometry of Cuts and Metrics, vol. 15 of Algorithms and Combinatorics. Springer-Verlag, Berlin (1997)

27.

Díaz, J., Petit, J., Serna, M.: A survey on graph layout problems. ACM Computing Surveys 34, 313–356 (2002)

28.

Foulds, L.R.: Graph Theory Applications. Springer-Verlag, New York (1991)

29.

Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach. 42(6), 1115–1145 (1995)

30.

Grötschel, M., Jünger, M., Reinelt, G.: Facets of the linear ordering polytope. Mathematical Programming 33, 43–60 (1985)

31.

Hall, K.M.: An r-dimensional quadratic placement algorithm. Management Sciences 17, 219–229 (1970)

32.

Hammer, P.L.: Some network flow problems solved with pseudo-boolean programming. Operations Research 13, 388–399 (1965)

33.

Helmberg, C., Kiwiel, K.C.: A spectral bundle method with bounds. Math. Program. 93(2, Ser. A), 173–194 (2002)

34.

Helmberg, C., Rendl, F.: A spectral bundle method for semidefinite programming. SIAM J. Optim. 10(3), 673–696 (2000)

35.

Heragu, S.S.: Facilities Design. iUniverse, second edition (2006)

36.

Heragu, S.S., Alfa, A.S.: Experimental analysis of simulated annealing based algorithms for the layout problem. European J. Oper. Res. 57(2), 190–202 (1992)

37.

Heragu, S.S., Kusiak, A.: Machine layout problem in flexible manufacturing systems. Oper. Res. 36(2), 258–268 (1988)

38.

Heragu, S.S., Kusiak, A.: Efficient models for the facility layout problem. European J. Oper. Res. 53, 1–13 (1991)

39.

Hungerländer, P., Rendl, F.: Semidefinite relaxations of ordering problems. Technical report, Alpen-Adria-Universität Klagenfurt (August 2010)

40.

Jankovits, I.: An improved convex optimization model for two-dimensional facility layout. Master’s thesis, University of Waterloo (2006)

41.

Karp, R.M., Held, M.: Finite-state processes and dynamic programming. SIAM J. Appl. Math. 15, 693–718 (1967)

42.

Kim, S., Kojima, M., Yamashita, M.: Second order cone programming relaxation of a positive semidefinite constraint. Optim. Methods Softw. 18(5), 535–541 (2003)

43.

Koopmans, T.C., Beckmann, M.: Assignment problems and the location of economic activities. Econometrica 25, 53–76 (1957)

44.

Kumar, K.R., Hadjinicola, G.C., Lin, T.: A heuristic procedure for the single-row facility layout problem. European J. Oper. Res. 87(1), 65–73 (1995)

45.

Lewis, M., Alidaee, B., Glover, F., Kochenberger, G.: A note on xQx as a modelling and solution framework for the linear ordering problem. International Journal of Operational Research 5(2), 152–162 (2009)

46.

Liers, F., Jünger, M., Reinelt, G., Rinaldi, G.: Computing Exact Ground States of Hard Ising Spin Glass Problems by Branch-and-Cut, pp. 47–68. New Optimization Algorithms in Physics. Wiley-VCH (2004)

47.

Liu, W., Vannelli, A.: Generating lower bounds for the linear arrangement problem. Discrete Appl. Math. 59(2), 137–151 (1995)

48.

Lovász, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1, 166–190 (1991)

49.

Love, R.F., Wong, J.Y.: On solving a one-dimensional space allocation problem with integer programming. INFOR 14(2), 139–143 (1976)

50.

Luo, C., Anjos, M.F., Vannelli, A.: A nonlinear optimization methodology for VLSI fixed-outline floorplanning. J. Comb. Optim. 16(4), 378–401 (2008)

51.

Mavridou, T.D., Pardalos, P.M.: Simulated annealing and genetic algorithms for the facility layout problem: a survey. Comput. Optim. Appl., 7(1), 111–126 (1997)

52.

Meller, R.D., Chen, W., Sherali, H.D.: Applying the sequence-pair representation to optimal facility layout designs. Oper. Res. Lett. 35(5), 651–659 (2007)

53.

Meller, R.D., Gau, K.Y.: The facility layout problem: recent and emerging trends and perspectives. Journal of Manufacturing Systems 15, 351–366 (1996)

54.

Meller, R.D., Narayanan, V., Vance, P.H.: Optimal facility layout design. Oper. Res. Lett. 23(3-5), 117–127 (1998)

55.

Montreuil, B.: A modelling framework for integrating layout design and flow network design. In: White, J.A., Pence, I.W. (eds.) Progress in Material Handling and Logistics, vol. 2, pp. 95–116. Springer-Verlag (1991)

56.

Murata, H., Fujiyoshi, K., Nakatake, S., Kajitani, Y.: VLSI module placement based on rectangle-packing by the sequence-pair. IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems 15(12), 1518–1524 (1996)

57.

Murata, H., Kuh, E.S.: Sequence-pair based placement method for hard/soft/pre-placed modules. Proceedings of the International Symposium on Physical Design, pp. 167–172 (1998)

58.

Picard, J.-C., Queyranne, M.: On the one-dimensional space allocation problem. Oper. Res. 29(2), 371–391 (1981)

59.

Reinelt, G.: The Linear Ordering Problem: Algorithms and Applications. Heldermann Verlag (1985)

60.

Rendl, F., Rinaldi, G., Wiegele, A.: A branch and bound algorithm for Max-Cut based on combining semidefinite and polyhedral relaxations. In Integer programming and combinatorial optimization, vol. 4513 of Lecture Notes in Computer Science, pp. 295–309. Springer Verlag, Berlin (2007)

61.

Romero, D., Sánchez-Flores, A.: Methods for the one-dimensional space allocation problem. Comput. Oper. Res. 17(5), 465–473 (1990)

62.

Sait, S.M., Youssef, H.: VLSI physical design automation: theory and practice. IEEE Press, New York, USA (1995)

63.

Sanjeevi, S., Kianfar, K.: A polyhedral study of triplet formulation for single row facility layout problem. Discrete Appl. Math. 158(16), 1861–1867 (2010)

64.

Sherali, H.D., Fraticelli, B.M.P., Meller, R.D.: Enhanced model formulation for optimal facility layout. Oper. Res. 51(4), 629–644 (2003)

65.

Simmons, D.M.: One-dimensional space allocation: An ordering algorithm. Oper. Res. 17, 812–826 (1969)

66.

Simmons, D.M.: A further note on one-dimensional space allocation. Oper. Res. 19, p. 249 (1971)

67.

Singh, S.P., Sharma, R.R.K.: A review of different approaches to the facility layout problems. Intl J. Adv. Manuf. Tech. 30(5–6), 425–433 (2006)

68.

Suryanarayanan, J.K., Golden, B.L., Wang, Q.: A new heuristic for the linear placement problem. Computers & Operations Research 18(3), 255–262 (1991)

69.

Takouda, P.L., Anjos, M.F., Vannelli, A.: Global lower bounds for the VLSI macrocell floorplanning problem using semidefinite optimization. In Proceedings of IWSOC 2005, pp. 275–280 (2005)

70.

Wong, D.F., Liu, C.L.: A new algorithm for floorplan design. In: Proc. of ACM/IEEE Design Automation Conf., pp. 101–107 (1986)

71.

Xie, W., Sahinidis, N.V.: A branch-and-bound algorithm for the continuous facility layout problem. Comput. & Chem. Eng. 32, 1016–1028 (2008)

Titel: Global Approaches for Facility Layout and VLSI Floorplanning
verfasst von: Miguel F. Anjos
Frauke Liers
Verlag: Springer US
Buch: Handbook on Semidefinite, Conic and Polynomial Optimization
Print ISBN: 978-1-4614-0768-3

Electronic ISBN: 978-1-4614-0769-0

Copyright-Jahr: 2012
DOI: https://doi.org/10.1007/978-1-4614-0769-0_29