A robust optimization approach to online problems
Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2017.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2017
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/112013 |
| _version_ | 1826214744905744384 |
|---|---|
| author | Korolko, Nikita (Nikita E.) |
| author2 | Dimitris Bertsimas and Patrick Jaillet. |
| author_facet | Dimitris Bertsimas and Patrick Jaillet. Korolko, Nikita (Nikita E.) |
| author_sort | Korolko, Nikita (Nikita E.) |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2017. |
| first_indexed | 2024-09-23T16:10:47Z |
| format | Thesis |
| id | mit-1721.1/112013 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T16:10:47Z |
| publishDate | 2017 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1120132019-04-10T09:07:16Z A robust optimization approach to online problems RO approach to online problems Korolko, Nikita (Nikita E.) Dimitris Bertsimas and Patrick Jaillet. Massachusetts Institute of Technology. Operations Research Center. Massachusetts Institute of Technology. Operations Research Center. Operations Research Center. Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2017. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Cataloged from student-submitted PDF version of thesis. Includes bibliographical references (pages 149-155). In this thesis, we consider online optimization problems that are characterized by incrementally revealed input data and sequential irrevocable decisions that must be made without complete knowledge of the future. We employ a combination of mixed integer optimization (MIO) and robust optimization (RO) methodologies in order to design new efficient online algorithms that outperform state-of-the-art methods for many important practical applications. We empirically demonstrate that RO-based algorithms are computationally tractable for instances of practical size, generate more cost-effective decisions and can simultaneously model a large class of similar online problems due to exceptional modeling power of MIO. In Part I, we consider the well-known K-server problem from the perspective of robust adaptive optimization. We propose a new tractable mixed integer linear formulation of the K-server problem that incorporates both information from the past and uncertainty about the future. By combining ideas from classical online algorithms developed in the computer science literature and robust and adaptive optimization developed in the operations research literature we propose a new method that (a) is computationally tractable, (b) almost always outperforms all other methods in numerical experiments, and (c) is stable with respect to potential errors in the assumptions about the future. In Part II, we consider several extensions of the asset-based weapon-to-target assignment problem whose objective is to protect ships in a fleet from incoming threats. We demonstrate that the new highly nonlinear MIO formulation (a) can be combined with lazy constraints techniques allowing the system designer to find optimal solutions in real time, (b) can be extended to the multi-period setting, and (c) admits a decentralized solution with limited loss of optimality. In Part III, we present a novel covariate-adaptive optimization algorithm for online allocation in clinical trials. The new approach leveraging MIO and RO techniques (a) guarantees a better between-group covariate balance in comparison with state-of- the-art methods, (b) yields statistical power at least as high as, and sometimes significantly higher than, randomization-based algorithms, and (c) is well protected against selection, investigator and accidental bias. by Nikita Korolko. Ph. D. 2017-10-30T15:04:21Z 2017-10-30T15:04:21Z 2017 2017 Thesis http://hdl.handle.net/1721.1/112013 1006888572 eng MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission. http://dspace.mit.edu/handle/1721.1/7582 155 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Operations Research Center. Korolko, Nikita (Nikita E.) A robust optimization approach to online problems |
| title | A robust optimization approach to online problems |
| title_full | A robust optimization approach to online problems |
| title_fullStr | A robust optimization approach to online problems |
| title_full_unstemmed | A robust optimization approach to online problems |
| title_short | A robust optimization approach to online problems |
| title_sort | robust optimization approach to online problems |
| topic | Operations Research Center. |
| url | http://hdl.handle.net/1721.1/112013 |
| work_keys_str_mv | AT korolkonikitanikitae arobustoptimizationapproachtoonlineproblems AT korolkonikitanikitae roapproachtoonlineproblems AT korolkonikitanikitae robustoptimizationapproachtoonlineproblems |