Top

Published in:

2020 | OriginalPaper | Chapter

Convex Quadratic Mixed-Integer Problems with Quadratic Constraints

Authors : Simone Göttlich, Kathinka Hameister, Michael Herty

Published in: Operations Research Proceedings 2019

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The efficient numerical treatment of convex quadratic mixed-integer optimization poses a challenging problem. Therefore, we introduce a method based on the duality principle for convex problems to derive suitable lower bounds that can used to select the next node to be solved within the branch-and-bound tree. Numerical results indicate that the new bounds allow the tree search to be evaluated quite efficiently compared to benchmark solvers.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

previous chapter A Steepest Feasible Direction Extension of the Simplex Method

next chapter The Bicriterion Maximum Flow Network Interdiction Problem in s-t-Planar Graphs

http://www.mathworks.com/matlabcentral/fileexchange/96-fminconset.

http://www.minlplib.org/instances.html.

Belotti, P., Kirches, C., Leyffer, S., Linderoth, J., Luedtke, J., Mahajan, A.: Mixed-integer nonlinear optimization. Acta Numer. 22, 1–131 (2013). https://doi.org/10.1017/S0962492913000032 CrossRef

Berthold, T.: Measuring the impact of primal heuristics. Oper. Res. Lett. 41(6), 611–614 (2013). https://doi.org/10.1016/S0167637713001181 CrossRef

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). https://doi.org/10.1016/j.disopt.2006.10.011 CrossRef

Bonami, P., Kilinç, M., Linderoth, J.: Algorithms and Software for Convex Mixed Integer Nonlinear Programs, pp. 1–39. Springer, New York (2012). https://doi.org/10.1007/978-1-4614-1927-3_1

Borchers, B., Mitchell, J.E.: An improved branch and bound algorithm for mixed integer nonlinear programs. Comput. Oper. Res. 21(4), 359–367 (1994). https://doi.org/10.1016/0305-0548(94)90024-8 CrossRef

Dakin, R.J.: A tree-search algorithm for mixed integer programming problems. Comput. J. 8(3), 250–255 (1965). https://doi.org/10.1093/comjnl/8.3.250 CrossRef

Fletcher, R., Leyffer, S.: Solving mixed integer nonlinear programs by outer approximation. Math. Program. 66(1–3), 327–349 (1994). https://doi.org/10.1007/BF01581153

Fletcher, R., Leyffer, S.: Numerical experience with lower bounds for MIQP branch-and-bound. SIAM J. Control Optim. 8(2), 604–616 (1998). https://doi.org/10.1137/S1052623494268455

Geiger, C., Kanzow, C.: Theorie und Numerik restringiererter Optimierungsaufgaben. Springer, Berlin (2002)

10.

Land, A.H., Doig, A.G.: An automatic method of solving discrete programming problems. Econometrica 28(3), 497 (1960). https://doi.org/10.2307/1910129 CrossRef

11.

Misener, R., Floudas, C.A.: GloMIQO: Global mixed-integer quadratic optimizer. J. Global Optim. 57, 3–30 (2013)CrossRef

12.

van Thoai, N.: Duality bound method for the general quadratic programming problem with quadratic constraints. J. Optim. Theory Appl. 107(2), 331–354 (2000). https://doi.org/10.1023/A:1026437621223

13.

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)

Title: Convex Quadratic Mixed-Integer Problems with Quadratic Constraints
Authors: Simone Göttlich
Kathinka Hameister
Michael Herty
Publisher: Springer International Publishing
Book: Operations Research Proceedings 2019
Print ISBN: 978-3-030-48438-5

Electronic ISBN: 978-3-030-48439-2

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-48439-2_15

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Premium Partner