10ème Séminaire POC

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

Résumé

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.

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.

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.

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.

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.

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.