Deep Learning in Discrete Optimization AMS 467/667, Spring 2019 Class meets in Shaffer 3, Tuesday and Thursday, 9:0010:15. Office Hours: Whitehead 201A, Tuesday 11AM  2PM. TA: Lucas Rosen, office hours Whitehead 212, Wednesday 4:305: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 researchlevel topics in the application of deeplearning 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 branchandbound. We will then make an indepth study of recent papers where deep learning has been proposed as a solutiontechnique in discrete optimization, aiming towards discussions of open research questions. Prerequisites 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 15. Combinatorial Optimization, Cook, Cunningham, Pulleyblank, Schrijver. See the course Blackboard page. LinearProgramming 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. CuttingPlane Method (Week 2) In Pursuit of the Traveling Salesman, Chapter 6. Gentle introduction to the cuttingplane method for the TSP. Traveling salesman problem: exact solution with the cutting plane method (YouTube video.) A tutorial for the TSP cuttingplane 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 branchandbound for the TSP and integer programming. Integer Programming: The Branch and Bound Method. Detailed example of branchandbound 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 mixedinteger 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. 296309. Maximum resilience of artificial neural networks, C.H. Cheng, G. N\"uhrenberg, H. Ruess, 2017. Appeared in ATVA 2017. You can see a 2minute 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 feedforward ReLU neural networks, A. Lomuscio, L. Maganti, 2017. Heuristic Algorithms and QLearning (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 Qlearning. 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. BranchandBound (Week 8) On learning and branching: a survey, A. Lodi, G. Zarpellon. Appear in the journal Top 25(10: 207236 (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 branchandbound algorithms, H. He, H. Daume, J. Eisner. Appeared in NIPS 2014. SequencetoSequence 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 branchandbound algorithms with neural networks 4. Subtle Shift in Emphasis A Deep LearningBased Approximation of Pseudocost Branching for TSP (and ATSP) 5. DGLZ To be announced. 6. Rapid Random Response Unit Deeplearning 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 mixedinteger optimization Thursday, May 2 12. Quietly Confident Reinforcement learning for traveling salesman and binpacking problems 13. Lacking that Small Match Tempermant Improvement of a Transformerbased TSP Solver 14. Learned Response Final Exam Scheduling with QLearning and Deep QNetwork 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. 
