| 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)
|
| 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)
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 |
