Laboratoire d'informatique de l'École polytechnique

PhD thesis defence of Luca Mencarelli: «The Multiplicative Weights Algorithm for Mixed Integer NonLinear Programming: Theory, Applications and Limits»

Speaker: Luca Mencarelli
Location: Gilles Khan room, Alan Turing building
Date: Mon, 4 Dec 2017, 14:00-16:00

Luca Mencarelli will defend his PhD thesis entitled “The Multiplicative Weights Algorithm for Mixed Integer NonLinear Programming: Theory, Applications and Limits” on Monday December 4th 2017 at 2:00 PM in the Gilles Khan room (Bâtiment Alan Turing).

Abstract: In this thesis we introduce a new heuristic algorithm for Mixed Integer NonLinear Programming (MINLP) based on the Multiple Weights Update (MWU) framework and involving a new class of Mathematical Programming (MP) reformulations, namely the pointwise reformulations. The MWU algorithm is a “meta-algorithm” with broad application in Mathematical Optimization, Machine Learning, and Game Theory. MINLP is a very interesting topic in Mathematical Optimization both for a theoretical and computational viewpoint. Moreover, formulations and reformulations constitute a key tool in MP: pointwise reformulation are a family of MINLPs, where several “complicated” terms are substituted with parameters in order to obtain easier problems.

The thesis is divided into three main parts. In the first part we introduce the more important ingredients for the heuristic algorithm, in the second one we theoretically describe the new algorithm and in the last one we practically apply the new methodology to two hard real-world problems, namely the Mean-Variance Portfolio Selection (MVPS) and the Multiple NonLinear Knapsack Problem (MNLKP). The first problem arises in financial portfolio context, where investors want to identify the portfolio with the highest return and the minimum volatility or risk; while the second problem occurs, for example, in resource allocation, where a set of resources with limited capacities must be divided among different categories.

Computational experiments indicate the new methodology behaves rather better that the benchmarks for the MVPS problems, while this is not the case for the MNLKP. Therefore, we propose a different constructive heuristic based on three different phases: a procedure based on the discretisation of the solution space and two procedures for the feasibility recovering of the solution produced by the surrogate relaxation. The constructive heuristic outperforms the benchmarks both with respect of the quality of the solution found and of the total elapsed time.