Invited Session Mon.3.MA 005

Monday, 15:15 - 16:45 h, Room: MA 005

Cluster 14: Mixed-integer nonlinear programming [...]

Tight relaxations


Chair: Stefan Vigerske



Monday, 15:15 - 15:40 h, Room: MA 005, Talk 1

Thomas Lehmann
On the efficient construction of disjunctive cutting planes for mixed-integer quadratic optimization problems


We present an algorithmic procedure for efficiently constructing disjunctive cutting planes for non-basic solutions or proving their non-existence. The method extends an algorithm proposed by Perregaard and Balas, such that it is applicable for non-basic solutions, e.g., obtained from the continuous relaxation of a mixed-integer quadratic program.
We also present preliminary numerical results for test problems, that arise within MIQP-based solution methods for mixed-integer nonlinear optimization problems, such as MISQP proposed by Exler, Lehmann and Schittkowski. The results indicate the potential of the proposed cut generator, but they also stress the necessity of an advanced cut management.



Monday, 15:45 - 16:10 h, Room: MA 005, Talk 2

Dennis Michaels
The convex hull of vectors of functions

Coauthors: Martin Ballerstein, Robert Weismantel


A challenging task in global optimization is to construct tight convex relaxations that provide reasonably globally valid bounds on a mixed-integer nonlinear program (MINLP). For a general MINLP, convex relaxations are usually obtained by replacing each non-linearity by convex under- and concave overestimators. The mathematical object studied to derive such estimators is given by the convex hull of the graph of the function over the relevant domain.
To derive improved relaxations, we consider a finite set of
given functions as a vector-valued function and study the
convex hull of its graph. We establish a link between such
a convex hull object and the convex hulls of the graphs of a certain family of real-valued functions. This link can be used to define improved relaxations. We especially focus on small sets of well-structured univariate functions. Numerical examples are presented demonstrating the impact of this concept.



Monday, 16:15 - 16:40 h, Room: MA 005, Talk 3

Ambros Gleixner
Rapid optimality-based bound tightening

Coauthors: Timo Berthold, Stefan Weltge


Optimality-based bound tightening (OBBT) is a well-known, simple, yet computationally expensive procedure to reduce variable domains of mixed-integer nonlinear programs (MINLPs) by solving a series of auxiliary linear programs (LPs). We present techniques to reduce the computational effort incurred by OBBT and exploit dual information from the LP solutions during a subsequent branch-and-bound solution process. We evaluate the performance impact of these techniques using an implementation within the MINLP solver SCIP.


  There are three major facts that should be watched out for in all payday loans in the United States. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis Online is the one that definitely differs from all other products.