Back to search

University of British Columbia

ML-empowered combinatorial search

Abstract

dc:description

Combinatorial search problems underlie a wide range of computational tasks, from resource allocation in 5G networks and spectrum auctions to verification of hardware and software systems. Despite the best-known techniques having worst-case exponential complexity, many real-world instances exhibit rich structural patterns that specialized solvers can exploit. No single solver excels across all problem distributions, and tuning solvers to specific distributions is crucial for best performance. When done by hand, this application-specific algorithm-design process is very tedious and limited. This thesis explores how machine learning (ML) can empower combinatorial search by integrating data-driven methods with symbolic solvers, maintaining correctness guarantees while adapting to specific applications. We begin by exploring evaluation and applications of two classic ML approaches for algorithm design: algorithm selection and configuration. We later relax two limitations of these classic approaches: (1) reliance on hand-crafted features to represent problem instances; and (2) a black-box view of one or more solvers. We relax the first constraint by learning an end-to-end neural representation of problem instances that captures the right invariances for reasoning about Boolean logic. We relax the second constraint by integrating ML into the solver’s internal decisions, proposing a new reinforcement learning approach, Monte Carlo Forest Search (MCFS), to learn improved branching policies in tree search. With these new advances, learning models for each new application typically demands extensive training data. We show it is possible to train foundation models that dramatically reduce the overhead of learning new tasks and distributions. We trained a single model on a large dataset across a broad range of combinatorial tasks that generalized both on held-out tasks and distributions. We found that models fine-tuned from the foundation models were substantially more sample efficient than models trained from scratch. Finally, we consider the predict-then-optimize paradigm, showing that coupling predictive models with the solver objective can prevent large degradations in solution quality. We formalize this in the setting where forecasts are inherently stochastic and multiple correlated forecasts drive downstream decisions.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy - PhD
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Cameron, Christopher
Contributors dc:contributor
  • Leyton-Brown, Kevin, 1975-

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/90814

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Cameron, Christopher. ML-empowered combinatorial search. doctoral thesis, University of British Columbia, 2025. http://hdl.handle.net/2429/90814