Beating the SDP bound for the floor layout problem: a simple combinatorial idea

References

• Amaral A. 2008. An exact approach to the one-dimensional facility layout problem. Oper Res. 56(4):1026–1033.
   Web of Science ®Google Scholar
• Amaral A. 2009. A new lower bound for the single row facility layout problem. Disc Appl Math. 157: 183–190.
   Web of Science ®Google Scholar
• Amaral AR. 2006. On the exact solution of a facility layout problem. Eur J Oper Res. 173: 508–518.
   Web of Science ®Google Scholar
• Amaral AR, Letchford A. 2012. A polyhedral approach to the single row facility layout problem. Math Program Series A. 141(1):453–477.
   Web of Science ®Google Scholar
• Anjos M, Kennings A, Vannelli A. 2005. A semidefinite optimization approach for the single-row layout problem with unequal dimensions. Disc Opt. 2: 113–122.
   Google Scholar
• Anjos M, Vannelli A. 2006. A new mathematical-programming framework for facility-layout design. INFORMS J Comput. 18(1):111–118.
   Web of Science ®Google Scholar
• Anjos M, Vannelli A. 2008. Computing globally optimal solutions for single-row layout problems using semidefinite programming and cutting planes. INFORMS J Comput. 20(4):611–617.
   Web of Science ®Google Scholar
• Anjos M, Yen G. 2009. Provably near-optimal solutions for very large single-row facility layout problems. Opt Methods Softw. 24(4–5):805–817.
   Web of Science ®Google Scholar
• Balas E, Ceria S, Cornuéjols G. 1993. A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math Prog. 58: 295–324.
   Web of Science ®Google Scholar
• Bazaraa M. 1975. Computerized layout design: a branch and bound approach. AIIE Trans. 7(4):432–438.
   Google Scholar
• Bernardi S. 2010. A three-stage mathematical-programming method for the multi-floor facility layout problem [dissertation]. Waterloo (ON): University of Waterloo.
   Google Scholar
• Bernardi S, Anjos M. 2013. A two-stage mathematical-programming method for the multi-floor facility layout problem. J Oper Res Soc. 64: 352–364.
   Web of Science ®Google Scholar
• Bezanson J, Karpinski S, Shah V, Edelman A. 2012. Julia: a fast dynamic language for technical computing. CoRR. abs/1209.5145.
   Google Scholar
• Bixby R, Rothberg E. 2007. Progress in computational mixed integer programming - a look back from the other side of the tipping point. Ann Oper Res. 149: 37–41.
   Web of Science ®Google Scholar
• Castillo I, Westerlund J, Emet S, Westerlund T. 2005. Optimization of block layout design problems with unequal areas: a comparison of MILP and MINLP optimization methods. Comput Chem Eng. 30: 54–69.
   Web of Science ®Google Scholar
• Chlamtac E, Tulsiani M. 2012. Convex relaxations and integrality gaps. Boston (MA): Springer US. ( International Series in Operations Research and Management Science; vol. 166; Chapter 6; p. 139–169).
   Google Scholar
• Conforti M, Cornuéjols G, Zambelli G. 2014. Integer programming. Switzerland: Springer.
   Google Scholar
• Dey SS, Iroume A, Molinaro M. 2015a. Some lower bounds on sparse outer approximations of polytopes. Oper Res Lett. 43(3):323–328.
   Web of Science ®Google Scholar
• Dey SS, Molinaro M, Wang Q. 2015b. Approximating polyhedra with sparse inequalities. Math Program. 154(1):329–352.
   Web of Science ®Google Scholar
• Dey SS, Molinaro M, Wang Q. 2016. Analysis of sparse cutting-planes for sparse MILPs with applications to stochastic MILPs. arXiv:1601.00198.
   Google Scholar
• Dunning I, Huchette J, Lubin M. 2015. JuMP: a modeling language for mathematical optimization. arXiv:1508.01982.
   Google Scholar
• Horn RA, Johnson CR. 1990. Matrix analysis. New York (NY): Cambridge University Press.
   Google Scholar
• Huchette J, Dey SS, Vielma JP. 2017. Strong mixed-integer formulations for the floor layout problem. INFORS: Info Sys Oper Res. Available at https://doi.org/10.1080/03155986.2017.1346916
   Google Scholar
• Jankovits I, Luo C, Anjos M, Vannelli A. 2011. A convex optimisation framework for the unequal-areas facility layout problem. Eur J Oper Res. 214: 199–215.
   Web of Science ®Google Scholar
• Lasserre J. 2001. Global optimization with polynomials and the problem of moments. SIAM J Optim. 11(3):796–817.
   Web of Science ®Google Scholar
• Laurent M, Rendl F. 2005. Semidefinite programming and integer programming. Handbooks Oper Res Manag Sci. 12: 393–514.
   Google Scholar
• Lin JM, Hung ZX. 2011. UFO: unified convex optimization algorithms for fixed-outline floorplanning considering pre-placed modules. IEEE Trans Comput Aided Design Integ Circ Syst. 30(7):1034–1044.
   Web of Science ®Google Scholar
• Liu Q, Meller R. 2007. A sequence-pair representation and MIP-model-based heuristic for the facility layout problem with rectangular departments. IEEE Trans. 39: 377–394.
   Web of Science ®Google Scholar
• Lovász L, Schrijver A. 1991. Cones of matrices and set-functions and 0-1 optimization. SIAM J Optim. 1(2):166–190.
   Web of Science ®Google Scholar
• Love RF, Wong JY. 1976. On solving a one-dimensional space allocation problem with integer programming. INFOR. 14(2):139–143.
   Google Scholar
• Luo C, Anjos M, Vannelli A. 2008. A nonlinear optimization methodology for VLSI fixed-outline floorplanning. J Comb Optim. 16: 378–401.
   Web of Science ®Google Scholar
• Marchand H, Martin A, Weismantel R, Wolsey LA. 2002. Cutting planes in integer and mixed integer programming. Disc Appl Math. 123: 397–446.
   Web of Science ®Google Scholar
• Meller R, Chen W, Sherali H. 2007. Applying the sequence-pair representation to optimal facility layout designs. Oper Res Lett. 35: 651–659.
   Web of Science ®Google Scholar
• Meller R, Narayanan V, Vance P. 1999. Optimal facility layout design. Oper Res Lett. 23: 117–127.
   Web of Science ®Google Scholar
• Richard JPP, Dey SS. 2010. The group-theoretic approach in mixed integer programming. Berlin: Springer. ( Chapter 19, p. 727–801).
   Google Scholar
• Sherali H, Fraticelli B, Meller R. 2003. Enhanced model formulations for optimal facility layout. Oper Res. 51(4):629–644.
   Web of Science ®Google Scholar
• Sherali HD, Adams WP. 1990. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J Disc Math. 3(3):411–430.
   Web of Science ®Google Scholar
• Takouda P, Anjos M, Vannelli A. 2005. Global lower bounds for the VLSI macrocell floorplanning problem using semidefinite optimization. Int Database Eng Appl Symp. 9: 1–6.
   Google Scholar
• van Camp D, Carter M, Vannelli A. 1991. A nonlinear optimization approach for solving facility layout problems. Eur J Oper Res. 57: 174–189.
   Web of Science ®Google Scholar
• Vielma JP. 2015. Mixed integer linear programming formulation techniques. SIAM Rev. 57: 3–57.
   Web of Science ®Google Scholar
• Walter M. 2012. Sparsity of lift-and-project cutting planes. In: Helber S, Breitner M, Rösch D, Schön C, Graf von der Schulenburg JM, Sibbertsen P, Steinbach M, Weber S, Wolter A, editors. Operations Research Proceedings 2012. Cham: Springer International Publishing; p. 9–14.
   Google Scholar