Deep Learning in Computational Discrete Optimization CO 759, Winter 2018 Class meets in MC 6486, Monday and Wednesday, 11:3012:50. 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 (CO255 and/or CO450/650 and/or CO452/652), (2) machine learning (CS489/695 or the Deep Learning text), (3) computation (TensorFlow or a good background in computer programming). HW1: Hello World Outline of Lectures Computational discrete optimization (Weeks 14) Computation, linearprogramming bounds, the cuttingplane method, column generation, branch decomposition. Rectified linear units (Week 5) Understanding deep neural networks with rectified linear units, R. Arora, A. Basu, P. Mianjy, A. Mukherjee. 2017 Bounding and counting linear regions of deep neural networks, T. Serra, C. Tjandraatmadja, S. Ramalingam. 2018 Maximum resilience of artificial neural networks, C.H. Cheng, G. N\"uhrenberg, H. Ruess, 2017. Deep neural networks as 01 mixed integer linear programs: a feasibility study, M. Fischetti, J. Jo. 2017. QLearning (Week 6) Learning combinatorial optimization algorithms over graphs, H. Dai, E. B. Khalil, Y. Zhang, B. Dilkina, L. Song. 2017. This is the main paper we will discuss in this week's lectures. Implementation of the techniques in 'Learning combinatorial optimization algorithms over graphs', HanjunDai. December 30, 2017. Code for the methods presented in the Dai et al. 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. BranchandBound (Week 7) On learning and branching: a survey, A. Lodi, G. Zarpellon. Learning to branch in mixed integer programming, E. B. Khalil, P. Le Bodic, L. Song, G. Nemhauser, B. Dilkina. SequencetoSequence Learning (Weeks 89) 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. 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. Attention (Week 10a) Attention is all you need, A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. Gomez, L. Kaiser, I. Polosukhin. December 2017. Attention solves your TSP, W. Kool, M. Welling. March 2018. (Source code on GitHub.) Computational Testing (Week 10b) 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. Final Projects 1. Youthful Indiscretion Deep learning to test if a graph is Hamiltonian 2. Funny, It Worked Last Time Deep learning for online knapsack and binpacking problems 3. Displacement Activity Improving localsearch methods using deep neural networks 4. Another Fine Product from the Nonsense Factory A mixed convexcombinatorial approach for training hardthreshold networks 5. So Much for Subtlety Reinforcement learning for MIP branchandbound decisions 6. Well, I was in the Neighborhood Using deep neural networks to generate localcut vertex clusters 7. Limiting Factor Deep learning for branchandbound variable selection in graph optimization Announcements Oberwolfach Seminar: Mathematics of Deep Learning 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. 
