×

zbMATH — the first resource for mathematics

Perspective reformulations of mixed integer nonlinear programs with indicator variables. (English) Zbl 1229.90106
In this paper the authors study mixed integer nonlinear programs (MINLP) that are driven by a collection of indicator variables where each indicator variable controls a subset of decision variables.
Based on this work some concepts that have been applied successfully in the case of mixed integer linear programs (MILP) can be applied for MINLP. In order to apply these ideas, the authors analyse simple sets that form the structures of many practical MINLPs and than the results are extended to more general sets.
Finally, the described ideas are applied to three problems: a quadratic uncapacitated facility location problem, a network design problem with nonlinear congestion constraints and a portfolio optimization problem with buy-in thresholds.

MSC:
90C11 Mixed integer programming
90C30 Nonlinear programming
90C90 Applications of mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abhishek, K., Leyffer, S., Linderoth, J.T.: FilMINT: an outer-approximation-based solver for nonlinear mixed integer programs. Preprint ANL/MCS-P1374-0906, Mathematics and Computer Science Division, Argonne National Lab, 2006 · Zbl 1243.90142
[2] Aktürk, S., Atamtürk, A., Gürel, S.: A strong conic quadratic reformulation for machine-job assignment with controllable processing times. Technical Report BCOL Research Report 07.01, Industrial Engineering & Operations Research, University of California, Berkeley, April 2007. Oper. Res. Lett. 37, 187–191 (2009) · Zbl 1167.90518
[3] Atamtürk, A., Narayanan, V.: Conic mixed integer rounding cuts. Math. Program. (2008) (Forthcoming) · Zbl 1184.90112
[4] Balas E., Ceria S., Corneujols G.: A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math. Program. 58, 295–324 (1993) · Zbl 0796.90041 · doi:10.1007/BF01581273
[5] Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization. SIAM, 2001. MPS/SIAM Series on Optimization · Zbl 0986.90032
[6] Bertsekas D., Gallager R.: Data Networks. Endlewood Cliffs, Prentice-Hall (1987)
[7] Bienstock D.: Computational study of a family of mixed-integer quadratic programming problems. Math. Program. 74, 121–140 (1996) · Zbl 0855.90090
[8] Bienstock D., Günlük O.: Capacitated network design–polyhedral structure and computation. ORSA J. Comput. 8, 243–260 (1996) · Zbl 0871.90031
[9] 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, 186–204 (2008) · Zbl 1151.90028 · doi:10.1016/j.disopt.2006.10.011
[10] Boorstyn R., Frank H.: Large-scale network topological optimization. IEEE Trans. Commun. 25, 29–47 (1977) · Zbl 0361.94044 · doi:10.1109/TCOM.1977.1093708
[11] Borchers B., Mitchell J.E.: An improved branch and bound algorithm for mixed integer nonlinear programs. Comput. Oper. Res. 21, 359–368 (1994) · Zbl 0797.90069 · doi:10.1016/0305-0548(94)90024-8
[12] Ceria S., Soares J.: Convex programming for disjunctive optimization. Math. Program. 86, 595–614 (1999) · Zbl 0954.90049 · doi:10.1007/s101070050106
[13] Cezik M.T., Iyengar G.: Cuts for mixed 0-1 conic programming. Math. Program. 104, 179–202 (2005) · Zbl 1159.90457 · doi:10.1007/s10107-005-0578-3
[14] Frangioni A., Gentile C.: Perspective cuts for a class of convex 0-1 mixed integer programs. Math. Program. 106, 225–236 (2006) · Zbl 1134.90447 · doi:10.1007/s10107-005-0594-3
[15] Frangioni A., Gentile C.: Sdp diagonalizations and perspective cuts for a class of nonseparable miqp. Oper. Res. Lett. 35, 181–185 (2007) · Zbl 1149.90379 · doi:10.1016/j.orl.2006.03.008
[16] Gomory, R.E.: An algorithm for the mixed integer problem. Technical Report RM-2597, The RAND Corporation, 1960 · Zbl 0095.14502
[17] Grossmann, I., Lee S.: Generalized convex disjunctive programming: Nonlinear convex hull relaxation. Comput. Optim. Appl. 83–100 (2003) · Zbl 1030.90069
[18] Günlük, O., Linderoth, J.: Perspective relaxation of mixed integer nonlinear programs with indicator variables. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008: The Thirteenth Conference on Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 5035, pp. 1–16 (2008) · Zbl 1143.90364
[19] Günlük, O., Linderoth, J.: Perspective relaxation of mixed integer nonlinear programs with indicator variables. Technical Report RC24694 (W0811-076), IBM Research Division, November 2008 · Zbl 1143.90364
[20] Günlük, O., Lee, J., Weismantel, R.: MINLP strengthening for separaable convex quadratic transportation-cost ufl. Technical Report RC24213 (W0703-042), IBM Research Division, March 2007
[21] Horst H., Pardalos P.M., Thoai V.: Introduction to Global Optimization. Kluwer, Dordrecht (1995) · Zbl 0836.90134
[22] Jobst N.J., Horniman M.D., Lucas C.A., Mitra G.: Computational aspects of alternative portfolio selection models in the presence of discrete asset choice constraints. Quant. Finance 1, 489–501 (2001) · doi:10.1088/1469-7688/1/5/301
[23] Kocis G.R., Grossmann I.E.: Computational experience with DICOPT solving MINLP problems in process systems engineering. Comput. Chem. Eng. 13, 307–315 (1989) · doi:10.1016/0098-1354(89)85008-2
[24] Lee J.: Mixed-integer nonlinear programming: some modeling and solution issues. IBM J. Res. Dev. 51, 489–497 (2007) · Zbl 05420261 · doi:10.1147/rd.513.0489
[25] Magnanti T., Mirchandani P.: Shortest paths, single origin-destination network design and associated polyhedra. Networks 23, 103–121 (1993) · Zbl 0791.90064 · doi:10.1002/net.3230230205
[26] Markowitz H.M.: Portfolio selection. J. Finance 7, 77–91 (1952) · doi:10.2307/2975974
[27] mosek. The mosek optimization tools manual. version 5.0 (revision 84), 2008. www.mosek.com
[28] Nemhauser G., Wolsey L.: A recursive procedure for generating all cuts for 0-1 mixed integer programs. Math. Program. 46, 379–390 (1990) · Zbl 0735.90049 · doi:10.1007/BF01585752
[29] Perold A.F.: Large-scale portfolio optimization. Manag. Sci. 30, 1143–1160 (1984) · Zbl 0548.90008 · doi:10.1287/mnsc.30.10.1143
[30] Quesada I., Grossmann I.E.: An LP/NLP based branch–and–bound algorithm for convex MINLP optimization problems. Comput. Chem. Eng. 16, 937–947 (1992) · doi:10.1016/0098-1354(92)80028-8
[31] Stubbs R., Mehrotra S.: A branch-and-cut method for 0-1 mixed convex programming. Math. Program. 86, 515–532 (1999) · Zbl 0946.90054 · doi:10.1007/s101070050103
[32] Stubbs, R.A.: Branch-and-Cut Methods for Mixed 0-1 Convex Programming. PhD thesis, Northwestern University, December 1996
[33] Sturm J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11(12), 625–653 (1999) · Zbl 0973.90526 · doi:10.1080/10556789908805766
[34] Tawarmalani M., Sahinidis N.V.: Global optimization of mixed integer nonlinear programs: a theoretical and computational study. Math. Program. 99, 563–591 (2004) · Zbl 1062.90041 · doi:10.1007/s10107-003-0467-6
[35] Wächter A., Biegler L.T.: On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Math. Program. 106(1), 25–57 (2006) · Zbl 1134.90542 · doi:10.1007/s10107-004-0559-y
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.