Deep Learning in Discrete Optimization

AMS 467/667, Spring 2020
Instructor: William Cook
Lectures: Maryland 110, Tuesday and Thursday, 9:00--10:15.
Office Hours: Whitehead 201-A, Tuesday 1PM - 3PM.
TA: Yuanya Ma

Course Description

The goal of the course is to examine research-level topics in the application of deep-learning techniques to the solution of computational problems in discrete optimization. The tools of deep learning, mixed-integer programming, and heuristic search will be studied, analyzed, and applied to a variety of models, including the traveling salemsan problem, vehicle routing, and graph coloring.

The first half of the course will cover background material, introducing students to deep learning (focusing on practical aspects) and heuristic search techniques, and covering major topics in applied mixed-integer programming, including modeling, linear-programming duality, cutting planes, column generation, and branch-and-bound. We will then make an in-depth study of recent papers where deep learning has been proposed as a solution-technique in discrete optimization and where mixed-integer programming has been adopted to study the performance of deep learning models. The presentations will be aimed towards discussions of open research questions.


General mathematical maturity is expected: students should feel comfortable reading on their own Part 1 (Applied Math and Machine Learning Basics) in the text Deep Learning.

Although no specific background in the topics is required, students will get the most out of the course if they have previous knowledge of one of the three components: (1) discrete optimization, (2) machine learning, (3) computation (PyTorch or a good background in computer programming).

Course Work

There will be two homework assignments. The first will be for you to build, train, and test a neural network for a simple combinatorial problem, using the PyTorch framework. The second is to create and solve a mixed-integer-programming model of a particular neural network, using the CPLEX package. The two assignments together will count for 25% of the course grade.

The major part of the course work is a final project, applying deep learning to a discrete optimization problem, or using discrete optimization to annalyze a deep learning model. In this project students are encouraged to work in teams of up to four members. Each team will submit a proposal (1 to 2 pages), a final report (5 to 10 pages), computer code, and test data. Teams will also give a short presentation in the final week of lectures. The project counts for 75% of the course grade.


Deep Learning, Goodfellow, Bengio, and Courville (pdf freely available, hardcopy $55.00 at Amazon).
In Pursuit of the Traveling Salesman (hardcopy $12.95 at Amazon).
Model Building in Mathematical Programming, H. Paul Williams (online version at no cost while on Johns Hopkins network, hardcopy $50.07 at Amazon).

Outline of Lectures

Introduction (Week 1a)
Deep Learning, Goodfellow, Bengio, Courville, Chapters 1-5.
In Pursuit of the Traveling Salesman, Chapter 1.

Topics from 2019 Version of Course

Linear-Programming Duality (Week 1b)
In Pursuit of the Traveling Salesman, Chapter 5. Very gentle introduction to linear programming.
Liner Programming, Vasek Chvatal. Fantastic introduction to LP, duality, and the simplex algorithm. Sadly, the book is out of print, but used copies are available for $13.
ORF 307: Optimization, Robert Vanderbei. Course notes based on his book Linear Programming: Foundations and Extensions.

Cutting-Plane Method (Week 2)
In Pursuit of the Traveling Salesman, Chapter 6. Gentle introduction to the cutting-plane method for the TSP.
Traveling salesman problem: exact solution with the cutting plane method (YouTube video.) A tutorial for the TSP cutting-plane method, created for the Concorde TSP app. Hope you don't mind the Siri voice.
Practical Problem Solving with Cutting Plane Algorithms in Combinatorial Optimization, M. Juenger, G. Reinelt, S. Thienel.

Branch and Bound (Week 3)
Applied Mathematical Programming, Chapter 9, Integer Programming, S. Bradley, A. Hax, T. Magnanti. Branch and bound is covered in Section 9.5.
In Pursuit of the Traveling Salesman, Chapter 7. Gentle introduction to branch-and-bound for the TSP and integer programming.
Integer Programming: The Branch and Bound Method. Detailed example of branch-and-bound applied to a small integer programming problem.

Simplex Method (Week 4a)
Robert Bixby: Solving Linear Programs: The Dual Simplex Algorithm (1/3): Some Basic Theory (YouTube video). Bixby's lecture on the simplex algorithm.
Solving Linear and Integer Programs, Robert Bixby and Ed Rothberg. The description of the simplex method we covered in class is given on slide 16.
Liner Programming, Vasek Chvatal, Chapters 2, 3, and 7.

PyTorch Tutorial (Week 4b)
Tutorial 1, notebook by Lucas Rosen (course TA).

Rectified linear units (Week 5a)
Understanding deep neural networks with rectified linear units, R. Arora, A. Basu, P. Mianjy, A. Mukherjee. 2018. Appeared in ICLR 2018.
Discrete Geometry meets Machine Learning, Amitabh Basu. Talk given at the 22nd Aussois Combinatorial Optimization Workshop, January 11, 2018.
Bounding and counting linear regions of deep neural networks, T. Serra, C. Tjandraatmadja, S. Ramalingam. 2018. Appeared in ICML 2018. A talk on this topic (given by one of the authors of the paper) can be viewed here.

Advesarial examples for neural nets via mixed-integer programming (Week 5a and 6a)
Evaluating robustness of neural networks with mixed integer programming, V. Tjeng, K. Xiao, R. Tedrake, 2019. Appeared in ICLR 2019. Computer code available here.
Deep neural networks and mixed integer linear optimizatio, M. Fischetti, J. Jo. 2018. Published in the journal Constraints, July 2018, Issue 3, pp. 296-309.
Maximum resilience of artificial neural networks, C.-H. Cheng, G. N\"uhrenberg, H. Ruess, 2017. Appeared in ATVA 2017. You can see a 2-minute demonstration of their software here.
Output range analysis for deep feedforward neural networks, S. Dutta, S. Jha, S. Sanakaranarayanan, A. Tiwari, 2017. Appeared in NFM 2018.
An approach to reachability analysis for feed-forward ReLU neural networks, A. Lomuscio, L. Maganti, 2017.

Heuristic Algorithms and Q-Learning (Week 6b and 7)
Learning combinatorial optimization algorithms over graphs, H. Dai, E. B. Khalil, Y. Zhang, B. Dilkina, L. Song. 2017. Appeared in NIPS 2017. Computer code by Hanjun Dai, implementing the discusssed models, is available on GitHub. Hanjun Dai also has PowerPoint slides available for a talk on this topic.
Machine learning for combinatorial optimization: a methodological Tour de Horizon, Y. Bengio, A. Lodi, A. Prouvost, 2018. Nice survey paper.
Machine Learning for Humans, Part 5: Reinforcement Learning, V. Maini. 2017. Very gentle introduction; good way to get accustomed to the terminology used in Q-learning. Experimental analysis of heuristics for the STSP, D. S. Johnson, L. McGeoch. Appeared in the book The Traveling Salesman Problem and its Variations, edited by Gutin and Punnen, 2002. Survey of classical heuristic methods for the (symmetric) TSP.

Branch-and-Bound (Week 8)
On learning and branching: a survey, A. Lodi, G. Zarpellon. Appear in the journal Top 25(10: 207--236 (2017).
Learning to branch in mixed integer programming, E. B. Khalil, P. Le Bodic, L. Song, G. Nemhauser, B. Dilkina. Appeard in AAAI 2016.
Learning to search in branch-and-bound algorithms, H. He, H. Daume, J. Eisner. Appeared in NIPS 2014.

Sequence-to-Sequence Learning (Week 9)
Neural machine translation by jointly learning to align and translate, D. Bahdanau, K. Cho, Y. Bengio. 2014.
Sequence to sequence learning with neural networks, I. Sutskever, O. Vinyals, Q. V. Le. 2014.
Pointer networks, O. Vinyals, M. Fortunato, N. Jaitly. 2017.

Attention (Week 10)
Attention is all you need, A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. Gomez, L. Kaiser, I. Polosukhin. December 2017.
Attention, learn to solve routing problems!, W. Kool, M. Welling. Appeared in ICLR 2019. (Source code on GitHub.)

Computational Testing (Week 11a)
Constraint Integer Programming, Tobias Achterberg, Ph. D. Thesis, Berlin 2009. Beautiful examples of careful computational testing.
Benchmarking optimization software with performance profiles, E. Dolan, J. More. 2004. Performance profiles at GAMS -- background on performance profiles.
Experimental analysis of algorithms, Catherine McGeoch. Notices of the AMS, March 2001.
A theoretician's guide to the experimental analysis of algorithms, David S. Johnson, 2001.

Explainable Machine Learning (Week 11b)
Boolean decision rules via column generation, S. Dash, O. Gunluk, D. Wei. Winner of the $5000 FICO Explainable Machine Learning Challenge at NeurIPS 2018.

Click here for the 2019 version of the course at Johns Hopkins University.

Topics from 2018 Version of Course

Neural combinatorial optimization with reinforcement learning,I. Bello, H. Pham, Q. V. Le, M. Norouzi, S. Bengio. 2017. Lecture by Samy Bengio (Berlin, June 2017.)
Deep reinforcement learning for solving the vehicle routing problem, M. Nazari, A. Oroojlooy, L. V. Snyder, M. Takac. February 2018.

Click here for the 2018 version of the course at the University of Waterloo.

General References

Deep Learning
Ian Goodfellow, Yoshua Bengio, Aaron Courville
MIT Press, 2016
The main course text for fundamentals of deep learning.

A Practical Guide to Discrete Optimization, Chapter 1, Chapter 7
David Applegate, William Cook, Sanjeeb Dash
Computational studies in discrete optimization.