SPOC 10 "Optimisation robuste et Programmation mathématique"

Date: 
Vendredi, 6 décembre, 2013

10ème Séminaire POC

Le VENDREDI 06 DECEMBRE 2013

Au laboratoire LIP6 de l’Université Pierre et Marie Curie - Paris 6
4 place Jussieu Paris 6 CEDEX 05

Tour 26 - Premier étage - Couloir 25-26 - Salle 105

 Accès

Sur le thème

"Optimisation robuste et Programmation mathématique"

Merci de remplir le formulaire d’inscription

INSCRITS à la journée SPOC10

9h30-10h00 Accueil des participants
10h00-11h00 On risk averse strategies for multistage mixed 0-1 / pure combinatorial optimization under a mixture of Exogenous and Endogenous Uncertainty

Laureano F. ESCUDERO
(Universidad Rey Juan Carlos, Madrid)

Résumé

 

11h00-12h00 Robust LP with Right-Hand side Uncertainty, Complexity Results and Applications

Michel Minoux
(Université Pierre et Marie Curie - LIP6)

The talk will focus on the class of so-called ‘2-stage robust
linear programs with right-hand side uncertainty’ (denoted R_LP_RHSU)
and will provide an overview of some recent complexity results and
applications. Contrasting with the robust linear programming models
studied by Bertsimas & Sim, and by Ben-Tal and Nemirovski (which lead
to polynomially solvable robust equivalents), it can be shown that
R_LP_RHSU with polyhedral uncertainty is strongly NP-hard, even in the
simplest case of uncertainty sets of Bertsimas-Sim type. A number of
polynomially solvable special cases will be mentioned. Also, the
class will be shown to be related to many applications of interest,
including robust versions of network flows, network optimization,
inventory management and optimal power production planning.

12h00-14h00 REPAS
14h00-15h00 Distributionally robust solution to the unreliable multisourcing Newsvendor problem with probabilistic constraints

Jean-Philippe Vial
(University of Geneva and ORDECSYS)

Résumé long

In the unreliable multi-sourcing Newsvendor problem the decision maker wants to meet
an uncertain demand for a single product by ordering from heterogeneous unreliable suppliers. Each supplier is characterized by a cost and a random yield factor. Because of the
uncertainty in the demand and the yield factors, the profit is itself uncertain. The problem
is to select how much to order from each supplier, so as to maximize the expected profit,
possibly under some additional constraints such as a target service level or a limiting budget
on the procurement cost. We consider a version of this problem in which the probability
distributions of the demand and the yield factors are imperfectly known and described by
their means and covariance matrix only. We formulate the problem as a maximin expected
profit model, where the objective function is the worst-case expected profit over the set of
probability distributions having the given mean and covariance. The optimal orders are so-
lutions of a tractable conic quadratic programming approach. Via the optimality conditions,
we give managerial insight concerning the relative importance of supplier purchase cost and
reliability. The model is extended in order to include constraints on the service level and the
procurement budget.

15h00-15h30 Robust models for LP with uncertain right hand side - applications to capacity assignment in telecommunications

Adam Aourou
(Orange Labs)

We propose new robust models for handling right hand side
uncertainty in linear problems. Upper approximations are constructed
using linear decision and zero-order rules on the adjustable variables and
an heuristic is proposed to compute lower bounds. Tractable reformulations
are given on two uncertainty sets arising in practice. To assess
the methodology we consider its application on the capacity assignment
problem.

15h30-15h45 PAUSE
15h45-16h45 Robust sketching and sparse optimization

Laurent EL Ghaoui
(Berkeley University)

In the recent years there has been a lot of interest in approximating a
data matrix by a "sketch", that is, a simpler matrix that preserves some
property of interest, and on which computations can be performed faster
than the original. We consider the idea in the context of solving a linear
or convex quadratic program, and develop the technique of "robust
sketching", which entails replacing the coefficient matrix with a sketch,
but keeping track of the error thus made, via robust optimization. We
examine applications of the concept in the areas of sparse machine
learning and in the context of very large LPs arising in energy management.

16h45-17h15 Portfolio optimization with pw-robustness

Cécile Murat
(Lamsade, Université Paris-Dauphine)

We consider the problem of portfolio optimization with uncertainty on
asset returns. In the context of a scenario-based approach, we want to
determine a robust portfolio performing an acceptable compromise between
the expected returns and the risk of making losses. Many approaches have
been suggested, all based on the formulation of two criteria : one for
expected return and the other for measuring the risk. Some approaches
propose to determine the set of Pareto-optimal solutions, other
approaches consists in optimizing one criterion and transforming the
second criterion into a constraint. In this latter approach, we propose
a new criterion (inducing a new optimization model), called the
pw-robustness criterion : the parameter w allows to manage the risk while
the parameter p handles the maximization of expected return. This
criterion generalizes the classical risk measure Value-at-Risk and can
be compared to the Conditional Value-at-Risk measure regarding the worst
cases.

17h15-17h45 Programmation linéaire mixte robuste avec variables de recours continues

Pierre-Louis Poirion
(ENSTA, Unité de Mathématiques Appliquées)

Nous nous intéresserons aux problèmes linéaires mixtes bi-niveaux, c’est
à dire aux problèmes dans lesquels le processus de décision est divisé
en deux parties : dans un premier temps, les valeurs optimales des
variables dites "de décisions" seront calculées ; puis, une fois que
l’incertitude sur les données est levée, nous calculerons les valeurs
des variables dites "de recours".

Nous commencerons par résoudre un problème linéaire simplifié dans
lequel l’incertitude porte seulement sur le membre droit des
contraintes, et est modélisée par un polytope bien particulier. Nous
supposerons en outre que le problème vérifie une propriété dite "de
recours complet". Nous verrons alors une méthode permettant, à partir
d’un programme robuste quelconque, de se ramener à un programme robuste
équivalent dont le problème déterministe associé vérifie la propriété de
recours complet. Avant de traiter le cas général, nous nous limiterons
d’abord au cas où les variables de décisions sont entières. Nous
testerons alors notre approche sur un problème de production.
Ensuite, après avoir remarqué que l’approche développée dans les
chapitres précédents ne se généralisait pas naturellement aux polytopes
qui n’ont pas des points extrêmes 0-1, nous montrerons comment, en
utilisant des propriétés de convexité du problème, résoudre le problème
robuste dans le cas général. Nous en déduirons alors des résultats de
complexité sur le problème de deuxième étape, et sur le problème robuste.

17h45 Clôture de la journée