A Probabilistic Model for Minmax Regret in Combinatorial Optimization

Karthik Natarajan (), Dongjian Shi () and Kim-Chuan Toh ()
Additional contact information
Karthik Natarajan: Engineering Systems and Design, Singapore University of Technology and Design, Singapore 138682, Republic of Singapore
Dongjian Shi: Department of Mathematics, National University of Singapore, Singapore 119076, Republic of Singapore
Kim-Chuan Toh: Department of Mathematics, National University of Singapore, Singapore 119076, Republic of Singapore

Operations Research, 2014, vol. 62, issue 1, 160-181

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.

Keywords: minmax regret; probability; mixed-integer programming (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2013.1212 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:62:y:2014:i:1:p:160-181

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().