Optimization Online


Robust Optimization of Sums of Piecewise Linear Functions with Application to Inventory Problems

Amir Ardestani-Jaafari (amir.ardestani-jaafari***at***hec.ca)
Erick Delage (erick.delage***at***hec.ca)

Abstract: Robust optimization is a methodology that has gained 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 cost function that needs to be robustified is not concave (or linear) with respect to the perturbing parameters. In this paper, we study robust optimization of sums of piecewise linear functions over polyhedral uncertainty set. Given that these problems are known to be intractable, we propose a new scheme for constructing conservative approximations based on the relaxation of an embedded mixed-integer linear program and relate this scheme to methods that are based on exploiting affine decision rules. Our new scheme gives rise to two tractable models that respectively take the shape of a linear program and a semi-definite program, with the latter having the potential to provide solutions of better quality than the former at the price of heavier computations. We present conditions under which our approximation models are exact. In particular, we are able to propose the first exact reformulations for a robust (and distributionally robust) multi-item newsvendor problem with budgeted uncertainty set and a reformulation for robust multi-period inventory problems that is exact whether the uncertainty region reduces to a L1-norm ball or to a box. An extensive set of empirical results will illustrate the quality of the approximate solutions that are obtained using these two models on randomly generated instances of the latter problem.

Keywords: Robust optimization, pecewise linear, linear programming relaxation, semi-definite program, tractable approximations, newsvendor problem, inventory problem

Category 1: Robust Optimization

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Applications -- OR and Management Sciences (Production and Logistics )


Download: [PDF]

Entry Submitted: 06/18/2013
Entry Accepted: 06/18/2013
Entry Last Modified: 03/06/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society