Optimization Online


Reformulations versus cutting planes for robust optimization: A computational study

Dimitris Bertsimas (bertsim***at***mit.edu)
Iain Dunning (idunning***at***mit.edu)
Miles Lubin (mlubin***at***mit.edu)

Abstract: Robust optimization (RO) is a tractable method to address uncertainty in optimization problems where uncertain parameters are modeled as belonging to uncertainty sets that are commonly polyhedral or ellipsoidal. The two most frequently described methods in the literature for solving RO problems are reformulation to a deterministic optimization problem or an iterative cutting-plane method. There has been limited comparison of the two methods in the literature, and there is no guidance for when one method should be selected over the other. In this paper we perform a comprehensive computational study on a variety of problem instances for both robust linear optimization (RLO) and robust mixed-integer optimization (RMIO) problems using both methods and both polyhedral and ellipsoidal uncertainty sets. We consider multiple variants of the methods and characterize the various implementation decisions that must be made. We measure performance with multiple metrics and use statistical techniques to quantify certainty in the results. We find for polyhedral uncertainty sets that neither method dominates the other, in contrast to previous results in the literature. For ellipsoidal uncertainty sets we find that the reformulation is better for RLO problems, but there is no dominant method for RMIO problems. Given that there is no clearly dominant method, we describe a hybrid method that solves, in parallel, an instance with both the reformulation method and the cutting-plane method. We find that this hybrid approach can reduce runtimes to 50% to 75% of the runtime for any one method and suggest ways that this result can be achieved and further improved on.

Keywords: robust optimization, computational benchmarking

Category 1: Robust Optimization

Citation: unpublished

Download: [PDF]

Entry Submitted: 04/30/2014
Entry Accepted: 04/30/2014
Entry Last Modified: 07/08/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society