Convexification of Bilinear Terms over Network Polytopes

References

• [1] Al-Khayyal FA, Falk JE (1983) Jointly constrained biconvex programming. Math. Oper. Res. 8:273–286.Link, Google Scholar
• [2] Balas E (1998) Disjunctive programming: Properties of the convex hull of the feasible points. Discrete Appl. Math. 89:3–44.Crossref, Google Scholar
• [3] Beale EML, Forrest JJH (1976) Global optimization using special ordered sets. Math. Programming 10:52–69.Crossref, Google Scholar
• [4] Ben-Ayed O, Blair CE (1990) Computational difficulties of bilevel linear programming. Oper. Res. 38:556–560.Link, Google Scholar
• [5] Boland N, Dey SS, Kalinowski T, Molinaro M, Rigterink F (2017) Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions. Math. Programming 162:523–532.Crossref, Google Scholar
• [6] Bonami P, Günlük O, Linderoth J (2018) Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods. Math. Programming Comput. 10(3):333–382.Crossref, Google Scholar
• [7] Buchheim C, Crama Y, Rodríguez-Heck E (2019) Berge-acyclic multilinear 0-1 optimization problems. Eur. J. Oper. Res. 273(1):102–107.Crossref, Google Scholar
• [8] Chiou SW (2005) Bilevel programming for the continuous transport network design problem. Transportation Res. Part B Methodol. 39(4):361–383.Crossref, Google Scholar
• [9] Davarnia D (2016) Convexification techniques for bilinear and complementarity constraints with application to network interdiction. PhD thesis, University of Florida, Gainesville, FL.Google Scholar
• [10] Davarnia D (2021) Strong relaxations for continuous nonlinear programs based on decision diagrams. Oper. Res. Lett. 49(2):239–245.Crossref, Google Scholar
• [11] Davarnia D, Van Hoeve WJ (2020) Outer approximation for integer nonlinear programs via decision diagrams. Math. Programming 187:111–150.Crossref, Google Scholar
• [12] Davarnia D, Richard JPP, Tawarmalani M (2017) Simultaneous convexification of bilinear functions over polytopes with application to network interdiction. SIAM J. Optim. 27:1801–1833.Crossref, Google Scholar
• [13] Del Pia A, Di Gregorio S (2021) Chvátal rank in binary polynomial optimization. INFORMS J. Optim. 3(4):315–349.Link, Google Scholar
• [14] Del Pia A, Khajavirad A (2018) The multilinear polytope for acyclic hypergraphs. SIAM J. Optim. 28(2):1049–1076.Crossref, Google Scholar
• [15] Del Pia A, Khajavirad A (2021) The running intersection relaxation of the multilinear polytope. Math. Oper. Res. 46:1008–1037.Link, Google Scholar
• [16] Del Pia A, Walter M (2022) Simple odd β-cycle inequalities for binary polynomial optimization. Aardal K, Sanità L, eds. Integer Programming and Combinatorial Optimization (Springer International Publishing, Cham, Switzerland), 181–194.Crossref, Google Scholar
• [17] Fampa M, Lee J (2021) Convexification of bilinear forms through non-symmetric lifting. J. Global Optim. 80:287–305.Crossref, Google Scholar
• [18] Ficker A, Spieksma F, Woeginger G (2021) The transportation problem with conflicts. Ann. Oper. Res. 298:207–227.Crossref, Google Scholar
• [19] Gupte A, Ahmed S, Cheon MS, Dey S (2013) Solving mixed integer bilinear problems using MILP formulations. SIAM J. Optim. 23:721–744.Crossref, Google Scholar
• [20] Gupte A, Kalinowski T, Rigterink F, Waterer H (2020) Extended formulations for convex hulls of some bilinear functions. Discrete Optim. 36:100569.Crossref, Google Scholar
• [21] Khajavirad A (2023) On the strength of recursive McCormick relaxations for binary polynomial optimization. Oper. Res. Lett. 51(2):146–152.Crossref, Google Scholar
• [22] Locatelli M, Schoen F (2014) On convex envelopes for bivariate functions over polytopes. Math. Programming 144:65–91.Crossref, Google Scholar
• [23] Luedtke J, Namazifar M, Linderoth J (2012) Some results on the strength of relaxations of multilinear functions. Math. Programming 136:325–351.Crossref, Google Scholar
• [24] McCormick GP (1976) Computability of global solutions to factorable nonconvex programs: Part I. Convex underestimating problems. Math. Programming 10:145–175.Crossref, Google Scholar
• [25] Muller B, Serrano F, Gleixner A (2020) Using two-dimensional projections for stronger separation and propagation of bilinear terms. SIAM J. Optim. 30(2):1339–1365.Crossref, Google Scholar
• [26] 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
• [27] Salemi H, Davarnia D (2022) On the structure of decision diagram-representable mixed integer programs with application to unit commitment. Oper. Res. 71:1943–1959.Link, Google Scholar
• [28] Salemi H, Davarnia D (2023) Solving unsplittable network flow problems with decision diagrams. Transportation Sci. 57(4):937–953.Link, Google Scholar
• [29] Sherali HD, Adams WP (1990) A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3:411–430.Crossref, Google Scholar
• [30] Sherali HD, Alameddine A (1992) A new reformulation-linearization technique for bilinear programming problems. J. Global Optim. 2:379–410.Crossref, Google Scholar
• [31] Sherali HD, Adams WP, Driscoll PJ (1998) Exploiting special structures in constructing a hierarchy of relaxations for 0-1 mixed integer problems. Oper. Res. 46:396–405.Link, Google Scholar
• [32] Smith JC, Lim C (2008) Algorithms for network interdiction and fortification games. Chinchuluun A, Pardalos PM, Migdalas A, Pitsoulis L, eds. Pareto Optimality, Game Theory And Equilibria, vol. 17 (Springer Optimization and Its Applications, New York), 609–644.Crossref, Google Scholar
• [33] Tawarmalani M, Richard JPP, Xiong C (2012) Explicit convex and concave envelopes through polyhedral subdivisions. Math. Programming 138:531–577.Crossref, Google Scholar
• [34] Vancroonenburg W, Della Croce F, Goossens D, Spieksma FC (2014) The red-blue transportation problem. Eur. J. Oper. Res. 237(3):814–823.Crossref, Google Scholar