Reformulation versus cutting-planes for robust optimization
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...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2016
|
| Online Access: | http://hdl.handle.net/1721.1/103105 https://orcid.org/0000-0001-6721-5506 https://orcid.org/0000-0002-1985-1003 https://orcid.org/0000-0001-6781-9633 |
| _version_ | 1826211798832906240 |
|---|---|
| author | Dunning, Iain Robert Lubin, Miles C Bertsimas, Dimitris J |
| author2 | Massachusetts Institute of Technology. Operations Research Center |
| author_facet | Massachusetts Institute of Technology. Operations Research Center Dunning, Iain Robert Lubin, Miles C Bertsimas, Dimitris J |
| author_sort | Dunning, Iain Robert |
| collection | MIT |
| description | 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–75 % of the runtime for any one method and suggest ways that this result can be achieved and further improved on. |
| first_indexed | 2024-09-23T15:11:34Z |
| format | Article |
| id | mit-1721.1/103105 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:11:34Z |
| publishDate | 2016 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1031052023-03-01T02:14:49Z Reformulation versus cutting-planes for robust optimization Dunning, Iain Robert Lubin, Miles C Bertsimas, Dimitris J Massachusetts Institute of Technology. Operations Research Center Sloan School of Management Bertsimas, Dimitris J. Dunning, Iain Robert Lubin, Miles C. 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–75 % of the runtime for any one method and suggest ways that this result can be achieved and further improved on. United States. Office of Naval Research (ONR Grant N00014-12-1-0999) United States. Dept. of Energy (DOE Computational Science Graduate Fellowship, Grant No. DE-FG02-97ER25308) 2016-06-14T15:53:14Z 2016-06-14T15:53:14Z 2015-07 2014-03 2016-05-23T12:11:45Z Article http://purl.org/eprint/type/JournalArticle 1619-697X 1619-6988 http://hdl.handle.net/1721.1/103105 Bertsimas, Dimitris, Iain Dunning, and Miles Lubin. “Reformulation Versus Cutting-Planes for Robust Optimization.” Comput Manag Sci 13, no. 2 (July 21, 2015): 195–217. https://orcid.org/0000-0001-6721-5506 https://orcid.org/0000-0002-1985-1003 https://orcid.org/0000-0001-6781-9633 en http://dx.doi.org/10.1007/s10287-015-0236-z Computational Management Science Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ Springer-Verlag Berlin Heidelberg application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Dunning, Iain Robert Lubin, Miles C Bertsimas, Dimitris J Reformulation versus cutting-planes for robust optimization |
| title | Reformulation versus cutting-planes for robust optimization |
| title_full | Reformulation versus cutting-planes for robust optimization |
| title_fullStr | Reformulation versus cutting-planes for robust optimization |
| title_full_unstemmed | Reformulation versus cutting-planes for robust optimization |
| title_short | Reformulation versus cutting-planes for robust optimization |
| title_sort | reformulation versus cutting planes for robust optimization |
| url | http://hdl.handle.net/1721.1/103105 https://orcid.org/0000-0001-6721-5506 https://orcid.org/0000-0002-1985-1003 https://orcid.org/0000-0001-6781-9633 |
| work_keys_str_mv | AT dunningiainrobert reformulationversuscuttingplanesforrobustoptimization AT lubinmilesc reformulationversuscuttingplanesforrobustoptimization AT bertsimasdimitrisj reformulationversuscuttingplanesforrobustoptimization |