Deep Learning in Discrete Optimization

AMS 467/667, Spring 2019

Class meets in Shaffer 3, Tuesday and Thursday, 9:00--10:15.
Office Hours: Whitehead 201-A, Tuesday 11AM - 2PM.
TA: Lucas Rosen, office hours Whitehead 212, Wednesday 4:30--5:30.
Textbook: Deep Learning, Goodfellow, Bengio, and Courville.

Note: Final projects are due on Thursday, May 2, 11:59 PM. Please submit your report (approximately 10 pages) as a pdf file. Send your source code as an email attachment or provide a link to the code in a location such at GitHub.

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 first part of the course will cover background material, introducing students to deep learning (focusing on practical aspects) and covering major topics in computational discrete optimization: heuristic methods, dynamic programming, linear programming, 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, aiming 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).

HW1: Hello Deep Learning World

Outline of Lectures

Introduction (Week 1a)
Deep Learning, Goodfellow, Bengio, Courville, Chapters 1-5.
Combinatorial Optimization, Cook, Cunningham, Pulleyblank, Schrijver. See the course Blackboard page.

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.

Project Presentations (Week 12)

Tuesday, April 30

1. Fate Amenable to Change
Making rational protein design "Intelligent"

2. Heavy Messing
Strong Branching

3. Break Even
Improved branch-and-bound algorithms with neural networks

4. Subtle Shift in Emphasis
A Deep Learning-Based Approximation of Pseudo-cost Branching for TSP (and ATSP)

To be announced.

6. Rapid Random Response Unit
Deep-learning assisted unit commitment

7. Profit Margin
Imitating strong branching with recurrent neural network

8. Displacement Activity
Deep Reinforcement Learning for Solving the Shortest Common Superstring Problem

9. Trade Surplus
Evaluate Roubustness of Neural Networks with MIP on Time Series Data

10. No Fixed Abode
Solving facility location problem using graph convolution networks

11. Passing By and Thought I'd Drop In
The Experienced Tree Trimmer: Deap learning for parametric mixed-integer optimization

Thursday, May 2

12. Quietly Confident
Reinforcement learning for traveling salesman and bin-packing problems

13. Lacking that Small Match Tempermant
Improvement of a Transformer-based TSP Solver

14. Learned Response
Final Exam Scheduling with Q-Learning and Deep Q-Network

15. Value Judgement
A Deep Learning Based Exploration of the Minimum Coloring Problem with the Strong Branching Algorithm

16. Control Surface
Using pointer networks to solve the traveling salesman problem

17. Well, I was in the Neighborhood
Guiding Chained Local Search with Deep Learning

18. Flexible Demeanour
Neural combinatorial optimization: improvmement in architectural design and reinforcement learning

19. Contents May Differ
Deep learning assisted branch and bound search for the TSP

20. Armchair Traveler
A Neural Network Solver of Local Search in Genetic Algorithm to solve Travelling Salesman Problem

21. Serious Callers Only
AlphaTSP: Learning a TSP heuristic using the AlphaGoZero methodology

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.

General Reference Texts

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.