Redesigning Benders Decomposition for Large-Scale Facility Location

References

• Applegate D, Bixby R, Chvátal V, Cook W (2006) The Traveling Salesman Problem: A Computational Study (Princeton University Press, Princeton, NJ).Google Scholar
• Balas E (1971) A duality theorem and an algorithm for (mixed-) integer nonlinear programming. Linear Algebra Appl. 4(4):341–352.Crossref, Google Scholar
• Barahona F, Chudak F (2000) Solving large scale uncapacitated facility location problems. Pardalos P, ed. Approximation and Complexity in Numerical Optimization, Nonconvex Optimization and Its Applications, Vol. 42 (Springer, New York), 48–62.Crossref, Google Scholar
• Basu S, Sharma M, Ghosh P (2015) Metaheuristic applications on discrete facility location problems: A survey. OPSEARCH 52(3):530–561.Crossref, Google Scholar
• Beasley JE (1990) OR-library: Distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11):1069–1072.Crossref, Google Scholar
• Beltran-Royo C, Vial J-P, Alonso-Ayuso A (2012) Semi-Lagrangian relaxation applied to the uncapacitated facility location problem. Comput. Optim. Appl. 51(1):387–409.Crossref, Google Scholar
• Ben-Ameur W, Neto J (2007) Acceleration of cutting-plane and column generation algorithms: Applications to network design. Networks 49(1):3–17.Crossref, Google Scholar
• Bonami P, Kilinc M, Linderoth J (2012) Algorithms and software for convex mixed integer nonlinear programs. Lee J, Leyffer S, eds. Mixed Integer Nonlinear Programming, Vol. 154 (Springer, New York), 1–39.Crossref, Google Scholar
• Cornuéjols G, Nemhauser GL, Wolsey LA (1980) A canonical representation of simple plant location problems and its applications. SIAM J. Algebraic Discrete Methods 1(3):261–272.Crossref, Google Scholar
• D’Ambrosio C, Lee J, Wächter A (2009) A global-optimization algorithm for mixed-integer nonlinear programs having separable non-convexity. Fiat A, Sanders P, eds. Algorithms—ESA 2009, Lecture Notes in Computer Science, Vol. 5757 (Springer, Berlin), 107–118.Crossref, Google Scholar
• Fischetti M, Lodi A (2003) Local branching. Math. Programming 98(1–3):23–47.Crossref, Google Scholar
• Fischetti M, Monaci M (2014) Proximity search for 0-1 mixed-integer convex programming. J. Heuristics 20(6):709–731.Crossref, Google Scholar
• Fischetti M, Salvagnin D (2010) An in-out approach to disjunctive optimization. Lodi A, Milano M, Toth P, eds. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Lecture Notes in Computer Science, Vol. 6140 (Springer, Berlin), 136–140.Crossref, Google Scholar
• Frangioni A, Gentile C (2006) Perspective cuts for a class of convex 0-1 mixed integer programs. Math. Programming 106(2):225–236.Crossref, Google Scholar
• Friberg HA (2016) CBLIB 2014: A benchmark library for conic mixed-integer and continuous optimization. Math. Programming Comput. 8(2):191–214.Crossref, Google Scholar
• Geoffrion AM (1972) Generalized benders decomposition. J. Optim. Theory Appl. 10(4):237–260.Crossref, Google Scholar
• Georgilakis PS, Hatziargyriou ND (2013) Optimal distributed generation placement in power distribution networks: Models, methods, and future research. IEEE Trans. Power Systems 28(3):3420–3428.Crossref, Google Scholar
• Gollowitzer S, Ljubić I (2011) MIP models for connected facility location: A theoretical and computational study. Comput. Oper. Res. 38(2):435–449.Crossref, Google Scholar
• Ghosh D (2003) Neighborhood search heuristics for the uncapacitated facility location problem. Eur. J. Oper. Res. 150(1):150–162.Crossref, Google Scholar
• Grossmann IE, Lee S (2003) Generalized convex disjunctive programming: Nonlinear convex hull relaxation. Comput. Optim. Appl. 26(1):83–100.Crossref, Google Scholar
• Günlük O, Linderoth J (2012) Perspective reformulation and applications. Lee J, Leyffer S, eds. Mixed Integer Nonlinear Programming (Springer, New York), 61–92.Crossref, Google Scholar
• Günlük O, Lee J, Weismantel R (2007) MINLP strengthening for separable convex quadratic transportation-cost UFL. Technical Report RC24213 (W0703-042), Research Division, IBM, Yorktown Heights, NY.Google Scholar
• Hijazi H, Bonami P, Ouorou A (2014) An outer-inner approximation for separable mixed-integer nonlinear programs INFORMS J. Comput. 26(1):31–44.Link, Google Scholar
• Hochbaum DS, Hong SP (1995) About strongly polynomial time algorithms for quadratic optimization over submodular constraints. Math. Programming 69(1–3):269–309.Crossref, Google Scholar
• Hoefer M (2006) UflLib. A collection of benchmark instances for the uncapacitated facility location problem. Accessed January 23, 2015, http://resources.mpi-inf.mpg.de/departments/d1/projects/benchmarks/UflLib/.Google Scholar
• Ke Q, Ferrara E, Radicchi F, Flammini A (2015) Defining and identifying sleeping beauties in science. Proc. Natl. Acad. Sci. USA 112(24):7426–7431.Crossref, Google Scholar
• Kelley JE Jr (1960) The cutting-plane method for solving convex programs. J. Soc. Indust. Appl. Math. 8(4):703–712.Crossref, Google Scholar
• Klose A, Drexl A (2005) Facility location models for distribution system design. Eur. J. Oper. Res. 162(1):4–29.Crossref, Google Scholar
• Körkel M (1989) On the exact solution of large-scale simple plant location problems. Eur. J. Oper. Res. 39(2):157–173.Crossref, Google Scholar
• Kratica J, Tošic D, Filipović V, Ljubić I (2001) Solving the simple plant location problem by genetic algorithm. RAIRO Oper. Res. 35(01):127–142.Crossref, Google Scholar
• Labbé M, Laporte G, Rodríguez-Martín I, Salazar-González JJ (2004) The ring star problem: Polyhedral analysis and exact algorithm. Networks 43(3):177–189.Crossref, Google Scholar
• Laporte G, Riera Ledesma J, Salazar González JJ (2003) A branch-and-cut algorithm for the undirected traveling purchaser problem. Oper. Res. 51(66):940–951.Link, Google Scholar
• Lemaréchal C, Nemirovskii A, Nesterov Y (1995) New variants of bundle methods. Math. Programming 69(1–3):111–147.Crossref, Google Scholar
• Letchford A, Miller S (2012) Fast bounding procedures for large instances of the simple plant location problem. Comput. Oper. Res. 39(5):985–990.Crossref, Google Scholar
• Letchford A, Miller S (2014) An aggressive reduction scheme for the simple plant location problem. Eur. J. Oper. Res. 234(3):674–682.Crossref, Google Scholar
• Li S (2013) A 1.488 approximation algorithm for the uncapacitated facility location problem. Inform. Comput. 222(Special issue):45–58.Crossref, Google Scholar
• Magnanti TL, Wong RT (1981) Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria. Oper. Res. 29(3):464–484.Link, Google Scholar
• Margot F (2009) Testing cut generators for mixed-integer linear programming. Math. Programming Comput. 1(1):69–95.Crossref, Google Scholar
• Martello S, Toth P (1990) Knapsack Problems: Algorithms and Computer Implementations (John Wiley & Sons, New York).Google Scholar
• Meisel S, Mattfeld D (2010) Synergies of operations research and data mining. Eur. J. Oper. Res. 206(1):1–10.Crossref, Google Scholar
• Melo MT, Nickel S, Saldanha da Gama F (2009) Facility location and supply chain management—A review. Eur. J. Oper. Res. 196(2):401–412.Crossref, Google Scholar
• Naoum-Sawaya J, Elhedhli S (2013) An interior-point Benders based branch-and-cut algorithm for mixed integer programs. Ann. Oper. Res. 210(1):33–55.Crossref, Google Scholar
• Olafsson S, Li X, Wu S (2008) Operations research and data mining. Eur. J. Oper. Res. 187(3):1429–1448.Crossref, Google Scholar
• Patriksson M, Strömberg C (2015) Algorithms for the continuous nonlinear resource allocation problem—New implementations and numerical studies. Eur. J. Oper. Res. 243(3):703–722.Crossref, Google Scholar
• Posta M, Ferland JA, Michelon P (2014) An exact cooperative method for the uncapacitated facility location problem. Math. Programming Comput. 6(3):199–231.Crossref, Google Scholar
• Shmoys DB, Tardos É, Aardal K (1997) Approximation algorithms for facility location problems. Leighton F, Shor P, eds. Proc. Twenty-Ninth Ann. ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 265–274.Crossref, Google Scholar
• Verter V (2011) Uncapacitated and capacitated facility location problems. Eiselt HA, Marianov V, eds. Foundations of Location Analysis, International Series in Operations Research and Management Science, Vol. 155 (Springer, New York), 25–37.Crossref, Google Scholar