On cutting planes for mixed-integer nonlinear programming

Mixed-integer nonlinear programming is a powerful technology that allows us to model and solve problems involving nonlinear functions, continuous, and discrete variables. The state-of-the-art solvers of mixed-integer nonlinear programs (MINLPs) use a combination of, among other techniques, branch- and-bound and cutting planes. In the late ’90s, solvers for mixed-integer linear programs saw an increase in performance due to the incorporation of general- purpose cutting planes. In this thesis, we deepen our understanding of a classical cutting planes algorithm, develop a strengthening technique, and two new cutting planes for MINLPs. We first show that Veinott’s supporting hyperplane algorithm is a particular case of Kelley’s cutting plane algorithm. We further extend the applicability of Veinott’s supporting hyperplane algorithm to solve convex problems repre- sented by non-convex functions. We then develop a technique to strengthen cutting planes for non-convex MINLPs. Many cuts for non-convex MINLPs strongly rely on the domain of the variables: tighter bounds produce tighter cuts. Using the point to be separated, we show that we can restrict the feasible region and still ensure the validity of the resulting cutting plane. Finally, we develop two intersection cuts for non-convex MINLP. The first one is a technique to construct S-free sets for any factorable MINLP. For the second one, we show how to build maximal quadratic-free sets, from which we compute intersection cuts. These last cuts reduce the average running time of the solver SCIP by 20% on hard MINLPs.

Author dc:creator

• Serrano Musalem, Felipe

Advisor dc:contributor.advisor

• Koch, Thorsten

Licence dc:rights.uri

• https://creativecommons.org/licenses/by/4.0/

Language dc:language.iso

en

Identifier URI

http://dx.doi.org/10.14279/depositonce-12180

OAI identifier oai:identifier

oai:depositonce.tu-berlin.de:11303/13396