A Probabilistic Model for Minmax Regret in Combinatorial Optimization

作     者：Natarajan, Karthik Shi, Dongjian Toh, Kim-Chuan 

作者机构：Singapore Univ Technol & Design Singapore 138682 Singapore Natl Univ Singapore Dept Math Singapore 119076 Singapore 

出 版 物：《OPERATIONS RESEARCH》 (运筹学)

年 卷 期：2014年第62卷第1期

页      面：160-181页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：SUTD-MIT International Design Center [IDG31300105] Ministry of Education Academic Research Fund [R-146-000-168-112] 

主　　题：minmax regret probability mixed-integer programming 

摘      要：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.