Integration of polyhedral outer approximation algorithms with MIP solvers through callbacks and lazy constraints

Andreas Lundell; Jan Kronqvist

doi:10.1063/1.5088979

Integration of polyhedral outer approximation algorithms with MIP solvers through callbacks and lazy constraints

Andreas Lundell, Jan Kronqvist

Forskningsoutput: Kapitel i bok/konferenshandling › Konferensbidrag › Vetenskaplig › Peer review

1 Citeringar (Scopus)

Sammanfattning

In this paper, it is explained how algorithms for convex mixed-integer nonlinear programming (MINLP) based on polyhedral outer approximation (P0A) can be integrated with mixed-integer programming (MIP) solvers through callbacks and lazy constraints. Through this integration, a new approach utilizing a single branching tree is obtained which reduces the overhead required when rebuilding the branching tree in the MIP solver due to the continuous addition of linear constraints approximating the nonlinear feasible region of the MINLP problem. The result is an efficient strategy for implementing a POA utilized by the Supporting llyperplane Optimization Toolkit (SHOT) solver.

Originalspråk	Odefinierat/okänt
Titel på värdpublikation	Proceedings LeGO : 14th International Global Optimization Workshop : Leiden, the Netherlands, 18-21 September 2018
Redaktörer	Michael T. M. Emmerich, André H. Deutz, Sander C. Hille, Yaroslav D. Sergeyev
Förlag	American Institute of Physics
Sidor	–
Antal sidor	4
ISBN (tryckt)	978-0-7354-1798-4
DOI	https://doi.org/10.1063/1.5088979
Status	Publicerad - 2019
MoE-publikationstyp	A4 Artikel i en konferenspublikation
Evenemang	International Global Optimization Workshop - LeGO 14th International Global Optimization Workshop Varaktighet: 18 sep. 2018 → 21 sep. 2018

Konferens

Konferens	International Global Optimization Workshop
Period	18/09/18 → 21/09/18

Åtkomst av dokument

10.1063/1.5088979

Citera det här

Lundell, A., & Kronqvist, J. (2019). Integration of polyhedral outer approximation algorithms with MIP solvers through callbacks and lazy constraints. I M. T. M. Emmerich, A. H. Deutz, S. C. Hille, & Y. D. Sergeyev (Red.), Proceedings LeGO : 14th International Global Optimization Workshop : Leiden, the Netherlands, 18-21 September 2018 (s. –). American Institute of Physics. https://doi.org/10.1063/1.5088979

Lundell, Andreas ; Kronqvist, Jan. / Integration of polyhedral outer approximation algorithms with MIP solvers through callbacks and lazy constraints. Proceedings LeGO : 14th International Global Optimization Workshop : Leiden, the Netherlands, 18-21 September 2018. redaktör / Michael T. M. Emmerich ; André H. Deutz ; Sander C. Hille ; Yaroslav D. Sergeyev. American Institute of Physics, 2019. s. –

@inproceedings{24b12f30fb45460a805763e8f5675521,

title = "Integration of polyhedral outer approximation algorithms with MIP solvers through callbacks and lazy constraints",

abstract = "In this paper, it is explained how algorithms for convex mixed-integer nonlinear programming (MINLP) based on polyhedral outer approximation (P0A) can be integrated with mixed-integer programming (MIP) solvers through callbacks and lazy constraints. Through this integration, a new approach utilizing a single branching tree is obtained which reduces the overhead required when rebuilding the branching tree in the MIP solver due to the continuous addition of linear constraints approximating the nonlinear feasible region of the MINLP problem. The result is an efficient strategy for implementing a POA utilized by the Supporting llyperplane Optimization Toolkit (SHOT) solver.",

author = "Andreas Lundell and Jan Kronqvist",

note = "ast. De gick inte att {\"o}ppna bilagan, s{\aa} Linda tog bort den. Den slutliga PDF:en {\"a}r {\"o}ppet tillg{\"a}nglig p{\aa} n{\"a}tet, s{\aa} det r{\"a}cker med den.; null ; Conference date: 18-09-2018 Through 21-09-2018",

year = "2019",

doi = "10.1063/1.5088979",

language = "Odefinierat/ok{\"a}nt",

isbn = "978-0-7354-1798-4",

pages = "–",

editor = "{M. Emmerich}, {Michael T.} and Deutz, {Andr{\'e} H.} and Hille, {Sander C.} and Sergeyev, {Yaroslav D.}",

booktitle = "Proceedings LeGO : 14th International Global Optimization Workshop : Leiden, the Netherlands, 18-21 September 2018",

publisher = "American Institute of Physics",

}

Lundell, A & Kronqvist, J 2019, Integration of polyhedral outer approximation algorithms with MIP solvers through callbacks and lazy constraints. i MT M. Emmerich, AH Deutz, SC Hille & YD Sergeyev (red), Proceedings LeGO : 14th International Global Optimization Workshop : Leiden, the Netherlands, 18-21 September 2018. American Institute of Physics, s. –, International Global Optimization Workshop, 18/09/18. https://doi.org/10.1063/1.5088979

Integration of polyhedral outer approximation algorithms with MIP solvers through callbacks and lazy constraints. / Lundell, Andreas; Kronqvist, Jan.

Proceedings LeGO : 14th International Global Optimization Workshop : Leiden, the Netherlands, 18-21 September 2018. red. / Michael T. M. Emmerich; André H. Deutz; Sander C. Hille; Yaroslav D. Sergeyev. American Institute of Physics, 2019. s. –.

Forskningsoutput: Kapitel i bok/konferenshandling › Konferensbidrag › Vetenskaplig › Peer review

TY - GEN

T1 - Integration of polyhedral outer approximation algorithms with MIP solvers through callbacks and lazy constraints

AU - Lundell, Andreas

AU - Kronqvist, Jan

N1 - ast. De gick inte att öppna bilagan, så Linda tog bort den. Den slutliga PDF:en är öppet tillgänglig på nätet, så det räcker med den.

PY - 2019

Y1 - 2019

N2 - In this paper, it is explained how algorithms for convex mixed-integer nonlinear programming (MINLP) based on polyhedral outer approximation (P0A) can be integrated with mixed-integer programming (MIP) solvers through callbacks and lazy constraints. Through this integration, a new approach utilizing a single branching tree is obtained which reduces the overhead required when rebuilding the branching tree in the MIP solver due to the continuous addition of linear constraints approximating the nonlinear feasible region of the MINLP problem. The result is an efficient strategy for implementing a POA utilized by the Supporting llyperplane Optimization Toolkit (SHOT) solver.

AB - In this paper, it is explained how algorithms for convex mixed-integer nonlinear programming (MINLP) based on polyhedral outer approximation (P0A) can be integrated with mixed-integer programming (MIP) solvers through callbacks and lazy constraints. Through this integration, a new approach utilizing a single branching tree is obtained which reduces the overhead required when rebuilding the branching tree in the MIP solver due to the continuous addition of linear constraints approximating the nonlinear feasible region of the MINLP problem. The result is an efficient strategy for implementing a POA utilized by the Supporting llyperplane Optimization Toolkit (SHOT) solver.

U2 - 10.1063/1.5088979

DO - 10.1063/1.5088979

M3 - Konferensbidrag

SN - 978-0-7354-1798-4

SP - –

BT - Proceedings LeGO : 14th International Global Optimization Workshop : Leiden, the Netherlands, 18-21 September 2018

A2 - M. Emmerich, Michael T.

A2 - Deutz, André H.

A2 - Hille, Sander C.

A2 - Sergeyev, Yaroslav D.

PB - American Institute of Physics

Y2 - 18 September 2018 through 21 September 2018

ER -

Lundell A, Kronqvist J. Integration of polyhedral outer approximation algorithms with MIP solvers through callbacks and lazy constraints. I M. Emmerich MT, Deutz AH, Hille SC, Sergeyev YD, redaktörer, Proceedings LeGO : 14th International Global Optimization Workshop : Leiden, the Netherlands, 18-21 September 2018. American Institute of Physics. 2019. s. – doi: 10.1063/1.5088979