×

zbMATH — the first resource for mathematics

Simultaneous convexification of bilinear functions over polytopes with application to network interdiction. (English) Zbl 1377.90066

MSC:
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
90C35 Programming involving graphs or networks
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C90 Applications of mathematical programming
91A43 Games involving graphs
PDF BibTeX Cite
Full Text: DOI
References:
[1] W. P. Adams and H. D. Sherali, Mixed-integer bilinear programming problems, Math. Programming, 59 (1993), pp. 279–305. · Zbl 0801.90085
[2] F. A. Al-Khayyal, Generalized bilinear programming: Part I. Models, applications and linear programming relaxation, Eur. J. Oper. Res., 60 (1992), pp. 306–314. · Zbl 0784.90051
[3] F. A. Al-Khayyal and J. E. Falk, Jointly constrained biconvex programming, Math. Oper. Res., 8 (1983), pp. 273–286. · Zbl 0521.90087
[4] D. S. Altner, Ö. Ergun, and N. A. Uhan, The maximum flow network interdiction problem: Valid inequalities, integrality gaps, and approximability, Oper. Res. Lett., 38 (2010), pp. 33–38. · Zbl 1182.90014
[5] K. M. Anstreicher, On convex relaxations for quadratically constrained quadratic programming, Math. Programming, 136 (2012), pp. 233–251. · Zbl 1267.90103
[6] N. Assimakopoulos, A network interdiction model for hospital infection control, Comput. Biol. Med., 17 (1987), pp. 413–422.
[7] C. Audet, J. Brimberg, P. Hansen, S. L. Digabel, and N. Mladenović, Pooling problem: Alternate formulations and solution methods, Management Sci., 50 (2004), pp. 761–776. · Zbl 1232.90349
[8] E. Balas, Disjunctive programming and a hierarchy of relaxations for discrete optimization problems, SIAM J. Discrete Math., 6 (1985), pp. 466–486, . · Zbl 0592.90070
[9] E. Balas, Disjunctive programming: Properties of the convex hull of the feasible points, Discrete Appl. Math., 89 (1998), pp. 3–44. · Zbl 0921.90118
[10] X. Bao, N. V. Sahinidis, and M. Tawarmalani, Semidefinite relaxations for quadratically constrained quadratic programming, Math. Programming, 129 (2011), pp. 129–157. · Zbl 1232.49035
[11] O. Ben-Ayed and C. E. Blair, Computational difficulties of bilevel linear programming, Oper. Res., 38 (1990), pp. 556–560. · Zbl 0708.90052
[12] A. Ben-Tal, G. Eiger, and V. Gershovitz, Global minimization by reducing the duality gap, Math. Programming, 63 (1994), pp. 193–212. · Zbl 0807.90101
[13] P. Bonami, A. Lodi, S. Tramontani, and A. Wiese, On mathematical programming with indicator constraints, Math. Programming, 151 (2015), pp. 191–223. · Zbl 1328.90086
[14] A. Caprara and M. Monaci, Bidimensional packing by bilinear programming, Math. Programming, 118 (2009), pp. 75–108. · Zbl 1169.90428
[15] T. Christof and A. Löbel, PORTA - POlyhedral Representation Transformation Algorithm, , 2012.
[16] R. A. Collado and D. Papp, Network Interdiction—Models, Applications, Unexplored Directions, RUTCOR research report RRR 4-2012, Rutgers Center for Operations Research Rutgers University, Piscataway, NJ, 2012.
[17] D. Davarnia, J.-P. P. Richard, and M. Tawarmalani, On the Strength and Structure of the KKT Formulation of Network Interdiction Problems, Tech. report, University of Florida, 2015.
[18] O. Günlük and J. Linderoth, Perspective reformulation and applications, in Mixed Integer Nonlinear Programming, J. Lee and S. Leyffer, eds., Springer, New York, 2012, pp. 61–89. · Zbl 1242.90134
[19] A. Gupte, S. Ahmed, M. S. Cheon, and S. Dey, Solving mixed integer bilinear problems using MILP formulations, SIAM J. Optim., 23 (2013), pp. 721–744, . · Zbl 1300.90021
[20] I. Harjunkoski, T. Westerlund, R. Pörn, and H. Skrifvars, Different transformations for solving non-convex trim-loss problems by MINLP, Eur. J. Oper. Res., 105 (1998), pp. 594–603. · Zbl 0955.90095
[21] T. E. Harris and F. S. Ross, Fundamentals of a Method for Evaluating Rail Network Capacities, Tech. report RM-1573, The RAND Corporation, Santa Monica, CA, 1955.
[22] H. Hijazi, P. Bonami, G. Cornuéjols, and A. Ouorou, Mixed integer nonlinear programs featuring on/off constraints, Comput. Optim. Appl., 52 (2012), pp. 537–558. · Zbl 1250.90058
[23] E. Israeli and R. K. Wood, Shortest-path network interdiction, Networks, 40 (2002), pp. 97–111. · Zbl 1027.90106
[24] R. G. Jeroslow, The polynomial hierarchy and a simple model for competitive analysis, Math. Programming, 32 (1985), pp. 146–164. · Zbl 0588.90053
[25] C. Lim and J. C. Smith, Algorithms for discrete and continuous multicommodity flow network interdiction problems, INFORMS J. Comput., 39 (2007), pp. 15–26.
[26] M. Locatelli and F. Schoen, On convex envelopes for bivariate functions over polytopes, Math. Programming, 144 (2014), pp. 65–91. · Zbl 1295.90055
[27] J. Luedtke, M. Namazifar, and J. Linderoth, Some results on the strength of relaxations of multilinear functions, Math. Programming, 136 (2012), pp. 325–351. · Zbl 1286.90117
[28] G. P. McCormick, Computability of global solutions to factorable nonconvex programs: Part I. Convex underestimating problems, Math. Programming, 10 (1976), pp. 145–175. · Zbl 0349.90100
[29] C. A. Meyer and C. A. Floudas, Trilinear monomials with mixed sign domains: Facets of the convex and concave envelopes, J. Global Optim., 29 (2004), pp. 125–155. · Zbl 1085.90047
[30] C. A. Meyer and C. A. Floudas, Convex envelopes for edge-concave functions, Math. Programming, 103 (2005), pp. 207–224. · Zbl 1099.90045
[31] R. Misener and C. A. Floudas, Advances for the pooling problem: Modeling, global optimization, and computational studies, Appl. Comput. Math., 8 (2009), pp. 3–22. · Zbl 1188.90287
[32] D. Morton, F. Pan, and K. Saeger, Models for nuclear smuggling interdiction, IIE Trans., 39 (2007), pp. 3–14.
[33] A. Nahapetyan, Bilinear programming: Applications in the supply chain management, in Encyclopedia of Optimization, C. Floudas, A. Christodoulos, and P. M. Pardalos, eds., Springer, New York, 2009.
[34] T. T. Nguyen, J.-P. P. Richard, and M. Tawarmalani, Deriving convex hulls through lifting and projection, Math. Programming, to appear, . · Zbl 1410.90132
[35] T. T. Nguyen, M. Tawarmalani, and J.-P. P. Richard, Convexification Techniques for Complementarity Constraints, Tech. report, University of Florida, Gainesville, FL, 2013. · Zbl 1341.90130
[36] I. Quesada and I. E. Grossmann, Global optimization of bilinear process networks with multicomponent flows, Comput. Chem. Engrg., 19 (1995), pp. 1219–1242.
[37] G. Rinaldi, U. Voigt, and G. J. Woeginger, The mathematics of playing golf, or: A new class of difficult non-linear mixed integer programs, Math. Programming, 93 (2002), pp. 77–86. · Zbl 1010.90066
[38] H. D. Sherali, W. P. Adams, and P. J. Driscoll, Exploiting special structures in constructing a hierarchy of relaxations for 0-1 mixed integer problems, Oper. Res., 46 (1998), pp. 396–405. · Zbl 0979.90090
[39] H. D. Sherali and A. Alameddine, An explicit characterization of the convex envelope of a bivariate bilinear function over special polytopes, Ann. Oper. Res., 25 (1992), pp. 197–210. · Zbl 0723.90073
[40] H. D. Sherali and A. Alameddine, A new reformulation-linearization technique for bilinear programming problems, J. Global Optim., 2 (1992), pp. 379–410. · Zbl 0791.90056
[41] J. C. Smith and C. Lim, Algorithms for network interdiction and fortification games, in Pareto Optimality, Game Theory and Equilibria, Springer Optim. Appl. 17, P. M. Pardalos, A. Migdalas, and L. Pitsoulis, eds., Springer-Verlag, New York, 2008, pp. 609–644. · Zbl 1152.91385
[42] K. M. Sullivan, J. C. Smith, and D. P. Morton, Convex hull representation of the deterministic bipartite network interdiction problem, Math. Programming, 145 (2014), pp. 349–376. · Zbl 1312.90042
[43] M. Tawarmalani, Inclusion Certificates and Simultaneous Convexification of Functions, manuscript.
[44] M. Tawarmalani, J.-P. P. Richard, and K. Chung, Strong valid inequalities for orthogonal disjunctions and bilinear covering sets, Math. Programming, 124 (2010), pp. 481–512. · Zbl 1198.90298
[45] M. Tawarmalani, J.-P. P. Richard, and C. Xiong, Explicit convex and concave envelopes through polyhedral subdivisions, Math. Programming, 138 (2012), pp. 531–577. · Zbl 1273.90165
[46] M. Tawarmalani and N. V. Sahinidis, Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications, Nonconvex Optim. Appl. 65, Springer Science+Business Media, Dordrecht, The Netherlands, 2002. · Zbl 1031.90022
[47] V. Visweswaran, MINLP: Applications in blending and pooling problems, in Encyclopedia of Optimization, C. Floudas and P. Pardalos, eds., Springer, New York, 2009, pp. 2114–2121.
[48] R. D. Wollmer, Removing arcs from a network, Oper. Res., 12 (1964), pp. 934–940. · Zbl 0204.20102
[49] R. K. Wood, Deterministic network interdiction, Math. Comput. Model., 17 (1993), pp. 1–18. · Zbl 0800.90772
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.