Augmented Lagrangian dual augments the classical Lagrangian dual with a non-negative non-linear penalty function of the violation of the relaxed/dualized constraints in order to reduce the duality gap. We investigate the cases in which mixed integer convex optimization problems have an exact penalty representation using sharp augmenting functions (norms as augmenting penalty functions). We present a generalizable constructive proof technique for proving existence of exact penalty representations for mixed integer convex programs under specific conditions using the associated value functions. This generalizes the recent results for MILP (Feizollahi, Ahmed and Sun, 2017) and MIQP (Gu, Ahmed and Dey 2020) whilst also providing an alternative proof for the aforementioned along with quantification of the finite penalty parameter in these cases.

We seek the global minimum of a quadratic function $f$ with box constrained variables. For this goal, we underestimate $f$ by a convex piecewise-quadratic function defined as the maximum of $p\ge 1$ convex quadratic functions. We show that when $p\to \mathrm{\infty }$ the optimal solution of this relaxation converges to an optimal solution of the strong "Shor plus RLT" semi-definite relaxation of the initial problem. To compute the new relaxation, we introduce an iterative algorithm that adds convex quadratic cuts one by one in cutting plane fashion. The resulting convexification is tighter than the one produced by previous related methods that use $p=1$. Its integration into a spatial branch-and-bound algorithm brings a second advantage: compared to previous work, we can refine the lower bound at each node of the branching tree. Numerical results show that even a small value of p can often be enough to reduce the branching tree size by half compared to sticking to $p=1$. The resulting algorithm is also competitive in terms of CPU time compared to well-established solvers that rely on other techniques.

I would like to present a comprehensive study on a special case of the bipartite boolean quadric polytope, which we, the authors of a recently submitted paper to this topic, namely me, Dr. Robert Burlacu and Dr. Patrick Gemander, termed the if-then polytope. Our research introduces a novel class of valid inequalities, that are sufficient to fully characterize the if-then polytope. Moreover, we present a linear program that is able to separate these inequalities in polynomial time. The presentation will highlight the practical relevance of our findings through a comprehensive computational study. We were able to demonstrate the usefulness of separating the inequalities found in the state-of-the-art branch-and-cut solver Gurobi for a real-world timetabling application for an underground train system and instances of the quadratic assignment problem. By providing a complete description of the if-then polytope, our work contributes to a deeper understanding of binary quadratic problems with multiple-choice constraints. We believe that our research will have significant impact on multiple application fields: among others, fixed recourse stochastic problems, the quadratic assignment problem and piecewise linear relaxations of nonlinear terms.

Multlilinear constraints require that some variable is the product of other variables. In the talk I will explain different classes of cutting planes that can be applied if many such constraints are present in a MINLP. First I will discuss recent results about so-called flower inequalities in comparison to recursive McCormick linearizations. Second, separation algorithms for different classes of cutting planes will be analyzed in theory and in practice. This is joint work with Alberto Del Pia and Emily Schutte.