Robust combinatorial optimization with variable budgeted uncertainty

Robust combinatorial optimization with variable budgeted uncertainty

0.00 Avg rating0 Votes
Article ID: iaor20131887
Volume: 11
Issue: 1
Start Page Number: 75
End Page Number: 92
Publication Date: Mar 2013
Journal: 4OR
Authors:
Keywords: mixed integer programming
Abstract:

We introduce a new model for robust combinatorial optimization where the uncertain parameters belong to the image of multifunctions of the problem variables. In particular, we study the variable budgeted uncertainty, an extension of the budgeted uncertainty introduced by Bertsimas and Sim. Variable budgeted uncertainty can provide the same probabilistic guarantee as the budgeted uncertainty while being less conservative for vectors with few non‐zero components. The feasibility set of the resulting optimization problem is in general non‐convex so that we propose a mixed‐integer programming reformulation for the problem, based on the dualization technique often used in robust linear programming. We show how to extend these results to non‐binary variables and to more general multifunctions involving uncertainty set defined by conic constraints that are affine in the problem variables. We present a computational comparison of the budgeted uncertainty and the variable budgeted uncertainty on the robust knapsack problem. The experiments show a reduction of the price of robustness by an average factor of 18 %.

Reviews

Required fields are marked *. Your email address will not be published.