Strong Formulations of Robust Mixed 0-1 Programming

Alper Atamturk (atamturkieor.berkeley.edu)

Abstract: We describe strong mixed-integer programming formulations for robust mixed 0-1 programming with uncertainty in the objective coefficients. In particular, we focus on an objective uncertainty set described as a polytope with a budget constraint. We show that for a robust 0-1 problem, there is a tight linear programming formulation with size polynomial in the size of a tight linear programming formulation for the nominal 0-1 problem. Finally, we give extensions to robust mixed 0-1 programming and present computational experiments with the strong formulations.

Keywords: Robust optimization, integer programming, disjunctive programming

Category 1: Integer Programming (0-1 Programming )

Category 2: Robust Optimization

Citation: Mathematical Programming 108, 235-250, 2006 http://www.ieor.berkeley.edu/~atamturk/pubs/

Download:

Entry Submitted: 01/30/2004
Entry Accepted: 01/30/2004
Entry Last Modified: 04/15/2008

Modify/Update this entry