Discrete Optimization algorithms underlie intelligent decision-making in a wide variety of domains. From airline fleet scheduling to kidney exchanges and data center resource management, decisions are often modeled with binary on/off variables that are subject to operational and financial constraints. In fact, Nemhauser [100] estimated that at least half of the winners of the INFORMS Franz Edelman Prize between 2000–2013 used discrete optimization in one form or the other, translating into billions of dollars in savings or profits. This thesis introduces “Learning-Driven Algorithm Design", a novel paradigm for boosting the performance of discrete optimization algorithms by leveraging two types of data:​ the set of problem instances arising from the application of interest;​ and information generated while solving each instance. We develop Machine Learning (ML) approaches that have advanced the state-of-the-art in both exact integer programming solvers as well as heuristics.

First, we show how Mixed Integer Programming (MIP) solvers can benefit from tailored, efficient machine learning models, resulting in data-driven MIP branch-and-bound algorithms that are the first of their kind. This paradigm is developed for two fundamental algorithmic tasks in branch-and-bound:​ branching and heuristic selection. Our methods augment the solver with the ability to direct the search based on the characteristics of a particular problem instance and the state of the search, resulting in substantial speedups on a variety of problem classes, as well as common benchmarks.

Second, in the realm of heuristic algorithms, we design a deep reinforcement learning approach to the automated design of greedy algorithms for graph optimization problems with simple constraints. For more complex problems with general constraints, we design a novel recurrent neural network model that takes a set of integer programming instances and learns to turn fractional solutions into integer (feasible) solutions. In both settings, we show that highly effective algorithms can be learned from a set of training instances, generalizing to unseen instances for various families of coverage, routing, assignment and satisfiability problems.

Third and last, we illustrate the potential for discrete optimization in machine learning. In particular, we study an adversarial machine learning problem in the context of binarized neural networks, a popular class of lightweight models with inherently discrete structure. We design an efficient combinatorial heuristic for perturbing inputs to a trained binarized neural network, such that the network predicts the wrong output. Our method generally outperforms the widely-used gradient-based heuristics on image classification datasets.