## On convex relaxations of quadrilinear terms

The best known method to find exact or at least epsilon-approximate solutions to polynomial programming problems is the spatial Branch-and-Bound algorithm, which rests on computing lower bounds to the value of the objective function to be minimized on each region that it explores. These lower bounds are often computed by solving convex relaxations of the … Read more

## The Integer Approximation Error in Mixed-Integer Optimal Control

We extend recent work on nonlinear optimal control problems with integer restrictions on some of the control functions (mixed-integer optimal control problems, MIOCP) in two ways. We improve a theorem that states that the solution of a relaxed and convexified problem can be approximated with arbitrary precision by a solution fulfilling the integer requirements. Unlike … Read more

## Reformulations in Mathematical Programming: Symmetry

If a mathematical program (be it linear or nonlinear) has many symmetric optima, solving it via Branch-and-Bound techniques often yields search trees of disproportionate sizes; thus, finding and exploiting symmetries is an important task. We propose a method for automatically finding the formulation group of any given Mixed-Integer Nonlinear Program, and reformulating the problem so … Read more

## Reformulations and Algorithms for the Optimization of Switching Decisions in Nonlinear Optimal Control

In model-based nonlinear optimal control switching decisions that can be optimized often play an important role. Prominent examples of such hybrid systems are gear switches for transport vehicles or valves in chemical engineering. Optimization algorithms need to take the discrete nature of the variables that model these switching decisions into account. Unnecessarily, for many applications … Read more

## Convex Relaxations of Non-Convex Mixed Integer Quadratically Constrained Programs: Projected Formulations

A common way to produce a convex relaxation of a Mixed Integer Quadratically Constrained Program (MIQCP) is to lift the problem into a higher dimensional space by introducing variables \$Y_{ij}\$ to represent each of the products \$x_i x_j\$ of variables appearing in a quadratic form. One advantage of such extended relaxations is that they can … Read more

## Strong Valid Inequalities for Orthogonal Disjunctions and Bilinear Covering Sets

In this paper, we develop a convexification tool that enables the construction of convex hulls for orthogonal disjunctive sets using convex extensions and disjunctive programming techniques. A distinguishing feature of our technique is that, unlike most applications of disjunctive programming, it does not require the introduction of new variables in the relaxation. We develop and … Read more

## Convex Relaxations of Non-Convex Mixed Integer Quadratically Constrained Programs: Extended Formulations

This paper addresses the problem of generating strong convex relaxations of Mixed Integer Quadratically Constrained Programming (MIQCP) problems. MIQCP problems are very difficult because they combine two kinds of non-convexities: integer variables and non-convex quadratic constraints. To produce strong relaxations of MIQCP problems, we use techniques from disjunctive programming and the lift-and-project methodology. In particular, … Read more

## Branching and bounds tightening techniques for non-convex MINLP

Many industrial problems can be naturally formulated using Mixed Integer Nonlinear Programming (MINLP). Motivated by the demand for Open-Source solvers for real-world MINLP problems, we have developed a spatial Branch-and-Bound software package named COUENNE (Convex Over- and Under-ENvelopes for Nonlinear Estimation). In this paper, we present the structure of couenne and discuss in detail our … Read more

## Disjunctive Cuts for Non-Convex Mixed Integer Quadratically Constrained Programs

This paper addresses the problem of generating strong convex relaxations of Mixed Integer Quadratically Constrained Programming (MIQCP) problems. MIQCP problems are very difficult because they combine two kinds of non-convexities: integer variables and non-convex quadratic constraints. To produce strong relaxations of MIQCP problems, we use techniques from disjunctive programming and the lift-and-project methodology. In particular, … Read more

## MINLP Strengthening for Separable Convex Quadratic Transportation-Cost UFL

In the context of a variation of the standard UFL (Uncapacitated Facility Location) problem, but with an objective function that is a separable convex quadratic function of the transportation costs, we present some techniques for improving relaxations of MINLP formulations. We use a disaggregation principle and a strategy of developing model-specific valid inequalities (some nonlinear), … Read more