Perspective Benders Decomposition with Applications to Fixed-Charge Nonlinear Resource Allocation

References

• Abhishek K, Leyffer S, Linderoth J (2010) FilMINT: An outer approximation-based solver for convex mixed-integer nonlinear programs. INFORMS J. Comput. 22(4):555–567.Link, Google Scholar
• Agnetis A, Grande E, Pacifici A (2012) Demand allocation with latency cost functions. Math. Programming 132(1–2):277–294.Crossref, Google Scholar
• Agnetis A, Grande E, Mirchandani PB, Pacifici A (2009) Covering a line segment with variable radius discs. Comput. Oper. Res. 36(5):1423–1436.Crossref, Google Scholar
• Aktürk MS, Atamtürk A, Gürel S (2009) A strong conic quadratic reformulation for machine-job assignment with controllable processing times. Oper. Res. Lett. 37(3):187–191.Crossref, Google Scholar
• Alizadeh F, Goldfarb D (2003) Second-order cone programming. Math. Programming 95(1):3–51.Crossref, Google Scholar
• Balas E, Martin CH (1980) Pivot and complement—A heuristic for 0-1 programming. Management Sci. 26(1):86–96.Link, 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
• Benders J (1962) Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4(1):238–252.Crossref, Google Scholar
• Birge JR, Louveaux FV (1988) A multicut algorithm for two-stage stochastic linear programs. Eur. J. Oper. Res. 34(3):384–392.Crossref, Google Scholar
• Bragalli C, D’Ambrosio C, Lee J, Lodi A, Toth P (2006) An MINLP solution method for a water network problem. Technical Report RC23893 (W0602-210), Research Division, IBM, Yorktown Heights, NY.Google Scholar
• Contreras I, Cordeau JF, Laporte G (2011) Benders decomposition for large-scale uncapacitated hub location. Oper. Res. 59(6):1477–1490.Link, Google Scholar
• Cosares S, Hochbaum DS (1994) Strongly polynomial algorithms for the quadratic transportation problem with a fixed number of sources. Math. Oper. Res. 19(1):94–111.Link, Google Scholar
• Crowder H, Padberg MW (1980) Solving large-scale symmetric travelling salesman problems to optimality. Management Sci. 26(5):495–509.Link, Google Scholar
• D’Amico AA, Sanguinetti L, Palomar DP (2014) Convex separable problems with linear constraints in signal processing and communications. IEEE Trans. Signal Process. 62(22):6045–6058.Crossref, Google Scholar
• Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. Oper. Res. 2(4):393–410.Link, Google Scholar
• de Camargo RS, Miranda G Jr, Luna HP (2008) Benders decomposition for the uncapacitated multiple allocation hub location problem. Comput. Oper. Res. 35(4):1047–1064.Crossref, Google Scholar
• Duguet A, Ngueveu SU (2022) Piecewise linearization of bivariate nonlinear functions: Minimizing the number of pieces under a bounded approximation error. Internat. Sympos. Combinatorial Optim. (Springer, Cham, Switzerland), 117–129.Google Scholar
• Duran MA, Grossmann IE (1986) An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Math. Programming 36:307–339.Crossref, Google Scholar
• Fischetti M, Ljubić I, Sinnl M (2016) Benders decomposition without separability: A computational study for capacitated facility location problems. Eur. J. Oper. Res. 253(3):557–569.Crossref, Google Scholar
• Fischetti M, Ljubić I, Sinnl M (2017) Redesigning Benders decomposition for large-scale facility location. Management Sci. 63(7):2146–2162.Link, Google Scholar
• Fletcher R, Leyffer S (1994) Solving mixed integer nonlinear programs by outer approximation. Math. Programming 66(3):327–349.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
• Frangioni A, Gentile C (2009) A computational comparison of reformulations of the perspective relaxation: SOCP vs. cutting planes. Oper. Res. Lett. 37(3):206–210.Crossref, Google Scholar
• Frangioni A, Furini F, Gentile C (2016) Approximated perspective relaxations: A project and lift approach. Comput. Optim. Appl. 63(3):705–735.Crossref, Google Scholar
• Frangioni A, Furini F, Gentile C (2017) Improving the approximated projected perspective reformulation by dual information. Oper. Res. Lett. 45(5):519–524.Crossref, Google Scholar
• Frangioni A, Gentile C, Lacalandra F (2009) Tighter approximated MILP formulations for unit commitment problems. IEEE Trans. Power Syst. 24(1):105–113.Crossref, Google Scholar
• Frangioni A, Gentile C, Grande E, Pacifici A (2011) Projected perspective reformulations with applications in design problems. Oper. Res. 59(5):1225–1232.Link, Google Scholar
• Fujishige S (2005) Submodular Functions and Optimization, Annals of Discrete Mathematics, vol. 58, 2nd ed. (Elsevier, Amsterdam).Google Scholar
• Geoffrion AM (1972) Generalized Benders decomposition. J. Optim. Theory Appl. 10(4):237–260.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
• Günlük O, Linderoth J (2010) Perspective reformulations of mixed integer nonlinear programs with indicator variables. Math. Programming 124(1–2):183–205.Crossref, Google Scholar
• Günlük O, Lee J, Weismantel R (2007) MINLP strengthening for separable convex quadratic transportation-cost UFL. Technical Report RC24213 (W703-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
• Hiriart-Urruty JB, Lemaréchal C (1996) Convex Analysis and Minimization Algorithms I: Fundamentals, Grundlehren Der Mathematischen Wissenschaften, vol. 305 (Springer Berlin, Heidelberg).Google Scholar
• IBM CPLEX Optimizer (2022) CPLEX user’s manual. https://www.ibm.com/docs/en/icos/22.1.0?topic=optimizers-users-manual-cplex.Google Scholar
• Kelley JE Jr (1960) The cutting-plane method for solving convex programs. J. Soc. Ind. Appl. Math. 8(4):703–712.Crossref, Google Scholar
• Kiwiel KC (2008a) Breakpoint searching algorithms for the continuous quadratic knapsack problem. Math. Programming 112:473–491.Crossref, Google Scholar
• Kiwiel KC (2008b) Variable fixing algorithms for the continuous quadratic knapsack problem. J. Optim. Theory Appl. 136:445–458.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(1):127–142.Crossref, Google Scholar
• Lee J, Skipper D, Speakman E, Xu L (2023) Gaining or losing perspective for piecewise-linear under-estimators of convex univariate functions. J. Optim. Theory Appl. 196(1):1–35.Crossref, Google Scholar
• Letchford AN, Miller SJ (2014) An aggressive reduction scheme for the simple plant location problem. Eur. J. Oper. Res. 234(3):674–682.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
• Schoot Uiterkamp MH, Gerards ME, Hurink JL (2022) On a reduction for a class of resource allocation problems. INFORMS J. Comput. 34(3):1387–1402.Link, Google Scholar
• Végh LA (2016) A strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives. SIAM J. Comput. 45(5):1729–1761.Crossref, Google Scholar
• Yang K, Song G, Wang R, Yang H, Leus R (2025) Perspective Benders decomposition with applications to fixed-charge nonlinear resource allocation. http://dx.doi.org/10.1287/ijoc.2024.0984.cd, https://github.com/INFORMSJoC/2024.0984.Google Scholar