Please use this identifier to cite or link to this item: https://doi.org/10.1287/opre.2013.1212
Title: A probabilistic model for minmax regret in combinatorial optimization
Authors: Natarajan, K.
Shi, D.
Toh, K.-C. 
Keywords: Minmax regret
Mixed-integer programming
Probability
Issue Date: Jan-2014
Citation: Natarajan, K., Shi, D., Toh, K.-C. (2014-01). A probabilistic model for minmax regret in combinatorial optimization. Operations Research 62 (1) : 160-181. ScholarBank@NUS Repository. https://doi.org/10.1287/opre.2013.1212
Abstract: In this paper, we propose a new probabilistic model for minimizing the anticipated regret in combinatorial optimization problems with distributional uncertainty in the objective coefficients. The interval uncertainty representation of data is supplemented with information on the marginal distributions. As a decision criterion, we minimize the worst-case conditional value at risk of regret. The proposed model includes the interval data minmax regret model as a special case. For the class of combinatorial optimization problems with a compact convex hull representation, a polynomial sized mixed-integer linear program is formulated when (a) the range and mean are known, and (b) the range, mean, and mean absolute deviation are known; and a mixed-integer second order cone program is formulated when (c) the range, mean, and standard deviation are known. For the subset selection problem of choosing K elements of maximum total weight out of a set of N elements, the probabilistic regret model is shown to be solvable in polynomial time in the instances (a) and (b) above. This extends the current known polynomial complexity result for minmax regret subset selection with range information only. © 2014 INFORMS.
Source Title: Operations Research
URI: http://scholarbank.nus.edu.sg/handle/10635/102736
ISSN: 0030364X
DOI: 10.1287/opre.2013.1212
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

3
checked on Oct 16, 2018

WEB OF SCIENCETM
Citations

3
checked on Oct 16, 2018

Page view(s)

71
checked on Oct 19, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.