3 Presentations

• 
  02:00 PM - 02:30 PM

  Pareto Efficiency in Robust Optimization

  • Nikos Trichakis, presenter, HBS
  • Dan Iancu, Stanford GSB

  This paper formalizes and adapts the well-known concept of Pareto efficiency in the context of the popular robust optimization (RO) methodology for linear optimization problems. We argue that the classical RO paradigm need not produce solutions that possess the associated property of Pareto optimality, and illustrate via examples how this could lead to inefficiencies and sub-optimal performance in practice. We provide a basic theoretical characterization of Pareto robustly optimal (PRO) solutions, and extend the RO framework by proposing practical methods that verify Pareto optimality, and generate solutions that are PRO. Critically important, our methodology involves solving optimization problems that are of the same complexity as the underlying robust problems, hence the potential improvements from our framework come at essentially limited extra computational cost. We perform numerical experiments drawn from three different application areas (portfolio optimization, inventory management, and project management), which demonstrate that PRO solutions have a significant potential upside compared with solutions obtained via classical RO methods,
  at no extra cost or downside.

• 
  02:30 PM - 03:00 PM

  Static vs Adjustable Solutions in Dynamic Optimization

  • Dimitris Bertsimas, Massachusetts Institute of Technology
  • Vineet Goyal, presenter, Columbia University
  • Brian Yin Lu, Columbia University

  We study the performance of static solutions for two-stage adjustable robust linear optimization problems with uncertain constraint and objective coefficients and give a tight characterization of the adaptivity gap. Computing an optimal adjustable robust optimization problem is often intractable, but a static solution can be computed efficiently in most cases. We show that for a fairly general class of uncertainty sets, a static solution is optimal for the two-stage adjustable robust linear optimization problem. Furthermore, when a static solution is not optimal, we give a tight approximation bound on the performance of the static solution that is related to a measure of non-convexity of a transformation of the uncertainty set. We also show that our bound is at least as good (and in many case significantly better) as the bound given by the symmetry of the uncertainty set.

• 
  03:00 PM - 03:30 PM

  Robust Optimization of a Class of Bi-Convex Functions

  • Erick Delage, presenter, GERAD, HEC Montréal
  • Amir Ardestani-Jaafari, University of British Columbia

  Robust optimization is a methodology that has gain a lot of attention in the recent years. This is mainly due to the simplicity of the modeling process and ease of resolution even for large scale models. Unfortunately, the second property is usually lost when the function that needs to be "robustified" is not concave (or linear) with respect to the perturbed parameters. In this work, we propose a new scheme for constructing safe tractable approximations for the robust optimization of a class of bi-convex functions; specifically, those that decompose as the sum of maximum of bi-affine functions (with respect to the decisions and the perturbation). Such functions arise very naturally in a wide range of application, including news-vendor, inventory, and classification problems and multi-attribute utility theory. We will present conditions under which our approximation scheme is exact, and otherwise show that it can always be used to improve on the approximations obtained using affinely adjustable decision rules. Some empirical results will illustrate the additional gains that can be achieved.