The edge of large-scale optimization in transportation and machine learning
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2019
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/1721.1/122388 |
| _version_ | 1826207541974007808 |
|---|---|
| author | Martin, Sébastien |
| author2 | Patrick Jaillet and Dimitris Bertsimas. |
| author_facet | Patrick Jaillet and Dimitris Bertsimas. Martin, Sébastien |
| author_sort | Martin, Sébastien |
| collection | MIT |
| description | This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. |
| first_indexed | 2024-09-23T13:51:10Z |
| format | Thesis |
| id | mit-1721.1/122388 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T13:51:10Z |
| publishDate | 2019 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1223882023-03-01T02:06:56Z The edge of large-scale optimization in transportation and machine learning Martin, Sébastien Patrick Jaillet and Dimitris Bertsimas. Massachusetts Institute of Technology. Operations Research Center. Massachusetts Institute of Technology. Operations Research Center Sloan School of Management Operations Research Center. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2019 Cataloged from student-submitted PDF version of thesis. Includes bibliographical references (pages 273-284). This thesis focuses on impactful applications of large-scale optimization in transportation and machine learning. Using both theory and computational experiments, we introduce novel optimization algorithms to overcome the tractability issues that arise in real world applications. We work towards the implementation of these algorithms, through software contributions, public policy work, and a formal study of machine learning interpretability. Our implementation in Boston Public Schools generates millions of dollars in yearly transportation savings and led to important public policy consequences in the United States. This work is motivated by large-scale transportation problems that present significant optimization challenges. In particular, we study the problem of ride-sharing, the online routing of hundreds of thousands of customers every day in New York City. We also contribute to travel time estimation from origin-destination data, on city routing networks with tens of thousands of roads. We additionally consider the problem of school transportation, the scheduling of hundreds of buses to send tens of thousands of children to school everyday. This transportation problem is related to the choice of school start times, for which we also propose an optimization framework. Building on these applications, we present methodological contributions in large- scale optimization. We introduce state-of-the-art algorithms for scheduling problems with time-window (backbone) and for school bus routing (BiRD). Our work on travel time estimation tractably produces solutions to the inverse shortest path length problem, solving a sequence of second order cone problems. We also present a theoretical and empirical study of the stochastic proximal point algorithm, an alternative to stochastic gradient methods (the de-facto algorithm for large-scale learning). We also aim at the implementation of these algorithms, through software contributions, public policy work (together with stakeholders and journalists), and a collaboration with the city of Boston. Explaining complex algorithms to decision-makers is a difficult task, therefore we introduce an optimization framework to decomposes models into a sequence of simple building blocks. This allows us to introduce formal measure of the "interpretability" of a large class of machine learning models, and to study tradeoffs between this measure and model performance, the price of interpretability. by Sébastien Martin. Ph. D. Ph.D. Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center 2019-10-04T21:31:38Z 2019-10-04T21:31:38Z 2019 2019 Thesis https://hdl.handle.net/1721.1/122388 1120105488 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 284 pages application/pdf n-us---n-us-man-us-ny Massachusetts Institute of Technology |
| spellingShingle | Operations Research Center. Martin, Sébastien The edge of large-scale optimization in transportation and machine learning |
| title | The edge of large-scale optimization in transportation and machine learning |
| title_full | The edge of large-scale optimization in transportation and machine learning |
| title_fullStr | The edge of large-scale optimization in transportation and machine learning |
| title_full_unstemmed | The edge of large-scale optimization in transportation and machine learning |
| title_short | The edge of large-scale optimization in transportation and machine learning |
| title_sort | edge of large scale optimization in transportation and machine learning |
| topic | Operations Research Center. |
| url | https://hdl.handle.net/1721.1/122388 |
| work_keys_str_mv | AT martinsebastien theedgeoflargescaleoptimizationintransportationandmachinelearning AT martinsebastien edgeoflargescaleoptimizationintransportationandmachinelearning |