Robust Counterparts of Inequalities Containing Sums of Maxima of Linear Functions

B.L. Gorissen, D. den Hertog

Research output: Working paperDiscussion paperOther research output

274 Downloads (Pure)

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.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Volume2011-115
Publication statusPublished - 2011

Publication series

NameCentER Discussion Paper
Volume2011-115

Fingerprint

Linear Function
Reformulation
Uncertainty
Inventory Management
Robust Optimization
Absolute value
Linear Inequalities
Recommendations
Regression
Optimization Problem
Numerical Examples

Keywords

  • robust optimization
  • sum of maxima of linear functions
  • biaffine uncertainty
  • robust conic quadratic constraints

Cite this

Gorissen, B. L., & den Hertog, D. (2011). Robust Counterparts of Inequalities Containing Sums of Maxima of Linear Functions. (CentER Discussion Paper; Vol. 2011-115). Tilburg: Operations research.
Gorissen, B.L. ; den Hertog, D. / Robust Counterparts of Inequalities Containing Sums of Maxima of Linear Functions. Tilburg : Operations research, 2011. (CentER Discussion Paper).
@techreport{8c6aa0e2c4c64693ab9af330d76ed76a,
title = "Robust Counterparts of Inequalities Containing Sums of Maxima of Linear Functions",
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",
author = "B.L. Gorissen and {den Hertog}, D.",
year = "2011",
language = "English",
volume = "2011-115",
series = "CentER Discussion Paper",
publisher = "Operations research",
type = "WorkingPaper",
institution = "Operations research",

}

Gorissen, BL & den Hertog, D 2011 'Robust Counterparts of Inequalities Containing Sums of Maxima of Linear Functions' CentER Discussion Paper, vol. 2011-115, Operations research, Tilburg.

Robust Counterparts of Inequalities Containing Sums of Maxima of Linear Functions. / Gorissen, B.L.; den Hertog, D.

Tilburg : Operations research, 2011. (CentER Discussion Paper; Vol. 2011-115).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - Robust Counterparts of Inequalities Containing Sums of Maxima of Linear Functions

AU - Gorissen, B.L.

AU - den Hertog, D.

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

KW - robust optimization

KW - sum of maxima of linear functions

KW - biaffine uncertainty

KW - robust conic quadratic constraints

M3 - Discussion paper

VL - 2011-115

T3 - CentER Discussion Paper

BT - Robust Counterparts of Inequalities Containing Sums of Maxima of Linear Functions

PB - Operations research

CY - Tilburg

ER -

Gorissen BL, den Hertog D. Robust Counterparts of Inequalities Containing Sums of Maxima of Linear Functions. Tilburg: Operations research. 2011. (CentER Discussion Paper).