Repository: DepositOnce – institutional repository for research data and publications of TU Berlin https://depositonce.tu-berlin.de
TY - THES
AU - Müller, Benjamin
PY - 2020
TI - Tighter relaxations in mixed-integer nonlinear programming
T2 - Technische Universität Berlin
DO - 10.14279/depositonce-9889
UR - http://dx.doi.org/10.14279/depositonce-9889
PB - Technische Universität Berlin
M3 - Doctoral Thesis
CY - Berlin
LA - en
AB - Mixed-integer nonlinear programming (MINLP) is one of the most important classes of mathematical optimization problems that combines difficulties from mixed-integer linear programming and nonlinear programming, namely optimizing over a set that is described by integrality, linear, and nonlinear restrictions. This class of optimization problems is essential when constructing accurate models of real-world applications such as energy production and distribution, logistics, engineering design, manufacturing, and fields in chemical and biological sciences. To the best of our knowledge, all state-of-the-art algorithms for solving nonconvex MINLPs to global optimality are based on branch and bound. The performance of these algorithms mainly depends on tight relaxations of a MINLP that are refined throughout a tree search. For this reason, the contribution of this thesis is to present new methods to construct and strengthen relaxations for mixed-integer nonlinear programs.
One application of MINLP is the recursive circle packing problem (RCPP), which arises in the tube industry when packing pipes into rectangular containers. Solving a compact formulation for the RCPP is entirely out of reach for state-of-the-art MINLP solvers because relaxations for this problem are known to be weak. To construct significantly tighter relaxations, we present an exact reformulation of the RCPP that is based on a Dantzig-Wolfe decomposition of a nonconvex MINLP formulation. We use column generation techniques to design an algorithm that solves the continuous relaxation of the reformulation to global optimality. This relaxation is substantially tighter than relaxations for a compact MINLP formulation, which enables us to solve 287 out of 800 instances to global optimality that could not be solved so far.
The most fundamental ingredient in MINLP solvers is the well-known McCormick relaxation for a product of two variables x and y over a box-constrained domain. This relaxation is far from being tight if the feasible region of a MINLP and its convexification projected in the x-y-space is a strict subset of the box. We develop an algorithm that solves a sequence of linear programs to compute globally valid inequalities on x and y in a similar fashion as optimization-based bound tightening. These valid inequalities enable us to exploit polyhedral results from the literature to tighten the classic McCormick relaxation. Additionally, we present two novel propagation algorithms that compute stronger bounds for x, y, and xy. The resulting implementation reduces the average running time by 36% on difficult MINLPs.
Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solvers improved tremendously during the last decades and are nowadays able to solve problems with a moderate presence of nonconvexities. This progress opens the door for the use of potentially tighter relaxations that contain only a few nonconvexities. Such a nonconvex relaxation can be obtained via the aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We revisit these relaxations in a MINLP setting and show the computational benefits and challenges they can have. Additionally, we study a generalization of such relaxation that allows for multiple aggregations simultaneously and present the first algorithm in the literature that is capable of computing the best set of aggregations. We propose a multitude of computational enhancements for improving its practical performance and evaluate the algorithm’s ability to generate tight relaxations through extensive computational experiments. Our results show that we are able to improve the best known bounds for unsolved instances and decrease the average gap by a factor of two on difficult instances.
Finally, we present the concept of variable holes for nonconvex MINLPs. Due to the presence of nonconvex nonlinear constraints, the set of feasible assignments of a variable can be disconnected. The resulting forbidden regions are called variable holes and can be viewed as a generalization of integrality restrictions. By exploiting these holes, it is possible to strengthen the relaxation of a MINLP by applying techniques that have been exclusively developed for integer variables to continuous variables. Unfortunately, computing a variable hole is in general NP-hard. Still, for many MINLPs, it is enough to consider relaxations that are described by few constraints to detect variable holes. Based on this observation, we develop three algorithms that are capable of computing variable holes for practical instances. Our computational study shows that integrating variable holes into pseudo cost branching rules decreases the average running time by 62% on affected instances.
KW - mixed-integer nonlinear programming
KW - nonconvex
KW - global optimization
KW - relaxations
KW - gemischt-ganzzahlige nichtlineare Programmierung
KW - nichtkonvex
KW - globale Optimierung
KW - Relaxierungen
ER -