Differentiation of Blackbox Combinatorial Solvers
By P. MarinVlastelica, Anselm Paulus, Vít Musil, Georg Martius, Michal Rolinek. International Conference on Learning Representations, 2019
350 citations recorded by the source corpus.
Achieving fusion of deep learning with combinatorial algorithms promises transformative changes to artificial intelligence. One possible approach is to introduce combinatorial building blocks into neural networks. Such end-to-end architectures have the potential to tackle combinatorial problems on raw input data such as ensuring global consistency in multi-object tracking or route planning on maps in robotics. In this work, we present a method that implements an efficient backward pass through blackbox implementations of combinatorial solvers with linear objective functions. We provide both theoretical and experimental backing. In particular, we incorporate the Gurobi MIP solver, Blossom V algorithm, and Dijkstra's algorithm into architectures that extract suitable features from raw inputs for the traveling salesman problem, the min-cost perfect matching problem and the shortest path problem.
View Paper: https://www.semanticscholar.org/paper/15b0dbc21d0e5875c00bbdda7c3abb4cfc797062
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Chunhua Shen
- Guosheng Lin
- Chi Zhang
- Yoshua Bengio
- Han-Jia Ye
- Dacheng Tao
- Liang-Chieh Chen
- Bernt Schiele
Citations in the corpus
- DeepEMD: Differentiable Earth Mover's Distance for Few-Shot Learning (2020, background): “[106] introduce the combinatorial building blocks into neural networks and the end-to-end trainable network can generate informative”
- Differentiating through the Fréchet Mean (2020, methodology): “To circumvent these issues, recent works compute gradients at the solved value instead of differentiating directly, allowing for full neural network integration (Chen et al., 2018; Pogančić et al., 2020).”
- Combinatorial optimization and reasoning with graph neural networks (2021, background): “Although promising ways to tackle the issue of gradient estimation have already emerged in the literature [136], another critical issue to consider is data e ciency.”