Optimization Online


Robust counterparts of inequalities containing sums of maxima of linear functions

Bram L. Gorissen (b.l.gorissen***at***tilburguniversity.edu)
Dick Den Hertog (d.denhertog***at***tilburguniversity.edu)

Abstract: This paper adresses the robust counterparts of optimization problems containing sums of maxima of linear functions and proposes several reformulations. These problems include many practical problems, e.g. problems with sums of absolute values, and arise when taking the robust counterpart of a linear inequality that is affine in the decision variables, affine in a parameter with box uncertainty, and affine in a parameter with general uncertainty. In the literature, often the reformulation that is exact when there is no uncertainty is used. However, in robust optimization this reformulation gives an inferior solution and provides a pessimistic view. We observe that in many papers this conservatism is not mentioned. Some papers have recognized this problem, but existing solutions are either too conservative or their performance for different uncertainty regions is not known, a comparison between them is not available, and they are restricted to specific problems. We provide techniques for general problems and compare them with numerical examples in inventory management, regression and brachytherapy. Based on these examples, we give tractable recommendations for reducing the conservatism.

Keywords: robust optimization; sum of maxima of linear functions; biaffine uncertainty; robust conic quadratic constraints

Category 1: Robust Optimization

Citation: B. L. Gorissen and D. den Hertog. Robust counterparts of inequalities containing sums of maxima of linear functions. European Journal of Operational Research, 227(1), 30-43, 2013.

Download: [PDF]

Entry Submitted: 11/04/2011
Entry Accepted: 11/04/2011
Entry Last Modified: 08/20/2014

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