Invited Session Thu.1.MA 041

Thursday, 10:30 - 12:00 h, Room: MA 041

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

Techniques for convex MINLPs


Chair: Jeff Linderoth



Thursday, 10:30 - 10:55 h, Room: MA 041, Talk 1

Pierre Bonami
On disjunctive cuts for mixed integer convex programs


We study the separation of disjunctive cuts for mixed integer nonlinear programs where the objective is linear and the relations between the decision variables are described by convex functions defining a convex feasible region. Our method can be seen as a practical implementation of the classical lift-and-project technique to the nonlinear case. To derive each cut we use a combination of a nonlinear programming subproblem and a linear outer approximation. One of the main features of the approach is that the nonlinear programming subproblems solved to generate cuts are typically not more complicated than the original continuous relaxation. In particular they do not require the introduction of additional variables and maintain the properties of the nonlinear functions describing the feasible region. We propose several strategies for using the technique and present computational evidence of its practical interest. In particular, the cuts allow us to improve the state of the art branch-and-bound of the solver Bonmin, solving more problems in faster computing times on average.



Thursday, 11:00 - 11:25 h, Room: MA 041, Talk 2

Ashutosh Mahajan
Algorithms for solving convex MINLPs with MINOTAUR

Coauthor: Sven Leyffer


MINOTAUR is an open-source software toolkit for implementing algorithms for mixed-integer nonlinear optimization problems. We will describe
the design features of the toolkit and present two new algorithms.
The first is a new tree-search algorithm for solving convex MINLPs. Rather than relying on computationally expensive nonlinear solves at every node of the branch-and-bound tree, our algorithm solves a quadratic approximation at every node. We show that the resulting algorithm retains global convergence properties for convex MINLPs, and we present numerical results on a range of test problems. The second is an algorithm for presolving MINLPs. In order to improve the formulation of a MINLP in the presolve, we directly manipulate the computational graph of nonlinear functions. Extensive computational results showing effects of presolving on different algorithms for convex MINLPs are provided using what we call `extended performance-profiles'. We show improvements of up to two orders of magnitude in running time for some classes of problems.



Thursday, 11:30 - 11:55 h, Room: MA 041, Talk 3

Andrew J. Miller
Valid inequalities for a nonseparable quadratic set

Coauthors: Hyemin Jeon, Jeff Linderoth


We describe approaches for finding strong valid inequalities for the convex hull of a quadratic mixed integer nonlinear set containing two integer variables that are linked by linear constraints. This study is motivated by the fact that such sets appear can be defined by a convex quadratic program, and therefore strong inequalities for this set may help to strengthen the formulation of the original problem.
A number of the inequalities that we define for this set are nonlinear (specifically conic). The techniques used to define strong inequalities include not only ideas related to perspective reformulations of MINLPs, but also disjunctive and lifting arguments. Initial computational tests will be presented.


  signature loans . What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.