On Robust 0-1 Optimization with Uncertain Cost Coefficients

Mustafa C. Pinar (mustafapbilkent.edu.tr)

Abstract: Based on the recent approach of Bertsimas and Sim \cite{bs1, bs2} to robust optimization in the presence of data uncertainty, we prove a bound on the probability that the robust solution gives an objective function value worse than the robust objective function value, under the assumption that only cost coefficients are subject to uncertainty. A simple extension to quadratic $0-1$ programs is given. A discussion on the cost of ignoring uncertainty is also included.

Keywords: Data uncertainty, Robust optimization, 0-1 optimization.

Category 1: Robust Optimization

Category 2: Integer Programming (0-1 Programming )

Citation: Bilkent University Department of Industrial Engineering Technical Report, December 2002.

Download:

Entry Submitted: 12/30/2002
Entry Accepted: 01/06/2003
Entry Last Modified: 09/25/2003

Modify/Update this entry