Disjoint Bilinear Optimization: A Two-Stage Robust Optimization Perspective

References

• Ahmadi AA, Zhang J (2021) Semidefinite programming and Nash equilibria in bimatrix games. INFORMS J. Comput. 33(2):607–628.Abstract, Google Scholar
• Ahmed S, Guan Y (2005) The inverse optimal value problem. Math. Programming 102(1):91–110.Crossref, Google Scholar
• Alarie S, Audet C, Jaumard B, Savard G (2001) Concavity cuts for disjoint bilinear programming. Math. Programming 90(2):373–398.Crossref, Google Scholar
• Al-Khayyal F, Larsen C, Van Voorhis T (1995) A relaxation method for nonconvex quadratically constrained quadratic programs. J. Global Optim. 6(3):215–230.Crossref, Google Scholar
• Anstreicher K (2012) On convex relaxations for quadratically constrained quadratic programming. Math. Programming 136(2):233–251.Crossref, Google Scholar
• Ardestani-Jaafari A, Delage E (2016) Robust optimization of sums of piecewise linear functions with application to inventory problems. Oper. Res. 64(2):474–494.Link, Google Scholar
• Ardestani-Jaafari A, Delage E (2017) The value of flexibility in robust location–transportation problems. Transportation Sci. 52(1):189–209.Link, Google Scholar
• Ardestani-Jaafari A, Delage E (2021) Linearized robust counterparts of two-stage robust optimization problems with applications in operations management. INFORMS J. Comput. 33(3):1138–1161.Link, Google Scholar
• Atamtürk A, Zhang M (2007) Two-stage robust network flow and design under demand uncertainty. Oper. Res. 55(4):662–673.Link, Google Scholar
• Audet C, Hansen P, Jaumard B, Savard G (1999) A symmetrical linear maxmin approach to disjoint bilinear programming. Math. Programming 85(3):573–592.Crossref, Google Scholar
• Avis D, Rosenberg G, Savani R, von Stengel B (2010) Enumeration of Nash equilibria for two-player games. Econom. Theory 42(1):9–37.Crossref, Google Scholar
• Ayoub J, Poss M (2016) Decomposition for adjustable robust linear optimization subject to uncertainty polytope. Comput. Management Sci. 13:219–239.Crossref, Google Scholar
• Beck A, Ben-Tal A (2009) Duality in robust optimization: Primal worst equals dual best. Oper. Res. Lett. 37(1):1–6.Crossref, Google Scholar
• Ben-Tal A, den Hertog D, Vial JP (2015) Deriving robust counterparts of nonlinear uncertain inequalities. Math. Programming 149(1):265–299.Crossref, Google Scholar
• Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust Optimization, Princeton Series in Applied Mathematics (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Ben-Tal A, Golany B, Nemirovski A, Vial JP (2005) Retailer-supplier flexible commitments contracts: A robust optimization approach. Manufacturing Service Oper. Management 7(3):248–271.Link, Google Scholar
• Ben-Tal A, Goryashko A, Guslitzer E, Nemirovski A (2004) Adjustable robust solutions of uncertain linear programs. Math. Programming 99(2):351–376.Crossref, Google Scholar
• Bertsimas D, Bidkhori H (2015) On the performance of affine policies for two-stage adaptive optimization: A geometric perspective. Math. Programming 153(2):577–594.Crossref, Google Scholar
• Bertsimas D, de Ruiter F (2016) Duality in two-stage adaptive linear optimization: Faster computation and stronger bounds. INFORMS J. Comput. 28(3):500–511.Link, Google Scholar
• Bertsimas D, Dunning I (2016) Multistage robust mixed integer optimization with adaptive partitions. Oper. Res. 64(4):980–998.Link, Google Scholar
• Bertsimas D, Goyal V (2012) On the power and limitations of affine policies in two-stage adaptive optimization. Math. Programming 134(2):491–531.Crossref, Google Scholar
• Bertsimas D, Dunning I, Lubin M (2015) Reformulation vs. cutting-planes for robust optimization. Comput. Management Sci. 13(2):195–217.Crossref, Google Scholar
• Bertsimas D, Iancu D, Parrilo P (2010) Optimality of affine policies in multistage robust optimization. Math. Oper. Res. 35(2):363–394.Link, Google Scholar
• Bertsimas D, Iancu D, Parrilo P (2011) A hierarchy of near-optimal policies for multistage adaptive optimization. IEEE Trans. Automatic Control 56(12):2809–2824.Crossref, Google Scholar
• Bertsimas D, Sim M, Zhang M (2019) Adaptive distributionally robust optimization. Management Sci. 65(2):604–618.Link, Google Scholar
• Bertsimas D, Litvinov E, Sun X, Zhao J, Zheng T (2013) Adaptive robust optimization for the security constrained unit commitment problem. IEEE Trans. Power Systems 28(1):52–63.Crossref, Google Scholar
• Bonami P, Lodi A, Tramontani A, Wiese S (2015) On mathematical programming with indicator constraints. Math. Programming 151(1):191–223.Crossref, Google Scholar
• Calafiore G (2008) Multi-period portfolio optimization with linear control policies. Automatica J. IFAC 44(10):2463–2473.Crossref, Google Scholar
• Calafiore G (2009) An affine control method for optimal dynamic asset allocation with transaction costs. SIAM J. Control Optim. 48(4):2254–2274.Crossref, Google Scholar
• Ceria S, Soares J (1999) Convex programming for disjunctive convex optimization. Math. Programming 86(3):595–614.Crossref, Google Scholar
• Chen X, Deng X (2006) Settling the complexity of two-player Nash equilibrium. 47th Annual IEEE Sympos. Foundations Comput. Sci., 261–272.Google Scholar
• Chen X, Zhang Y (2009) Uncertain linear programs: Extended affinely adjustable robust counterparts. Oper. Res. 57(6):1469–1482.Link, Google Scholar
• Chen X, Sim M, Sun P, Zhang J (2008) A linear decision-based approximation approach to stochastic programming. Oper. Res. 56(2):344–357.Link, Google Scholar
• Combettes P (2018) Perspective functions: Properties, constructions, and examples. Set-Valued Variational Anal. 26(2):247–264.Crossref, Google Scholar
• Ćustić A, Sokol V, Punnen AP, Bhattacharya B (2017) The bilinear assignment problem: Complexity and polynomially solvable special cases. Math. Programming 1(2):185–205.Crossref, Google Scholar
• Dantzig G (1963) Linear Programming and Extensions (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• de Ruiter F, Ben-Tal A (2017) Tractable nonlinear decision rules for robust optimization. Working paper, Tilburg University, Netherlands.Google Scholar
• de Ruiter F, Zhen J, den Hertog D (2019) Dual approach to two-stage nonlinear robust optimization. Optimization Online. Accessed August 2018, http://www.optimization-online.org/DB_HTML/2018/03/6522.html.Google Scholar
• El Housni O, Goyal V (2021) On the optimality of affine policies for budgeted uncertainty sets. Math. Oper. Res. 46(2):674–711.Link, Google Scholar
• Firouzbakht K, Noubir G, Salehi M (2016) Linearly constrained bimatrix games in wireless communications. IEEE Trans. Comm. 64(1):429–440.Crossref, Google Scholar
• Floudas C, Pardalos P (2008) Encyclopedia of Optimization (Springer Science & Business Media).Crossref, Google Scholar
• Fukuda K (2013) Polyhedral Computation, Lecture notes (ETH Zurich).Google Scholar
• Gabrel V, Lacroix M, Murat C, Remli N (2014) Robust location transportation problems under uncertain demands. Discrete Appl. Math. 164(1):100–111.Crossref, Google Scholar
• Gallo G, Ülkücü A (1977) Bilinear programming: An exact algorithm. Math. Programming 12(1):173–194.Crossref, Google Scholar
• Gamrath G, Anderson D, Bestuzheva K, Chen WK, Eifler L, Gasse M, Gemander P, Gleixner A, Gottwald L, Halbig K, et al. (2020) The SCIP optimization suite 7.0.Google Scholar
• Geoffrion A (1972) Generalized Benders decomposition. J. Optim. Theory Appl. 10(4):237–260.Crossref, Google Scholar
• Georghiou A, Tsoukalas A, Wiesemann W (2019) A primal-dual lifting scheme for two-stage robust optimization. Oper. Res. 68(2):1–19.Google Scholar
• Georghiou A, Tsoukalas A, Wiesemann W (2021) On the optimality of affine decision rules in robust and distributionally robust optimization. Optimization Online. Accessed August 2018, http://www.optimization-online.org/DB_HTML/2021/05/8407 .html.Google Scholar
• Gorissen B, den Hertog D (2013) Robust counterparts of inequalities containing sums of maxima of linear functions. Eur. J. Oper. Res. 227(1):30–43.Crossref, Google Scholar
• Gorissen B, Ben-Tal A, Blanc H, den Hertog D (2014) Technical note—Deriving robust and globalized robust solutions of uncertain linear programs with general convex uncertainty sets. Oper. Res. 62(3):672–679.Link, Google Scholar
• Grossmann I, 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 (2010) Perspective reformulations of mixed integer nonlinear programs with indicator variables. Math. Programming 124(1–2):183–205.Crossref, Google Scholar
• Guslitzer E (2002) Uncertainty-immunized solutions in linear programming. Unpublished master’s thesis, Technion-Israel Institute of Technology, Haifa.Google Scholar
• Hadjiyiannis MJ, Goulart PJ, Kuhn D (2011) A scenario approach for estimating the suboptimality of linear decision rules in two-stage robust optimization. 2011 50th IEEE Conf. Decision Control Eur. Control Conf., 7386–7391.Google Scholar
• Hanasusanto G, Kuhn D (2018) Conic programming reformulations of two-stage distributionally robust linear programs over Wasserstein balls. Oper. Res. 66(3):1–21.Link, Google Scholar
• Hanasusanto G, Kuhn D, Wiesemann W (2014) K-adaptability in two-stage robust binary programming. Oper. Res. 63(4):877–891.Link, Google Scholar
• Hijazi H, Bonami P, Cornuéjols G, Ouorou A (2012) Mixed-integer nonlinear programs featuring “on/off” constraints. Comput. Optim. Appl. 52:537–558.Crossref, Google Scholar
• Iancu D, Sharma M, Sviridenko M (2013) Supermodularity and affine policies in dynamic robust optimization. Oper. Res. 61(4):941–956.Link, Google Scholar
• Jaillet P, Jena S, Ng T, Sim M (2016) Satisficing awakens: Models to mitigate uncertainty. Optimization Online. Accessed August 2018, http://www.optimization-online.org/DB_HTML/2016/01/5310.html.Google Scholar
• Jiang R, Li D (2019) Convex relaxations with second order cone constraints for nonconvex quadratically constrained quadratic programming. J. Global Optim. 75(2):461–494.Crossref, Google Scholar
• Konno H (1971a) Bilinear programming: Part I. Algorithm for solving bilinear programs. Technical report, DTIC, Fort Belvoir, VA.Google Scholar
• Konno H (1971b) Bilinear programming: Part II. Application of bilinear programming. Technical report, DTIC, Fort Belvoir, VA.Google Scholar
• Konno H (1976) A cutting plane algorithm for solving bilinear programs. Math. Programming 11(1):14–27.Crossref, Google Scholar
• Lemke CE, Howson JT Jr (1964) Equilibrium points of bimatrix games. J. Soc. Indust. Appl. Math. 12(2):413–423.Crossref, Google Scholar
• Lim C, Smith J (2007) Algorithms for discrete and continuous multicommodity flow network interdiction problems. IIE Trans. 39(1):15–26.Crossref, Google Scholar
• Lipp T, Boyd S (2016) Variations and extension of the convex–concave procedure. Optim. Engrg. 17(2):263–287.Crossref, Google Scholar
• Löfberg J (2004) YALMIP: A toolbox for modeling and optimization in MATLAB. 2004 IEEE Internat. Conf. Robotics Automation (IEEE Cat. No. 04CH37508), 284–289.Google Scholar
• Mangasarian O, Stone H (1964) Two-person nonzero-sum games and quadratic programming. J. Math. Anal. Appl. 9(3):348–355.Crossref, Google Scholar
• McCormick G (1976) Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems. Math. Programming 10(1):147–175.Crossref, Google Scholar
• Moehle N, Boyd S (2015) A perspective-based convex relaxation for switched-affine optimal control. Systems Control Lett. 86:34–40.Crossref, Google Scholar
• MOSEK ApS (2017) The MOSEK optimization toolbox for MATLAB manual. Version 8.1. http://docs.mosek.com/8.1/toolbox.pdf.Google Scholar
• Nahapetyan AG (2008) Bilinear programming. Floudas C, Pardalos P, eds. Encyclopedia of Optimization (Springer, Boston), 279–282.Crossref, Google Scholar
• Ng T, Sy C (2014) An affine adjustable robust model for generation and transmission network planning. Internat. J. Electr. Power Energy Systems 60:141–152.Crossref, Google Scholar
• Ordóñez F, Zhao J (2007) Robust capacity expansion of network flows. Networks 50(2):136–145.Crossref, Google Scholar
• Park J, Boyd S (2017) General heuristics for nonconvex quadratically constrained quadratic programming. Preprint, submitted March 22, https://arxiv.org/abs/1703.07870.Google Scholar
• Postek K, den Hertog D (2016) Multi-stage adjustable robust mixed-integer optimization via iterative splitting of the uncertainty set. INFORMS J. Comput. 28(3):553–574.Link, Google Scholar
• Rebennack S, Nahapetyan A, Pardalos P (2009) Bilinear modeling solution approach for fixed charge network flow problems. Optim. Lett. 3:347–355.Crossref, Google Scholar
• Rocha P, Kuhn D (2012) Multistage stochastic portfolio optimisation in deregulated electricity markets using linear decision rules. Eur. J. Oper. Res. 216(2):397–408.Crossref, Google Scholar
• Rockafellar R (1970) Convex Analysis (Princeton University Press).Crossref, Google Scholar
• Roos E, den Hertog D, Ben-Tal A, de Ruiter F, Zhen J (2018) Tractable approximation of hard uncertain optimization problems. Optimization Online. Accessed August 2018, http://www.optimization-online.org/DB_HTML/2018/06/6679.html.Google Scholar
• Sahinidis N, Grossmann E (1991) Convergence properties of generalized benders decomposition. Comput. Chemical Engrg. 15(7):481–491.Crossref, Google Scholar
• See CT, Sim M (2009) Robust approximation of multiperiod inventory management. Oper. Res. 58(3):583–594.Link, Google Scholar
• Selvi A, Ben-Tal A, Brekelmans R, den Hertog D (2022) Convex maximization via adjustable robust optimization. INFORMS J. Comput. Forthcoming.Google Scholar
• Sherali H, Alameddine A (1992) A new reformulation-linearization technique for bilinear programming problems. J. Global Optim. 2(4):379–410.Crossref, Google Scholar
• Sherali H, Liberti L (2008) Reformulation-linearization methods for global optimization. Pardalos P, Floudas C, eds. Encyclopedia of Optimization (Springer, Berlin), 3263–3268.Crossref, Google Scholar
• Sherali H, Shetty C (1980) A finitely convergent algorithm for bilinear programming problems using polar cuts and disjunctive face cuts. Math. Programming 19(1):14–31.Crossref, Google Scholar
• Simchi-Levi D, Wang H, Wei Y (2019) Constraint generation for two-stage robust network flow problems. INFORMS J. Optim. 1(1):49–70.Link, Google Scholar
• Soland R (1974) Optimal facility location with concave costs. Oper. Res. 22(2):373–382.Link, Google Scholar
• Stursberg O, Panek S (2002) Hybrid Systems: Computation and Control. Tomlin CJ, Greenstreet MR, eds. HSCC 2002. Lecture Notes in Computer Science, vol. 2289.Google Scholar
• Thieu T (1988) A note on the solution of bilinear programming problems by reduction to concave minimization. Math. Programming 41(1–3):249–260.Crossref, Google Scholar
• Vaish H (1974) Nonconvex programming with applications to production and location problems. Unpublished PhD thesis, Georgia Institute of Technology, Atlanta.Google Scholar
• Vaish H, Shetty C (1976) The bilinear programming problem. Naval Res. Logist. 23(2):303–309.Crossref, Google Scholar
• Wiesemann W, Kuhn D, Rustem B (2012) Robust resource allocations in temporal networks. Math. Programming 135(1):437–471.Crossref, Google Scholar
• Xu G, Burer S (2018) A copositive approach for two-stage adjustable robust optimization with uncertain right-hand sides. Comput. Optim. Appl. 70(1):33–59.Crossref, Google Scholar
• Zeng B, Zhao L (2013) Solving two-stage robust optimization problems using a column-and-constraint generation method. Oper. Res. Lett. 41(5):457–461.Crossref, Google Scholar
• Zhen J, den Hertog D (2017) Computing the maximum volume inscribed ellipsoid of a polytopic projection. INFORMS J. Comput. 30(1):31–42.Link, Google Scholar
• Zhen J, den Hertog D, Sim M (2017) Adjustable robust optimization via Fourier-Motzkin elimination. Oper. Res. 66(4):1086–1100.Link, Google Scholar
• Zhen J, Kuhn D, Wisemann W (2021a) Mathematical foundations of robust and distributionally robust optimization. Optimization Online. Accessed August 2018, http://www.optimization-online.org/DB_FILE/2021/04/8360.pdf.Google Scholar
• Zhen J, de Ruiter FJ, Roos E, den Hertog D (2022) Robust optimization for models with uncertain second-order cone and semidefinite programming constraints. INFORMS J. Comput. Forthcoming.Link, Google Scholar
• Zhen J, Marandi A, de Moor D, den Hertog D, Vandenberghe L (2021c) R4B version v2021.1222. http://dx.doi.org/10.5281/zenodo.5752594.Google Scholar
• Zheng X, Sun X, Li D (2011) Nonconvex quadratically constrained quadratic programming: Best DC decompositions and their SDP representations. J. Global Optim. 50(4):695–712.Crossref, Google Scholar