A Caltech Library Service

Learning to Optimize: from Theory to Practice


Song, Jialin (2021) Learning to Optimize: from Theory to Practice. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/7qaw-kd75.


Optimization is at the heart of everyday applications, from finding the fastest route for navigation to designing efficient drugs for diseases. The study of optimization algorithms has focused on developing general approaches that do not adapt to specific problem instances. While they enjoy wide applicability, they forgo the potentially useful information embedded in the structure of an instance. Furthermore, as new optimization problems appear, the algorithm development process relies heavily on domain expertise to identify special properties and design methods to exploit them. Such design philosophy is labor-intensive and difficult to deploy efficiently to a broad range of domain-specific optimization problems, which are becoming ubiquitous in the pursuit of ever more personalized applications.

In this dissertation, we consider different hybrid versions of classical optimization algorithms with data-driven techniques. We aim to equip classical algorithms with the ability to adapt their behaviors on the fly based on specific problem instances. A common theme in our approaches is to train the data-driven components on a pre-collected batch of representative problem instances to optimize some performance metrics, e.g., wall-clock time. Varying the integration details, we present several approaches to learning data-driven optimization modules for combinatorial optimization problems and study the corresponding fundamental research questions on policy learning. We provide multiple practical experimental results to showcase the practicality of our methods which lead to state-of-the-art performance on some classes of problems.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:machine learning, discrete optimization
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computing and Mathematical Sciences
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Yue, Yisong
Thesis Committee:
  • Wierman, Adam C. (chair)
  • Murray, Richard M.
  • Yue, Yisong
  • Dilkina, Bistra
Defense Date:26 May 2021
Funding AgencyGrant Number
DHS Center of Excellence "Critical Infrastructure Resilience Institute"UNSPECIFIED
Rosen Bioengineering CenterUNSPECIFIED
Northrop Grumman CorporationUNSPECIFIED
UChicago CDAC via a JTFI AI + Science GrantUNSPECIFIED
Record Number:CaltechTHESIS:06022021-223508132
Persistent URL:
Related URLs:
URLURL TypeDescription adapted for Ch. 3 adapted for Ch. 4 adapted for Ch. 5 adapted for Ch. 6
Song, Jialin0000-0001-5633-9909
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:14234
Deposited By: Jialin Song
Deposited On:07 Jun 2021 15:41
Last Modified:17 Jun 2021 20:54

Thesis Files

[img] PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page