**Dr. Bogdan Savchynskyy, Prof. Dr. Carsten Rother, WiSe 2021/22**

Credits: 2 / 4 / 6 CP depending on course of study

### Summary

Machine learning techniques are tightly coupled with optimization methods. Many techniques become practical only if there exists a supporting optimization tool.

In the seminar we will discuss a number of recent articles on combinatorial optimization with applications in computer vision and machine learning.

The topic of this semester is again

** Neural Networks meet Combinatorial Optimization**

In particular, we will consider methods for

- training parameters of combinatorial optimization algorithms with the machine learning techniques,
- combinatorial optimization based loss-functions for deep learning

### General Information

TBA### Seminar Repository:

TBA### Papers to Choose from:

See overwiew slides for the papers here. See also the presentation video.

For a quick overview of the general problem these slides could be also helpful. A large collection of slides for the leading **black-box differentiation method** can be found here.

[1] M. Vlastelica, A. Paulus, V. Musil, G. Martius, M. Rolínek, Differentiation of Blackbox Combinatorial Solvers, ICLR 2020 (see also slides here).

[3] M. Rolínek, P. Swoboda, D. Zietlow, V. Musil, A. Paulus, G. Martius, Deep Graph Matching via Blackbox Differentiation, ECCV 2020

[4] A. Paulus, M. Rolínek, V. Musil, B. Amos, G. Martius, Fit the right NP-Hard Problem: End-to-end Learning of Integer Programming Constraints, NeurIPS 2020, LMCA

[6] A. Ferber, B. Wilder, B. Dilkina, M. Tambe, MIPaaL: Mixed Integer Program as a Layer, AAAI 2020

[7] Q. Berthet, M. Blondel, O. Teboul, M. Cuturi, J. Vert, F. Bach, Learning with Differentiable Perturbed Optimizers, NeurIPS 2020

[8] X. Gao, H. Zhang, A. Panahi, T. Arodz, Differentiable Combinatorial Losses through Generalized Gradients of Linear Programs, ArXiv 2020

[10] J. Mandi, E. Demirovic, P. Stuckey, T. Guns, Smart Predict-and-Optimize for Hard Combinatorial Optimization Problems, AAAI 2020

[12] T. Gal, Rim Multiparametric Linear Programming, J. Management Science, 1975

[13] R. Freund, Postoptimal Analysis of a Linear Program Under Simultaneous Changes in Matrix Coefficients, 1984

[14] D. De Wolf,, Generalized Derivatives of the Optimal Value of a Linear Program with Respect to Matrix Coefficients, European J. of Operational Research, 2000

[16] A. Agrawal, B. Amos, S. Barratt, Differentiable Convex Optimization Layers, NeurIPS 2019

[17] M. Blondel, O. Teboul, Q. Berthet, J. Djolonga, Fast Differentiable Sorting and Ranking, ICML 2020

[18] R. Kleiman, D. Page AUC_\mu: A Performance Metric for Multi-Class Machine Learning Models, NeurIPS, 2019

[19] K. Ataman, W. Street, Y. Zhang, Learning to Rank by Maximizing AUC with Linear Programming, IJCNNP, 2006

[20] I. Tsochantaridis, T. Joachims, T. Hofmann, Y. Altun, Large Margin Methods for Structured and Interdependent Output Variables, JMLR, 2005

[21] A. Sadat, M. Ren, A. Pokrovsky, Y. Lin, E. Yumer, R. Urtasun, Jointly Learnable Behavior and Trajectory Planning for Self-Driving Vehicles, IROS 2019

[24] X. Chen, Y. Zhang, C. Reisinger, L. Song, Understanding Deep Architecture with Reasoning Layer, NeurIPS 2020

[25] P. Wang, P. Donti, B. Wilder, Z. Kolter, SATNet: Bridging Deep Learning and Logical Reasoning Using a Differentiable Satisfiability Solver, ICML, 2019

[27] P. Swoboda, C. Rother, H.A. Alhaija, D. Kainmuller, B. Savchynskyy, A Study of Langrangean Decompositions and Dual Ascent Solvers for Graph Matching, CVPR, 2016

[28] A. Hornakova, R. Henschel, B. Rosenhahn, P. Swoboda, Lifted Disjoint Paths with Application in Multiple Object Tracking, ICML 2020

[29] J. Thapper, S. Živný, The Complexity of finite-valued CSPs, J ACM, 2016

[31] Knöbelreiter, P., Reinbacher, C., Shekhovtsov, A., and Pock, T. End-to-end training of hybrid CNN-CRF models for stereo. CVPR 2017