nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

A Conic Representation of the Convex Hull of Disjunctive Sets and Conic Cuts for Integer Second Order Cone Optimization

verfasst von : Pietro Belotti, Julio C. Góez, Imre Pólik, Ted K. Ralphs, Tamás Terlaky

Erschienen in: Numerical Analysis and Optimization

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We study the convex hull of the intersection of a convex set E and a disjunctive set. This intersection is at the core of solution techniques for Mixed Integer Convex Optimization. We prove that if there exists a cone K (resp., a cylinder C) that has the same intersection with the boundary of the disjunction as E, then the convex hull is the intersection of E with K (resp., C).The existence of such a cone (resp., a cylinder) is difficult to prove for general conic optimization. We prove existence and unicity of a second order cone (resp., a cylinder), when E is the intersection of an affine space and a second order cone (resp., a cylinder). We also provide a method for finding that cone, and hence the convex hull, for the continuous relaxation of the feasible set of a Mixed Integer Second Order Cone Optimization (MISOCO) problem, assumed to be the intersection of an ellipsoid with a general linear disjunction. This cone provides a new conic cut for MISOCO that can be used in branch-and-cut algorithms for MISOCO problems.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nächstes Kapitel Runge–Kutta Methods for Ordinary Differential Equations

Nur mit Berechtigung zugänglich

A cone is called a conic cut if it cuts off some non-integer solutions but none of the feasible integer solutions.

Lemma 8.2 in Barvinok [7, page 65] and Theorems 11.3 and 11.7 in Rockafeller [23, pages 97 and 100].

Atamtürk, A., Narayanan, V.: Conic mixed-integer rounding cuts. Math. Program. 122(1), 1–20 (2010)CrossRefMathSciNetMATH

Atamtürk, A., Narayanan, V.: Lifting for conic mixed-integer programming. Math. Program. A 126, 351–363 (2011)CrossRefMATH

Atamtürk, A., Berenguer, G., Shen, Z.J.: A conic integer programming approach to stochastic joint location-inventory problems. Oper. Res. 60(2), 366–381 (2012)CrossRefMathSciNetMATH

Balas, E.: Disjunctive programming. In: Hammer, P.L., Johnson, E.L., Korte, B.H. (eds.) Annals of Discrete Mathematics 5: Discrete Optimization, pp. 3–51. North Holland, Amsterdam, The Netherlands (1979)

Balas, E.: Disjunctive programming: properties of the convex hull of feasible points. Discret. Appl. Math. 89(1–3), 3–44 (1998)CrossRefMathSciNetMATH

Balas, E., Ceria, S., Cornuéjols, G.: A lift-and-project cutting plane algorithm for mixed 0–1 programs. Math. Program. 58, 295–324 (1993)CrossRefMATH

Barvinok, A.: A Course in Convexity. American Mathematical Society, Providence, RI (2002)CrossRefMATH

Belotti, P., Góez, J., Pólik, I., Ralphs, T., Terlaky, T.: On families of quadratic surfaces having fixed intersections with two hyperplanes. Discret. Appl. Math. 161(16–17), 2778–2793 (2013)CrossRefMATH

Ben-Tal, A., Nemirovski, A.: On polyhedral approximations of the second-order cone. Math. Oper. Res. 26(2), 193–205 (2001)CrossRefMathSciNetMATH

10.

Bertsimas, D., Shioda, R.: Algorithm for cardinality-constrained quadratic optimization. Comput. Optim. Appl. 43(1), 1–22 (2009)CrossRefMathSciNetMATH

11.

Çezik, M., Iyengar, G.: Cuts for mixed 0–1 conic programming. Math. Program. 104(1), 179–202 (2005)CrossRefMathSciNetMATH

12.

Cornuéjols, G.: Valid inequalities for mixed integer linear programs. Math. Program. 112(1), 3–44 (2008)CrossRefMathSciNetMATH

13.

Cornuéjols, G., Lemaréchal, C.: A convex-analysis perspective on disjunctive cuts. Math. Program. 106(2), 567–586 (2006)CrossRefMathSciNetMATH

14.

Dadush, D., Dey, S., Vielma, J.: The split closure of a strictly convex body. Oper. Res. Lett. 39(2), 121–126 (2011)CrossRefMathSciNetMATH

15.

Drewes, S.: Mixed integer second order cone programming. Ph.D. thesis, Technische Universität Darmstadt, Germany (2009)

16.

Fampa, M., Maculan, N.: Using a conic formulation for finding Steiner minimal trees. Numer. Algorithms 35(2), 315–330 (2004)CrossRefMathSciNetMATH

17.

Grossmann, I.E.: Review of nonlinear mixed-integer and disjunctive programming techniques. Optim. Eng. 3, 227–252 (2002)CrossRefMathSciNetMATH

18.

Júdice, J.J., Sherali, H.D., Ribeiro, I.M., Faustino, A.M.: A complementarity-based partitioning and disjunctive cut algorithm for mathematical programming problems with equilibrium constraints. J. Glob. Optim. 36, 89–114 (2006)CrossRefMATH

19.

Krokhmal, P.A., Soberanis, P.: Risk optimization with p-order conic constraints: a linear programming approach. Eur. J. Oper. Res. 201(3), 653–671 (2010)CrossRefMathSciNetMATH

20.

Kumar, M., Torr, P., Zisserman, A.: Solving Markov random fields using second order cone programming relaxations. In: 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 1, pp. 1045–1052 (2006)

21.

Masihabadi, S., Sanjeevi, S., Kianfar, K.: n-Step conic mixed integer rounding inequalities. Optimization Online (2011). http://www.optimization-online.org/DB_HTML/2011/11/3251.html

22.

Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley-Interscience, New York (1999)MATH

23.

Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)MATH

24.

Stubbs, R.A., Mehrotra, S.: A branch-and-cut method for 0–1 mixed convex programming. Math. Program. 86(3), 515–532 (1999)CrossRefMathSciNetMATH

25.

Vielma, J., Ahmed, S., Nemhauser, G.: A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs. INFORMS J. Comput. 20(3), 438–450 (2008)CrossRefMathSciNetMATH

Titel: A Conic Representation of the Convex Hull of Disjunctive Sets and Conic Cuts for Integer Second Order Cone Optimization
verfasst von: Pietro Belotti
Julio C. Góez
Imre Pólik
Ted K. Ralphs
Tamás Terlaky
Verlag: Springer International Publishing
Buch: Numerical Analysis and Optimization
Print ISBN: 978-3-319-17688-8

Electronic ISBN: 978-3-319-17689-5

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-17689-5_1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner