Optimization Online


A Probabilistic Model for Minmax Regret in Combinatorial Optimization

Karthik Natarajan(natarajan_karthik***at***sutd.edu.sg)
Dongjian Shi(shidongjian***at***nus.edu.sg)
Kim Chuan Toh(mattohkc***at***nus.edu.sg)

Abstract: In this paper, we propose a 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 standard interval data minmax regret as a special case. For the class of combinatorial optimization problems with a compact convex hull representation, a polynomial sized mixed integer linear program (MILP) is formulated when (a) the range and mean are known, and (b) the range, mean and mean absolute deviation are known while a mixed integer second order cone program (MISOCP) 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.


Category 1: Combinatorial Optimization


Download: [PDF]

Entry Submitted: 05/11/2012
Entry Accepted: 05/11/2012
Entry Last Modified: 05/11/2012

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