Invited Session Thu.3.MA 004

Thursday, 15:15 - 16:45 h, Room: MA 004

Cluster 20: Robust optimization [...]

Regret with robustness: Models, algorithms and applications


Chair: Karthik Natarajan



Thursday, 15:15 - 15:40 h, Room: MA 004, Talk 1

Dongjian Shi
A probabilistic model for minmax regret combinatorial optimization

Coauthors: Karthik Natarajan, Kim Chuan Toh


We propose a probabilistic model for minimizing 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 adopt a worst-case conditional value-at-risk of regret measure. The proposed model includes 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, the probabilistic regret model is shown to be solvable in polynomial time for instances (a) and (b).



Thursday, 16:15 - 16:40 h, Room: MA 004, Talk 3

Joline Uichanco
Regret optimization for stochastic inventory models with spread information

Coauthors: Retsef Levi, Georgia Perakis


We study a minimax regret approach to the newsvendor problem. Using a distribution statistic, called absolute mean spread (AMS), we introduce new families of demand distributions under the minimax regret framework. We propose order policies that only require a distribution's mean and information on the AMS. Our policies have several attractive properties. First, they take the form of simple closed-form expressions. Second, we can quantify an upper bound on the resulting regret. Third, under an environment of high profit margins, they are provably near-optimal under mild technical assumptions on the failure rate of the demand distribution. And finally, the information that they require is easy to estimate with data. We show in extensive numerical simulations that when profit margins are high, even if the information in our policy is estimated from (sometimes few) samples, they often manage to capture at least 99,% of the optimal expected profit.


  In particular, Texas Loans Online can cater to the needs of its residents. If you have already decided to take Levitra For Sale, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.