Accueil des participants

Mixed Integer Non Linear Programming

Claudia D'Ambrosio

(CNRS, LIX)

In this tutorial we aim at surveying on the fundamentals of theoretical and practical aspects of mixed integer non linear programming (MINLP). MINLPs are very powerful and challenging optimization problems that can represent an extremely large variety of real-world applications. The first part of the tutorial will be devoted to an introduction to MINLP in general and on algorithm for nonconvex MINLPs. In the second part, we will consider some well-structured classes of nonconvex MINLPs and introduce tailored methods solve them.

Pause café

Intégration d'une méthode de points intérieurs dans LocalSolver 9.0

Nikolas Stott

(LocalSolver)

Les méthodes de points intérieurs sont une classe d'algorithmes numériques permettant de résoudre efficacement des problèmes d'optimisation en variables réelles, notamment ceux qui sont fortement contraints. Elles ont été introduites par Karmarkar pour la résolution de programmes linéaires et ont rapidement été généralisées à la résolution de programmes non-linéaires. La même idée est au coeur de ces méthodes : déplacer les contraintes dans l'objectif du problème sous la forme d'une pénalisation de type barrière à l'aide d'un paramètre $\mu$ et effectuer des itérations du second ordre (généralement moins de 50) sur les équations d'optimalité (KKT) en faisant décroître $\mu$ vers 0, pour obtenir la solution optimale du problème (localement optimale pour des problèmes non-linéaires). Nous présentons l'implémentation d'une telle méthode dans LocalSolver. L'algorithme est inspiré d'une méthode récente développée par Hinder et Ye, qui propose de décaler la barrière dans le sens de l'infaisabilité, et de la rapprocher de la vraie barrière lorsque $\mu$ tend vers 0. Cette approche possède plusieurs avantages. Tout d'abord, ce décalage permet de s'affranchir des contraintes d'égalité en les remplaçant par des inégalités, sans compromettre la stabilité numérique de la résolution ou l'explosion des multiplicateurs de Lagrange trop près de l'optimum. De plus, l'absence d'une "phase de secours" comme dans de nombreux autres solveurs et une pénalisation des non-convexités innovante améliorent grandement la stabilité globale de l'algorithme. Nous validons ce nouvel algorithme sur un benchmark de problèmes non-linéaires. Ces tests révèlent que la méthode de points intérieurs implémentée se compare favorablement à d'autres solveurs existants et que son intégration dans LocalSolver 9.0 permet de résoudre à l'optimum deux fois plus de problèmes d'optimisation continue qu'avec la version 8.5.

Pause déjeuner

Nonlinear optimization of mixed continuous and discrete variables for black-box simulators

Thi-Thoi Tran

(IFPEN)

The form of the problem we address is the following : min f_b(x, y) such that x ∈ [x^L, x^U] ∩ Rⁿ, y ∈ {0, 1}^m, g(x, y) ≤ 0 and g_b(x, y) ≤ 0 where the objective function f_b and some constraints g_b are outputs of a "blackbox" mechanical simulator, and g are analytic constraints. We are interested in the optimal design of bladed disks for aircraft industry : the objective is the maximization of the compressor efficiency under some stability constraints (minimal vibrations) by mixing two different pre-defined shapes of blades. A binary variable y_i is associated to each blade, value 0 is for a reference shape and value 1 for the other pre-defined shape. x are shape parameters associated to the two pre-defined blade shapes. Thus, the optimization provides the distribution of the two shapes around the turbine disk. In this talk, we will discuss the formulation of an appropriate distance with respect to discrete variables which can deal with the cyclic symmetry property of the system under study. The necklace concept is used to characterize similar blade configurations and an adapted distance is proposed and evaluated from results of a simplified model of the application. This distance will be integrated in the exploration phase of the derivative free trust region optimization method extended to mixed binary problems.

Bilevel programming and the computation of pessimistic single-leader-multi-follower equilibria in Stackelberg games

Stefano Coniglio

(University of Southampton)

We give a very broad overview of bilevel programming problems and their relationship with Stackelberg games, with focus on two classical limitations of this paradigm: the presence of a single follower and the assumption of optimism. We then investigate the problem of computing an equilibrium in Stackelberg games with two or more noncooperating followers who react to the strategy chosen by the leader by playing a Nash Equilibrium, focusing, in particular, on the pessimistic case where, if the follower's game (parameterized by the leader's strategy) admits more Nash equilibria, the followers choose one which minimizes the leader's utility. We then address the case where the followers are restricted to pure strategies, illustrate some hardness and inapproximability results, and the concentrate on exact solution algorithms. After proposing a single-level (but undecidable) reformulation for the problem, we propose an exact implicit enumeration algorithm capable of computing the supremum of the problem as well as an alpha-approximate strategy, for any nonnegative alpha. Experimental results are presented and illustrated, showing the viability of our approach.

Pause café

Approximated perspective relaxations: a project and lift approach

Fabio Furini

(Université Paris-Dauphine)

The perspective reformulation (PR) of a Mixed-Integer NonLinear Program with semi-continuous variables is obtained by replacing each term in the (separable) objective function with its convex envelope. Solving the corresponding continuous relaxation requires appropriate techniques. Under some rather restrictive assumptions, the Projected PR (P2R) can be defined where the integer variables are eliminated by projecting the solution set onto the space of the continuous variables only. This approach produces a simple piecewise-convex problem with the same structure as the original one; however, this prevents the use of general-purpose solvers, in that some variables are then only implicitly represented in the formulation. We show how to construct an Approximated Projected PR (AP2R) whereby the projected formulation is “lifted” back to the original variable space, with each integer variable expressing one piece of the obtained piecewise-convex function. In some cases, this produces a reformulation of the original problem with exactly the same size and structure as the standard continuous relaxation, but providing substantially improved bounds. In the process we also substantially extend the approach beyond the original P2R development by relaxing the requirement that the objective function be quadratic and the left endpoint of the domain of the variables be non-negative. While the AP2R bound can be weaker than that of the PR, this approach can be applied in many more cases and allows direct use of off-the-shelf MINLP software; this is shown to be competitive with previously proposed approaches in some applications.

Optimal Power Flow : non convex quadratically convex problem for electric grid management.

Jean Maeght

(RTE)

RTE is the French TSO Transmission System Operator, owns and operates the high voltage electric grid (63kV to 400kV). Modeling of power flow on the grid needs products of complex variables representing voltages and currents. Translation to real numbers gives either trigonometric functions (polar coordinates) or quadratically constrained problems (cartesian coordinates).
Since the late 90’, in both cases interior point methods give (good ?) feasible solutions. For lower bounds, linear relaxations are very bad. About 10 years ago, SDP relaxations have been proposed for the Cartesian formulation. Bounds are indeed very good, proving that original interior point solution are good. Many other conic relaxations have been proposed. Polynomial optimization (Lasserre Hierarchy) could in some case solve large instances, but not all.
Still the gap is not yet closed and no efficient method nor software is available to achieve the global optimality for OPF quest.
Our approach is based on specialization the Mixed-Integer Quadratic Convex Reformulation method (MIQCR) to OPF.