Mixed integer programming with a class of nonlinear convex constraints. (English) Zbl 1387.90166
Summary: We study solution approaches to a class of mixed-integer nonlinear programming problems that arise from recent developments in risk-averse stochastic optimization and contain second- and \(p\)-order cone programming as special cases. We explore possible applications of some of the solution techniques that have been successfully used in mixed-integer conic programming and show how they can be generalized to the problems under consideration. Particularly, we consider a branch-and-bound method based on outer polyhedral approximations, lifted nonlinear cuts, and linear disjunctive cuts. Results of numerical experiments with discrete portfolio optimization models are presented.
MSC:
| 90C11 | Mixed integer programming |
| 90C22 | Semidefinite programming |
| 90C25 | Convex programming |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 90C90 | Applications of mathematical programming |
Keywords:
mixed-integer nonlinear programming; measures of risk; quasi-arithmetic average; valid inequalities; conic programmingReferences:
| [1] | Vinel, A.; Krokhmal, P. A., Certainty equivalent measures of risk, Ann. Oper. Res., 1-21 (2015) · Zbl 1406.91207 |
| [2] | Rysz, M.; Vinel, A.; Krokhmal, P.; Pasiliao, E. L., A scenario decomposition algorithm for stochastic programming problems with a class of downside risk measures, INFORMS J. Comput., 27, 2, 416-430 (2015) · Zbl 1329.90096 |
| [3] | Bullen, P. S.; Mitrinović, D. S.; Vasić, P. M., (Means and their Inequalities. Means and their Inequalities, Mathematics and its Applications (East European Series), vol. 31 (1988), D. Reidel Publishing Co.: D. Reidel Publishing Co. Dordrecht), translated and revised from the Serbo-Croatian · Zbl 0687.26005 |
| [4] | Hardy, G. H.; Littlewood, J. E.; Pólya, G., Inequalities (1952), at the University Press: at the University Press Cambridge · Zbl 0047.05302 |
| [5] | Wilson, R., Auctions of shares, Quart. J. Econ., 93, 4, 675-689 (1979), URL http://www.jstor.org/stable/1884475 · Zbl 0414.90011 |
| [6] | McCord, M.; Neufville, R.d., “lottery equivalents”: Reduction of the certainty effect problem in utility assessment, Manage. Sci., 32, 1, 56-60 (1986), URL http://www.jstor.org/stable/2631399 · Zbl 0599.90008 |
| [7] | Ben-Tal, A.; Teboulle, M., An old-new concept of convex risk measures: An optimized certainty equivalent, Math. Finance, 17, 3, 449-476 (2007) · Zbl 1186.91116 |
| [8] | Krokhmal, P.; Zabarankin, M.; Uryasev, S., Modeling and optimization of risk, Surv. Oper. Res. Manage. Sci., 16, 2, 49-66 (2011), URL http://www.sciencedirect.com/science/article/pii/S187673541000005X |
| [9] | Rockafellar, R. T.; Uryasev, S., Conditional value-at-risk for general loss distributions, J. Bank. Finance, 26, 7, 1443-1471 (2002) |
| [10] | Krokhmal, P. A., Higher moment coherent risk measures, Quant. Finance, 7, 4, 373-387 (2007) · Zbl 1190.91074 |
| [11] | Vielma, J. P.; Ahmed, S.; Nemhauser, G. L., A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs, INFORMS J. Comput., 20, 3, 438-450 (2008) · Zbl 1243.90170 |
| [12] | Gupta, O. K.; Ravindran, A., Branch and bound experiments in convex nonlinear integer programming, Manage. Sci., 31, 12, 1533-1546 (1985) · Zbl 0591.90065 |
| [13] | Borchers, B.; Mitchell, J. E., An improved branch and bound algorithm for mixed integer nonlinear programs, Comput. Oper. Res., 21, 4, 359-367 (1994) · Zbl 0797.90069 |
| [14] | Leyffer, S., Integrating SQP and branch-and-bound for mixed integer nonlinear programming, Comput. Optim. Appl., 18, 3, 295-309 (2001) · Zbl 1009.90074 |
| [15] | Duran, M. A.; Grossmann, I. E., An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Math. Program., 36, 3, 307-339 (1986) · Zbl 0619.90052 |
| [16] | Fletcher, R.; Leyffer, S., Solving mixed integer nonlinear programs by outer approximation, Math. Program., 66, 3, 327-349 (1994), (Ser. A) · Zbl 0833.90088 |
| [17] | Quesada, I.; Grossmann, I. E., An lp/nlp based branch and bound algorithm for convex minlp optimization problems, Comput. Chem. Eng., 16, 10, 937-947 (1992) |
| [18] | Bonami, P.; Biegler, L. T.; Conn, A. R.; Cornuéjols, G.; Grossmann, I. E.; Laird, C. D.; Lee, J.; Lodi, A.; Margot, F.; Sawaya, N.; Wächter, A., An algorithmic framework for convex mixed integer nonlinear programs, Discrete Optim., 5, 2, 186-204 (2008) · Zbl 1151.90028 |
| [19] | Abhishek, K.; Leyffer, S.; Linderoth, J., FilMINT: an outer approximation-based solver for convex mixed-integer nonlinear programs, INFORMS J. Comput., 22, 4, 555-567 (2010) · Zbl 1243.90142 |
| [20] | Ben-Tal, A.; Nemirovski, A., On polyhedral approximations of the second-order cone, Math. Oper. Res., 26, 2, 193-205 (2001) · Zbl 1082.90133 |
| [21] | Vinel, A.; Krokhmal, P. A., Polyhedral approximations in \(p\)-order cone programming, Optim. Methods Softw., 29, 6, 1210-1237 (2014) · Zbl 1306.90155 |
| [22] | Atamtürk, A.; Narayanan, V., Conic mixed-integer rounding cuts, Math. Program., 122, 1, 1-20 (2010), (Ser. A) · Zbl 1184.90112 |
| [23] | Atamtürk, A.; Narayanan, V., Lifting for conic mixed-integer programming, Math. Program., 126, 2, 351-363 (2011), (Ser. A) · Zbl 1206.90102 |
| [24] | Stubbs, R. A.; Mehrotra, S., A branch-and-cut method for \(0-1\) mixed convex programming, Math. Program., 86, 3, 515-532 (1999), (Ser. A) · Zbl 0946.90054 |
| [25] | Çezik, M. T.; Iyengar, G., Cuts for mixed 0-1 conic programming, Math. Program., 104, 1, 179-202 (2005), (Ser. A) · Zbl 1159.90457 |
| [26] | Bonami, P., Lift-and-project cuts for mixed integer convex programs, (Integer Programming and Combinatorial Optimization. Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci., vol. 6655 (2011), Springer: Springer Heidelberg), 52-64 · Zbl 1339.90243 |
| [27] | Saxena, A.; Bonami, P.; Lee, J., Disjunctive cuts for non-convex mixed integer quadratically constrained programs, (Integer Programming and Combinatorial Optimization. Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci., vol. 5035 (2008), Springer: Springer Berlin), 17-33 · Zbl 1143.90365 |
| [28] | Burer, S.; Saxena, A., The milp road to miqcp, (Lee, J.; Leyffer, S., Mixed Integer Nonlinear Programming. Mixed Integer Nonlinear Programming, IMA Vol. Math. Appl., vol. 154 (2012), Springer: Springer New York), 373-405 · Zbl 1242.90122 |
| [29] | Cadoux, F., Computing deep facet-defining disjunctive cuts for mixed-integer programming, Math. Program., 122, 2, 197-223 (2010), (Ser. A) · Zbl 1184.90105 |
| [30] | Kılınç, M.; Linderoth, J.; Luedtke, J., Effective separation of disjunctive cuts for convex mixed integer nonlinear programs, Tech. Rep. (2010) |
| [31] | Modaresi, S.; Kılınç, M. R.; Vielma, J. P., Split cuts and extended formulations for mixed integer conic quadratic programming, Oper. Res. Lett., 43, 1, 10-15 (2015) · Zbl 1408.90201 |
| [32] | Vinel, A.; Krokhmal, P., On valid inequalities for mixed integer \(p\)-order cone programming, J. Optim. Theory Appl., 160, 2, 439-456 (2014) · Zbl 1300.90022 |
| [33] | Balas, E., Intersection cuts—a new type of cutting planes for integer programming, Oper. Res., 19, 19-39 (1971) · Zbl 0219.90035 |
| [34] | Andersen, K.; Jensen, A. N., Intersection cuts for mixed integer conic quadratic sets, (Integer Programming and Combinatorial Optimization. Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci., vol. 7801 (2013), Springer: Springer Heidelberg), 37-48 · Zbl 1346.90623 |
| [35] | Belotti, P.; Góez, J. C.; Pólik, I.; Ralphs, T. K.; Terlaky, T., A Conic Representation of the Convex Hull of Disjunctive Sets and Conic Cuts for Integer Second Order Cone Optimization, 1-35 (2015), Springer International Publishing: Springer International Publishing Cham · Zbl 1330.65083 |
| [36] | Bienstock, D.; Michalka, A., Cutting-planes for optimization of convex functions over nonconvex sets, SIAM J. Optim., 24, 2, 643-677 (2014) · Zbl 1334.90130 |
| [37] | Burer, S.; Kılınç-Karzan, F., How to convexify the intersection of a second order cone and a nonconvex quadratic, Tech. Rep. (2014) |
| [38] | Kılınç-Karzan, F., On minimal valid inequalities for mixed integer conic programs, Math. Oper. Res., 41, 2, 477-510 (2016) · Zbl 1338.90275 |
| [39] | Kılınç-Karzan, F.; Yıldız, S., Two-term disjunctions on the second-order cone, Math. Program., 154, 1, 463-491 (2015) · Zbl 1327.90137 |
| [40] | Rockafellar, R. T., Convex analysis, (Princeton Landmarks in Mathematics (1997), Princeton University Press: Princeton University Press Princeton, NJ), reprint of the 1970 original, Princeton Paperbacks · Zbl 0897.49014 |
| [41] | Auslender, A.; Teboulle, M., (Asymptotic Cones and Functions in Optimization and Variational Inequalities. Asymptotic Cones and Functions in Optimization and Variational Inequalities, Springer Monographs in Mathematics (2003), Springer-Verlag: Springer-Verlag New York) · Zbl 1017.49001 |
| [42] | Rockafellar, R. T.; Uryasev, S., Optimization of conditional value-at-risk, J. Risk, 2, 21-41 (2000) |
| [43] | Glineur, F., Computational experiments with a linear approximation of second order cone optimization, Tech. Rep. 0001 (2000), Service de Mathématique et de Recherche Opérationnelle, Faculté Polytechnique de Mons, Mons: Service de Mathématique et de Recherche Opérationnelle, Faculté Polytechnique de Mons, Mons Belgium |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
