Invited Session Tue.2.MA 005

Tuesday, 13:15 - 14:45 h, Room: MA 005

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

Advances in MINLP


Chair: Sarah Drewes



Tuesday, 13:15 - 13:40 h, Room: MA 005, Talk 1

Tamás Terlaky
Conic representation of the convex hull of disjunctions of convex sets and conic cuts for mixed integer second order cone optimization

Coauthors: Pietro Belotti, Julio C. Goez, Imre Pólik, Ted Ralphs


This talk gives some insight of how to design disjunctive conic cuts for mixed integer conic linear optimization problems. The novel disjunctive conic cuts may be used to design branch-and-cut algorithms for CLO problems.
Second order conic optimization (SOCO) has been the subject of intense study in the past two decades. Interior point methods (IPMs) provide polynomial time algorithms in theory, and powerful software tools in computational practice. Just as in linear and nonlinear optimization, the use of integer variables naturally occur in SOCO. Thus, the need for dedicated mixed integer SOCO algorithms and software is evident.
We present efficiently computable disjunctive conic cuts for MISOCO problems. The novel disjunctive conic cuts may be used to design branch-and-cut algorithms for MISOCO. Finally, some illustrative, preliminary computational results as presented when disjunctive conic cuts are used in solving MICOSO problems.



Tuesday, 13:45 - 14:10 h, Room: MA 005, Talk 2

Sarah Drewes
Cover inequalities and outer-approximation for mixed-01 SOCPs

Coauthor: Alper Atamtürk


We present how cover inequalities can be utilized in outer approximation based
branch and bound algorithms for mixed 0-1 convex nonlinear
programming problems in general and show more specific results for a class of mixed 0-1 second order cone programs.
The discussed class of algorithms use an outer approximation of the mixed 0-1 problem arising from linearizations of the nonlinear functions. Based on this outer approximations, assignments for the binary variables are derived which give rise to valid cover inequalities. These inequalities can then be lifted to derive strong valid inequalities that tighten the continuous relaxation of the outer approximation problem. The potential of this approach is discussed considering a class of mixed 0-1 second order cone programs for which a computational study is provided.



Tuesday, 14:15 - 14:40 h, Room: MA 005, Talk 3

Antonio Morsi
Solving MINLPs on loosely coupled networks

Coauthors: Bjoern Geissler, Alexander Martin, Lars Schewe


Considering MINLPs defined on a network structure, such as nonlinearly-constrained network flow problems, we obtain dual bounds on the overall problem by a decomposition of the underlying graph into its biconnected and triconnected components and by the relaxation of the coupling constraints between these components. The dual bounds are further tightened by branching on violated nonconvex constraints. Branching candidates are obtained from an approximate primal solution to the master problem, which is solved by a bundle method. To solve the subproblems, in the case of factorable MINLPs, we use Chebyshev approximation to compute univariate piecewise linearizations (or piecewise polynomials) of the arising nonlinearities in advance. These approximations lead to MILP relaxations, or mixed integer polynomial relaxations, of the subproblems. We conclude with computational results of our approach for two real-world applications, water and gas network optimization.


  Getting Payday Loans In California should be thought of many times. What can cause long-term use of Viagra Sale? 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.