Differentiation of Blackbox Combinatorial Solvers
Authors: Marin Vlastelica Pogančić
Anselm Paulus
Vit Musil
Georg Martius
Michal Rolinek
Venue:  (2020)
Keywords: combinatorial algorithms
deep learning
representation learning
optimization

Abstract: 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.

Published as a conference paper at ICLR 2020
DIFFERENTIATION OF BLACKBOX COMBINATORIAL SOLVERS
Marin Vlastelica ", Anselm Paulus' Vit Musil", Georg Martius' Michal Rolínek
1 Max-Planck- Institute for Intelligent Systems, Tübingen, Germany 2 Università degli Studi di Firenze, Italy
marin. vlastelica, paulus, georg.martius, michal.rolinek) @ruebingen.mpg.de vit.musil@ inifi.it
ABSTRACT
Achieving fusion of deep learning with combinatorial algorithms promises trans- formative changes artificial intelligence. One possible approach introduce combinatorial building blocks into neural networks. Such end-to-end architec- tures have the potential tackle combinatorial problems on raw input data such as ensuring global consistency in multi-object tracking route planning on maps in robotics. In this work, we present a method that implements an efficient back- ward 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 Di- jkstra's '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. The code is available at
http:///gthhb..oommmartttslllllu htw.://aaaatuusaabbabbbbbbboo-ea
INTRODUCTION
The toolbox of popular methods in computer science currently sees split into two major com- ponents. On the one hand, there are classical algorithmic techniques from discrete optimization graph algorithms, SAT-solvers, integer programming solvers often with heavily optimized im- plementations and theoretical guarantees runtime and performance. On the other hand, there is the realm of deep learning allowing data-driven feature extraction as well as the flexible design of end-to-end architectures. The fusion of deep learning with combinatorial optimization is desirable both for foundational reasons extending the reach of deep learning to data with large combinato- rial complexity and in practical applications. These often occur for example in computer vision problems that require solving a combinatorial sub-task on top of features extracted from raw input such establishing global consistency in multi-object tracking from sequence of frames.
The fundamental problem with constructing hybrid architectures is differentiability of the combina- torial components. State-of-the-art approaches pursue the following paradigm: introduce suitable approximations or modifications of the objective function or of a bascline algorithm that eventu- ally yield differentiable computation. The resulting algorithms are often sub-optimal in terms of runtime, performance and optimality guarantees when compared to their unmodified counterparts. While the sources of sub-optimality vary from example to example, there a common theme: any differentiable algorithm in particular outputs continuous values and as such it solves relaxation of the original problem. It is well-known in combinatorial optimization theory that even strong and practical convex relaxations induce lower bounds the approximation ratio for large classes of problems (Raghavendra, 2008; Thapper & Zivný, 2017) which makes them inherently sub-optimal. This inability to incorporate the best implementations of the best algorithms is unsatisfactory.
In this paper, we propose method that, at the cost of one hyperparameter, implements backward pass for a blackbox implementation of a combinatorial algorithm or a solver that optimizes a linear
TThese authors contributed equally.

---

Published as a conference paper at ICLR 2020
learned representation
solver output
Iapul (e.g. imnge)]
arti IS
?
y(w)
Loss
dfx dwer
df
dL
dy
dy
more NN layers
NN layers/ convolutions
Blackbox combinatorial solver
(optional)
Figure 1: Architecture design enabled by Theorem 1. Blackbox combinatorial solver embedded into neural network.
objective function. This effectively turns the algorithm solver into composable building block of neural network architectures, as illustrated in Fig. 1. Suitable problems with linear objective include classical problems such SHORTEST-PATH, PERFECT-MATCIINGG various cut problems as well as entire frameworks such as integer programs (IP), Markov random fields (MRF) and conditional random fields (CRF).
GRAVELING-SALESMA.
(TSP), MIN-COST-
The main technical challenge boils down to providing an informative gradient of piecewise con- stant function. To that end, we are able to heavily leverage the minimization structure of the un- derlying combinatorial problem and efficiently compute a gradient of a continuous interpolation. While the roots of the method lie in loss-augmented inference, the employed mathematical tech- nique for continuous interpolation is novel. The computational cost of the introduced backward pass matches the cost of the forward pass. In particular, it also amounts to one call to the solver.
In experiments, we train architectures that contain unmodified implementations of the fol- lowing efficient combinatorial algorithms: general-purpose mixed-integer programming solver Gurobi (Gurobi Optimization, 2019), state-of-the-art C implementation of MIN-COST-PERFECT MATCHING algorithm Blossom (Kolmogorov, 2009) and Dijkstra's algorithm (Dijkstra, 1959) for SHORTEST- We demonstrate that the resulting architectures train without sophisticated tweaks and are able to solve tasks that are beyond the capabilities of conventional neural networks.
2 RELATED WORK
Multiple lines of work lie at the intersection of combinatorial algorithms and deep learning. We primarily distinguish them by their motivation.
Motivated by applied problems. Even though computer vision has substantial shift from combinatorial methods to deep learning, some problems still have a strong combinatorial aspect and require hybrid approaches. Examples include multi-object tracking (Schulter et al., 2017), semantic segmentation (Chen et al., 2018), 18), multi pertoo pose estimation (Pishchulin et al., 2016; Song et al., 2018), stereo matching (Knöbelreiter et al., 2017) and person re-identification (Ye al., 2017). The combinatorial algorithms in question are typically Markov random fields (MRF) (Chen et al., 2015), conditional random fields (CRF) (Marin al., 2019), graph matching (Ye et al., 2017) or integer programming (Schulter et al., 2017). In recent years, plethora of hybrid end-to-end architectures have been proposed. The techniques used for constructing the backward pass range from employing various relaxations and approximations of the combinatorial problem (Chen et al., 2015; Zheng et al., 2015) over differentiating a fixed number of iterations of an iterative solver (Paschalidou et al., 2018; Tompson et al., 2014; Liu et al., 2015) all the way to relying the structured SVM framework (Tsochantaridis et al., 2005; Chen et al., 2015).
Motivated by "bridging the gap"' Building links between combinatorics and deep learning can also be viewed as foundational problem; for example, (Battaglia et al., 2018) advocate that "com- binatorial generalization must be a top priority for AI". One such line of work focuses on designing architectures with algorithmic structural prior for example by mimicking the layout of Turing machine (Sukhbaatar et al., 2015; Vinyals et al., 2015; Graves et al., 2014; 2016) or by promoting behaviour that resembles message-passing algorithms as it is the case in Graph Neural Networks and
2

---

Published as a conference paper at ICLR 2020
related architectures (Scarselli al., 2009; Li et al., 2016; Battaglia al., 2018). Another approach is to provide neural network building blocks that are specialized to solve some types of combina- torial problems such satisfiability (SAT) instances (Wang et al., 2019). mixed integer programs (Ferber et al., 2019), sparse inference (Niculae et al., 2018), or submodular maximization (Tsschi- atschek et al., 2018). 8). A related mindset of learning inputs an optimization problem gave rise the "predict-and-optiiize
framework and its variants (Elmachtoub & Grigas, 2017; Demirovic et al., 2019; Mandi et all. 2019). Some works have directly addressed the question of learning combinato- rial optimization algorithms such as the or its vehicle routing variants (Nazari et al., 2018). A recent approach also learns combinatorial algorithms via clustering proxy (Wilder et al., 2019).
in (Bello et al., 2017)
There are also efforts to bridge the gap the opposite direction; to use deep learning methods to im- prove state-of-the-art combinatorial solvers, typically by learning (otherwise hand-crafted) heuris- ties. Some works have again targeted the TRAVELING-SALEEMM ALLEEAAN-POOBLE (Kool et al., 2019; Deudon et al., 2018: 8; Bello et al., 2017) well as other NP-Hard problems (Li et al., 2018). Also, more general solvers received some attention; this includes SAT-solvers (Selsam & Bjørner, 2019;
Selsam et al., 2019), integer programming solvers (often with learning branch-and and-bound rules) (Khalil et al., 2016; Balcan et al., 2018; Gasse et al., 2019) and SMT-solvers (satisfiability modulo (Baluiei et al., 2018).
METHOD
Let us first formalize the notion of a combinatorial solver. We expect the solver to receive continuous input w E W S R. (e.g. edge weights of fixed graph) and return discrete output from some finite set Y (e.g. all traveling salesman tours on a fixed graph) that minimizes some cost c(w, y) (e.g. length of the tour). More precisely, the solver maps
+ y(w) such that y(w)= = arg min c(w,
VEY
We will restrict ourselves to objective functions c(w, y) that are linear, namely c(w, y) may be represented
c(w, y) = w -vv) for w E W and EY in which o: - R. is an injective representation of E Y in RN, For brevity, we omit the mapping and instead treat elements of Y discrete points in R..
(2)
Note that such definition of a solver is still very general as there are no assumptions on the set of constraints or on the structure of the output space Y.
Example 1 (Encoding shortest-path problem). IfG = EV, is a given graph with vertices s, E V, the combinatorial solver for the (s, t) D--SORTESS-PPAHH would take edge weights w E WW R as input and produce the shortest path y(w) represented as Φ(y) {0, 1] [R] indicator vector of the selected edges. The cost function is then indeed the inner product c(w.y) .y) = w x ((y).
The task to solve during back- poc-ppropagation the following. We receive the gradient dT./dy of the global loss L with respect to solver output y at a given point ğ y(w). We are expected return dL/dw, the gradient of the loss with respect to solver input w at a point w.
Since Y is finite, there are only finitely many values of y(w). In other words, this function of w is piecewise constant and the gradient is identically zero or does not exist (at points of jumps). This should not come as surprise: if one does a small perturbation to edge weights of graph, one usually does not change the optimal TSP tour and on rare occasions alters it drastically. This has an important consequence:
The fundamental problem with differentiating through combinatorial solvers is not the lack of differentiability;; the gradient exists almost everywhere. However, this gradient is a constant zero and as such is unhelpful for optimization.
Accordingly, we will not rely on standard techniques for gradient estimation (see (Mohamed et al., 2019) for a comprehensive survey).
3

---

Published as a conference paper at ICLR 2020
((((w)
f(U2)
f(((w))
fx(w)
fxw
((n)
W
WA
W
G
(8)
(b)
Figure 2: Continuous interpolation of a piecewise constant function. (a) fA for a small value of A; the set W is still substantial and only two interpolators 91 and 92 are incomplete. Also, all interpolators are 0-interpolators. (b) fx for a high value of X; most interpolators are incomplete and also encounter d-interpolator Os (between y1 and y2) which attains the value f(y ) 6-away from the set Pj. Despite losing some local structure for high X, the gradient of fx is still informative.
First, we simplify the situation by considering the lincarization f of L at the point ÿ. Then for
f(v) = L(0) + dL.
(0) (v ÿ) we have df()(w) dT.
dy
dw dw
and therefore it suffices focus on differentiating the piecewise constant function ff (v(w)).
If the piecewise constant function at hand was arbitrary, we would be forced to use zero-order gradient estimation techniques such computing finite differences. These require prohibitively many function evaluations particularly for nigh-dimensional problems.
However, the function f (y(w)) is result of minimization process and it known that for smooth spaces Y there are techniques for such "differentiation through argmin" (Schmidt & Roth, 2014; Samuel & Tappen, 2009; Foo al., 2008; Domke, 2012; Amos et al., 2017: Amos Kolter, 2017). It turns out to be possible to build with different mathematical tools a viable discrete analogy. In particular, we can efficiently construct a function (w), continuous interpolation of ʃ (y(w)).
whose gradient we return (see Fig. 2). The hyper-parameter À > controls the trade-off between "informativeness the gradient" and "faithfulness to the original function".
Before diving into the formalization, present the final algorithm as listed in Algo. 1. It simple to implement and the backward pass indeed only runs the solver once on modified input. Providing the justification, however, is not straightforward, and it is the subject of the rest of the section.
Algorithm Forward and Backward Pass
function FORWARDPASS(Or
function BACKWARDPASSI dl (ū). A) dy
i == Solver(
i (
load á and ÿ from forward pass W = T + X dl
save v and ý for backward pass return ş
(i)
dy
// Calculate perturbed weights
/ = Solver(w')
return V fx == - [ yx]
// Gradient of continuous interpolation
3.1 CONSTRUCTION AND PROPERTIES SA
Before give the exact definition of the function fx, formulate several requirements on it. This will help us understand why fww is a reasonable replacement for f (y(w)) and, most importantly, why its gradient captures changes in the values of f-
Property A1. For each À > 0, fx is continuous and piecewise affine.
4

---

Published as a conference paper at ICLR 2020
The second property describes the trade-off induced by changing the value of X. For A O, define sets Wa and Wir as the sets where (y((w) and fx(w) coincide and where they differ, i.e.
W = {w E W (aw) =
( [v(w))} and Wa = W W
Property A2. The sets W are monotone and they vanish as - 0+ i.e.
W dif C W for A1 S X2 and Wa - 0 as - 0+.
In other words, Property A2 tells us that À controls the size of the set where fx deviates from f and where fx has meaningful gradient. This behaviour of fx can be seen in Fig. 2.
In the third and final property, we want to capture the interpolation behavior of fx. For that purpose, define 6 6-interpolator of f. We say that g. defined on set G W, is 6-interpolator of between yn and E Y,
is non-constant affine function;
the image g(G) is an interval with endpoints f(y1) and f(y2);
I attains the boundary values (11) and (122 at most δ-far away from where f((ww) does. In particular, there a point wP E for which g(wx) = f(yx) and dist(ww,,)) Pk) S 6, where Ps (w W (ww) ys J. for 1,2.
In the special case of O-interpolator g. the graph of g connects (in a topological sense) two com- ponents of the graph [v((w). the general case, measures displacement of the interpolator (see also Fig. 2 for some examples). This displacement the one hand loosens the connection to
(u(w)) but on the other hand allows for less local interpolation which might be desirable.
Property A3. The function fx consists of finitely many (possibly incomplete) 6-interpolators of f on W where CA for some fixed C. Equivalently, the displacement linearly controlled by X.
Intuitively, the consequence of Property A3 is that fx has reasonable gradients everywhere since consists of elementary affine interpolators.
For defining the function fx, need solution of perturbed optimization problem
yx (w) arg min(c((, Af())) yEY
(3)
Theorem 1. Ler À > O. The function fa defined by
1 (x(w) = [(x((w)) ā [c(w.)(w)) v(w)) - v2(2))
(4)
satisfies Properties AI, A2.
Let us remark that already the continuity of fx is not apparent from its definition as the first term fux (w)) is still piecewise constant function. Proof this result, along with geometrical descrip- tion of fx, can be found in section A.2. Fig. visualizes fx for different values if X.
Now, since fA ensured to be differentiable, we have
dc f(((w) = - Ldw (w. ((w))= dw
1 dc
(w.yx (u(x)((
1 - -x())- )
(5)
The second equality then holds due to (2). We then return VA loss gradient.
Remark 1. The roots of the method we propose lie in loss-augmented inference. In fact, the update rule from (5) (but not the function fx or any of its properties) was already proposed in a different context in (Hazan et al., 2010; Song al., 2016) and was later used in (Lorberbom al., 2018; Mohapatra et al., 2018). The main difference to our work is that only the case of x 0 recom- mended and studied, which in situation computes the correct but uninformative zero gradient. Our analysis implies that larger values of À are not only sound but even preferable. This will be seen in experiments where we use values X RJ 10 20.

---

Published as a conference paper at ICLR 2020
A (w)
fa(w)
(x(w)
W2
W2
wi
W1
W1
Figure 3: Example fx for E R² and À = 3, 10, 20 (left to right). As À changes, the interpolation fx less faithful the piecewise constant f(((w) but provides reasonable gradient on larger set.
3.2 EFFICIENT COMPUTATION OF fx
Computing (3) is the only potentially expensive part of evaluating (5). However, the linear interplay of the cost function and the gradient trivially gives resolution.
Proposition Let i W be fixed. If we set + dy (t), we can compute yı as
( arg min c(w', ,))
yEY
In other words, yx is the output of calling the solver input w'.
4 EXPERIMENTS
In this section, we experimentally validate proof of concept: that architectures containing exact blackbox solvers (with backward pass provided by Algo. 1) can be trained by standard methods.
Table 1: Experiments Overview.
Graph Problem
Solver
Solver instance size
Input format
Shortest path
Dijkstra
up to 900 vertices up to 1104 edges
(image) up to 240 x 240 (image) up to 528 x 528 up to 40 images (20 40)
Min Cost PM
Blossom
Traveling Salesman
Gurobi
up to 780 edges
To that end, we solve three synthetic tasks as listed in Tab. 1. These tasks are designed to mimic practical examples from Section and solving them anticipates two-stage process: 1) extract suitable features from raw input, 2) solve combinatorial problem over the features. The dimen- sionalities of input and of intermediate representations also aim to mirror practical problems and are chosen to be prohibitively large for zero-order gradient estimation methods. Guidelines of setting the hyperparameter À are given in section A.1.
We include the performance of ResNet18 (He al., 2016) sanity check to demonstrate that the constructed datasets are too complex for standard architectures.
The included solvers have very efficient implementations and do not severely impact runtime. All models train in under two hours on a single machine with GPU and no more than 24 utilized CPU cores. Only for the large TSP problems the solver's runtime dominates.
Remark 2.
4.1 WARCRAFT SHORTEST PATH
Problem input and output. The training dataset for problem SP(k) consists of 10000 examples of randomly generated images of terrain maps from the Warcraft II tileset (Guyomarch, 2017). The maps have an underlying grid dimension x where each vertex represents a terrain with fixed cost that is unknown to the network. The shortest (minimum cost) path between top left and bottom right vertices is encoded as an indicator matrix and serves as a label (see also Fig. 4). We consider datasets SP))) for l (12, 18, 24, 30). More experimental details provided in section A.3.

---

Published as a conference paper at ICLR 2020
Label
1 0 ...
1 0
Inpui
k indicator matrix of shortest path
(a)
(b)
Figure 4: The SP(k) dataset. (a) Each input is a k x i grid tiles corresponding to a Warcraft II terrain map, the respective label is the matrix indicating the shortest path from top left to bottom right. (b) is a different map with correctly predicted shortest path.
Architecture. An image of the terrain map is presented a convolutional neural network which outputs a x k grid of vertex costs. These costs are then the input to the Dijkstra algorithm to compute the predicted shortest path for the respective map. The loss used for computing the gradient update is the Hamming distance between the true shortest path and the predicted shortest path.
Results. Our method lears to pre- dict the shortest paths with high ac- curacy and generalization capability, whereas the ResNet18 baseline un- surprisingly fails to generalize al- ready for small grid sizes of k 12. Since the shortest paths in the maps often nonunique (i.e. there are multiple shortest paths with the same cost), we report the percentage of shortest path predictions that have optimal cost. The results are summa- rized in Tab. 2.
Table 2: Results for Warcraft shortest path. Reported is the accuracy, i.e. percentage of paths with the optimal costs. Standard deviations are over five restarts.
Embedding Dijkstra
ResNet18
k
Train %
Test %
Train %
Test %
12
99.7 + 0.0
96.0 + 0.3
100.0 + 0.0
23.0 1.0::00 0.3
18
98.9 1 0.2
94.4 0.2
99.9 0.0
0.7
24
97.8
0.2
94.4
1.0
0.0
30
9.1
94.0
95.6 0.5
0.0
4.2 GLOBE TRAVELING SALESMAN PROBLEM
Problem input and output. The training dataset for problem TSP(k) consists of 10000 examples where the input for each example is k-element subset of fixed 100 country flags and the label the shortest traveling salesman tour through the capitals of the corresponding countries. The optimal tour is represented by its adjacency matrix (see also Fig. 5). We consider datasets TSP(k) for & E (5, 10, 20, 40).
Label
Input & flugs
l: x l adjacency matrix with optimal TSP tour
(a)
(b)
Figure 5: The TSP(K) problem. (a) illustrates the dataset. Each input is a sequence of & flags and the corresponding label is the adjacency matrix of the optimal TSP tour around the corresponding capitals. (b) displays the learned locations of 10 country capitals in southeast Asia and Australia, accurately recovering their true position.
7

---

Published as a conference paper at ICLR 2020
Architecture. Each of the k flags is presented to convolutional network that produces io three- dimensional vectors. These vectors are projected onto the unit sphere in R²; representation of the globe. The TSP solver receives a matrix of pairwise distances of the k computed locations. The loss of the network is the Hamming distance between the true and the predicted TSP adjacency matrix. The architecture is expected to learn the correct representations of the flags (i.e. locations of the respective countries' capitals on Earth, up to rotations of the sphere). The employed Gurobi solver optimizes mixed-integer programming formulation of TSP using the cutting plane method (Marchand et al., 2002) for lazy sub-tour elimination.
Results. This architecture not only learns to extract the correct TSP tours but also learns the correct represen- tations. Quantitative evidence is pre- sented in Tab. 3, where we see that the learned locations generalize well and lead to correct TSP tours also on the test set and also somewhat large instances (note that there are 39! x 10a6 admissible TSP tours for k = 40). The baseline architecture only memorizes the training set. Additionally, we can extract the suggested locations of world capi-
Table 3: Results for Globe TSP. Reported the full tour accuracy. Standard deviations are over five restarts.
Embedding TSP Solver
ResNet18
k
Train %
Test %
Train %
Test %
5
99.8 + 0.0
99.2 + 0.1
100.0 + 0.0
1.9 - 0.6
10
99.8 + 0.1
98.7 = 0.2
99.0 = 0.1
0.0
20
99.1 + 0.1
98.4 0.4
98.8 + 0.3
0.0 0.0
40
9.2
96.7 1 0.4
0.3
0.0 0.0
tals and compare them with reality. To that end, we present Fig. 5b, where the learned locations of 10 capitals in Southeast Asia are displayed.
4.3 MNIST MIN-COST PERFECT MATCHING
Problem input and output. The training dataset for problem PM( consists of 10000 examples where the input to each example is a set of k22 digits drawn from the MNIST dataset arranged in a k x k grid. For computing the label, we consider the underlying k x k grid graph (without diagonal problem, where edge weights are given simply
edges) and solve a MIN-COST- PERFECT- by reading the two vertex digits as two-digit number (we read downwards for vertical edges and from left to right for horizontal edges). The optimal perfect matching (i.e. the label) is encoded by an indicator vector for the subset of the selected edges, see example in Fig. 6.
The grid image is the input of a convolutional neural network which outputs grid of vertex weights. These weights transformed into edge weights as described above and given to the solver. The loss function is Hamming distance between solver output and the true label.
Architecture.
Results. The architecture con- taining the solver is capable of good generalizations suggesting that the correct representation is learned. The performance good even on larger instances and despite the presence of noise in supervision often there are many optimal matchings. con- trast, the ResNet18 baseline only achieves reasonable performance for the simplest case PM) The results are summarized in Tab. 4.
Table 4: Results for MNIST Min-cost perfect matching, Re- ported is the accuracy of predicting an optimal matching. Stan- dard deviations are over five restarts.
Embedding Blossom V
ResNet18
k
Train %
Test %
Train
Test %
4
99.97 + 0.01 98.32 0.24
100.0 + 0.0
92.5 + 0.3
8
99.95 + 0.04 99.92 0.01
100.0 - 0.0
8.3 0.8
16
99.02 + 0.84 99.06 0.57
100.0 0.0
0.0
24
95.63 = 5.49 92.06
7.97
96.1 0.5
0.0
5 DISCUSSION
We provide a unified mathematically sound algorithm to embed combinatorial algorithms into neu- ral networks. Its practical implementation is straightforward and training succeeds with standard deep learning techniques. The two main branches future work are: 1) exploring the potential of newly enabled architectures, 2) addressing standing real-world problems. The latter case requires
8

---

Published as a conference paper at ICLR 2020
2
4
6
4
6
Imput
7
7
3
5 4
3
6
8
3
6
8
3
y
1
7
(
2
(-2
(b)
Figure 6: Visualization of the PM dataset. (a) shows the case of PM(4). Each input is 4 x 4 grid of MNIST digits and the corresponding label is the indicator vector for the edges in the min-cost perfect matching.
(b) shows the correct min-cost perfect matching output from the network. The cost of the matching 348 (46 12 horizontally and 27 + 45 40 67 + 78 + vertically).
embedding approximate solvers (that are common in practice). This breaks some of our theoretical guarantees but given their strong empirical performance, the fusion might still work well in practice.
ACKNOWLEDGEMEEN
We thank the International Max Planck Research School for Intelligent Systems (IMPRS-IS) for supporting Marin Vlastelica. We acknowledge the support from the German Federal Ministry of Education and Research (BMBF) through the Tbingen AI Center (FKZ: 011S18039B). Additionally, we would like to thank Paul Swoboda and Alexander Kolesnikov for valuable feedback on an early version of the manuscript.
REFERENCES
Google's 's or-tools, 2019. URL
Brandon Amos and J, Zico Kolter. Optnet: Differentiable optimization layer in neural networks. arXiv, 1703.00443, 2017. URL http://arriv.org/ab///0........
Brandon Amos, Lei Xu, and Zico Kolter. Input convex neural networks. In 34th International Conference on Machine Learning (ICML'17), pp. 146-155. JMLR, 2017.
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning branch. In Jennifer G. Dy and Andreas Krause (eds.). Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 353-362. PMLR, 2018. URL 8a.html.
http://poeeeddingg....rrrsss///s
Mislav Balunovic, Pavol Bielik, and Martin Vechev. Learning solve SMT formulas. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Besa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 10317-10328. Curran Associates, Inc., 2018
Peter Battaglia, Jessica Blake Chandler Hamrick, Victor Bapst, Alvaro Sanchez, Vinicius Zam- baldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre, Francis Song, Andy Ballard, Justin Gilmer, George E. Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Jayne Langston, Chris Dyer, Nicolas Heess, Daan Wier- stra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Rela- tional inductive biases, deep learning, and graph networks. arXiv, abs/1806.01220 2018. URL http://arxiv.org/abss 880.00121.
Irwan Bello, Hieu Pham, Quoe V. Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. In 5th International Conference Learning Repre- sentations, ICLR 2017, Workshop Track Proceedings, 2017. URL http://opanevioo..ee//oomm id=Bk9mxISFx.
L. Chen, G. Papandreou, Kokkinos, K. Murphy, and A. L. Yuille. DeepLab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected CRFs. IEÉE Transactions Pattern Analysis and Machine Intelligence, 40(04):834-844 848, 2018.

---

Published as a conference paper at ICLR 2020
Liang- Chigc Chen, Alexander G. Schwing, Alan L. Yuille, and Raquel Urtasun. Learning deep the 32nd International Conference on International Confer- ence on Machine Learning. ICML' 15, pp. 1785-1787751 1794. JMLR, 2015.
structured models. In Proceedings the
Emir Demirovic, Peter Stuckey, James Bailey, Jeffrey Chan, Christopher Leckie, Kotagiri Ra- mamohanarao, and Tias Guns. Predict+optimise with ranking objectives: Exhaustively learning linear functions. In Sarit Kraus (ed.), Proceedings of the Twenty- International Joint Con- ference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pp. 1078-1085. URL
ijcai.org, 2019. doi: 2224999//aaiii011999/
Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin Rousseau. Learning heuristics for the tsp by policy gradient. In Willem-Jan van Hoeve (ed.), Proc. of Intl. Conf. on Integration of Constraint Programming, Artificial Intelligence, and Opera- tions Research, pp. 170-181. Springer, 2018.
E. W. Dijkstra. A note on two problems in connexion with graphs. Numer, Math., 1(1):269-271, December 1959. doi: 10. 10.1007/BF0138699
Justin Domke. Generic methods for optimization-based modeling. In Artificial Intelligence and Statistics, pp. 318 326, 2012.
Jack Edmonds. Paths, trees, and flowers. Canad. J. Math., 17:449 1965. URL www.cs. sekkeeeeeeu--hhnsssscclsscceoono
Adam N. Elmachtoub and Paul Grigas. Smart "predict, then optimize". ArXiv, abs/ abs/1710.08005, 2017.
Aaron Ferber, Bryan Wilder, Bistra Dilkina, and Milind Tambe. Mipaal: Mixed integer program as layer. CoRR, abs/1907.05912, 2019. URL http://arxiv.org/abs/ https///9900099999
Chuan-sheng Foo, Chuong B Do, and Andrew Ng. Efficient multiple hyperparameter learning for log-linear models. In Advances in neural information processing systems, pp- 377-384, 2008.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combina- torial optimization with graph convolutional neural networks. arXiv, abs/1906.01629, 2019. URL http://akkii.oog/ab///9990
John C. Gower and Garmt B. Dijksterhuis. Procrustes problems, volume 30 of Oxford Statistical Science Series. Oxford University Press, Oxford, UK, January 2004.
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. arXiv, abs/ abs/1440.5540, 2014.
URL http://arxiv.or//abb// httpg//////////..5..0 410.5400.
Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska- Barwiñska, Sergio Gómez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, Adrià Puigdomenech Badia, Karl Moritz Hermann, Yori Zwols, Georg Ostrovski, Adam Cain, Helen King, Christopher Summerfield, Phil Blunsom, Koray Kavukcuoglu, and Demis Hassabis. Hybrid computing using a neural network with dynamic external memory. Nature, 538(7626): 471 October 2016.
Reynolds.
LLC Gurobi Optimization. Gurobi optimizer reference manual, 2019. URL http://wwww.gurbbi.omm
Jean Guyomarch. Warcraft ii open-source map editor, 2017. URL http://gittbbboo///waawaaaaaaeee
Tamir Hazan, Joseph Keshet, and David A. McAllester. Direct loss minimization for structured prediction. In Advances in Neural Information Processing Systems 23, pp. 1594-1602. Curran Associates, Inc., 2010.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In The IEEE Conference Computer Vision and Pattern Recognition (CVPR), June 2016.
Elias B. Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch mixed integer programming. In Proceedings of the Thirtieth AAAI Conference on Arti- ficial Intelligence, AAAI16, pp. 724731. AAAI Press, 2016
10

---

Published as a conference paper at ICLR 2020
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2014. cite Published as a conference paper at the 3rd International Conference for Learning Representations, San Diego, 2015.
Patrick Knöbelreiter, Christian Reinbacher, Alexander Shekhovtsov, and Thomas Pock. End-to-end training of hybrid cnn-crf models for stereo. In JEEE Conference Computer Vision and Pattern Recognition (CVPR' 17), July 2017.
Vladimir Kolmogorov. Blossom V: new implementation of minimum cost perfect matching algorithm. Mathematical Programming Computation, 1(1):43-67, Jul 2009. doi: 10.1007/ $12532-009-0002- 8. URL http://ppbbistaaacaaaa/vvssstaat
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference Learning Representations (ICIR 19), 2019. URL htpp//pppennrr.
Yujia Li, Richard Zemel, Mare Brockschmidt, and Daniel Tarlow. Gated graph sequence neural networks. In International Conference on Learning Representations (ICLR' 16), 2016. URL. http://axii..rr//ab//1111..3...
Zhuwen Li. Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolu- tional networks and guided tree search. In Advances in Neural Information Processing Systems, NeurlPS'18 18, pp. 537-546, USA, 2018. Curran Associates Inc.
Ziwei Liu, Xiaoxiao Li, Ping Luo, Chen-Change Change Loy, and Xiaoou Tang. Semantic image segmenta- tion via deep parsing network. In IEEE International Conference on Computer Vision, ICCV' 15, pp. 1377-1385. IEEE Computer Society, 2015. doi: 10. 10111CCC.220115...6.
Guy Lorberbom, Andreea Gane, Tommi S. Jaakkola, and Tamir Hazan. Direct optimization through arg max for discrete variational auto-encoder. arXiv, abs/1806.08 806.02867, 2018. URL http://arxiv. Bataaas/1806.0220
Jaynta Mandi, Emir Demirovic, Peter J. Stuckey, and Tias Guns. Smart predict-and-opimiize for hard combinatorial optimization problems. CoRR, abs/1911.10092, 2019, URL http://arxivvorg/
abs/1911.1000
Hugues Marchand, Alexander Martin, Robert Weismantel, and Laurence Wolsey. Cutting planes in integer and mixed integer programming. Discrete Appl. Math., 123(1-3):397-446, November 2002. doi: (0066/0066-2188((0)
Dmitrii Marin, Meng Tang. Ismail Ben Ayed, and Yuri Boykov. Beyond gradient descent for reg- ularized segmentation losses. In IEEE Conference Computer Vision and Pattern Recognition (CVPR'I9) 19), June 2019.
Shakir Mohamed, Mihaela Rosca, Michael Figurnov, and Andriy Mnih. Monte carlo gradient esti- mation in machine learning. arXivv abs/1906.10652 2019. URL http://axxiv.orr/aa////99/ 1901.10652.
Pritish Mohapatra, Michal Rolínck, C.V. Jawahar, Vladimir Kolmogorov, and M. Pawan Kumar. Efficient optimization for rank-based loss functions. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR' 18), June 2018.
MohammadReza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takac. Reinforcement learning for solving the vehicle routing problem. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Dasa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Process- ing Systems 31, pp. 9839-98849 Curran Associates, Inc., 2018. URL http://apper..isscccopeee 9190-reinforccement learning- for colvsolving--tee wheeiine- wwwweveeeiiiiiiiieeeeeee wowttirooooooooooommpppr. problem.pdf.
Vlad Niculae, Andre Martins, Mathieu Blondel, and Claire Cardie. SparseMAP: Differentiable sparse structured inference. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. -899, Stockholmsmssan, Stockholm Sweden, 10-15 Jul 2018. PMLR. URL mlr http:///eedddii.mmmmeeee//////ie html.

---

Published as a conference paper at ICLR 2020
Despoina Paschalidou, Ali Osman Ulusoy, Carolin Schmitt, Luc Gool, and Andreas Geiger. Raynet: Learning volumetric 3d reconstruction with ray potentials. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR 18), 2018.
Leonid Pishchulin, Eldar Insafutdinov, Siyu Tang, Bjöm Andres, Mykhaylo Andriluka, Peter Gehler, and Bernt Schiele. Deepcut: Joint subset partition and labeling for multi person pose estimation. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR' 16), pp. 4929-4937. IEEE, 2016.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks, 2015. URL http://arxiv.or//aas///S. 15.044434.
Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP? Proceed- ings of the 40th Annual ACM Symposium on Theory of Computing, STOC '08, pp. 245-254, New York, NY, USA, 2008. ACM. doi: 10.1145/1374376.117444
Kegan GG Samuel and Marshall F Tappen. Learning optimized map estimates in continuously- valued mrf models. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR 00), pp. 477-484, 2009.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. Trans. Neur. Netw., 20(1):61-80, January 2009. ISSN 1045- 9227. doi: 10. I 1009/TNN.008..00 2005605.
Uwe Schmidt and Stefan Roth. Shrinkage fields for effective image restoration. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR' 14), pp. 2774-2781, 2014.
Samuel Schulter, Paul Vernaza, Wongun Choi, and Manmohan Krishna Chandraker. Deep network flow for multi-object tracking. IEEE Conference on Computer Vision and Pattern Recognition 2017.
(CVPR' 17), pp. 2730-2739, 2017.
Daniel Selsam and Nikolaj Bjørner. Guiding high- perhrmerrfomecce SAT solvers with Unsat-Cor predic- tions. In Mikolás Janota and Inês Lynce (eds.), Theory and Applications of Satisfiability Testing SAT 2019, pp. 336-353 Springer International Publishing, 2019.
Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang. Leonardo de Moura, and David L. Dill. Learning SAT solver from single-bit supervision. In International Conference on Learning Representations (ICLR' 19), 2019. URL
iA5tm.
Jie Song, Bjoern Andres, Michael Black, Otmar Hilliges, and Siyu Tang. Ead-to-end learning for graph decomposition. arXiv,, 1812.09733 2018. URL http://aaiiv.org/bbs/1/12.00
Yang Song, Alexander Schwing, Richard, and Raquel Urtasun. Training deep neural networks via direct loss minimization. In 33rd International Conference on Machine Learning (ICML), volume 48 of Proceedings of Machine Learning Research, pp. 2169-2177. PMLR, 2016
Sainbayar Sukhbaatar, Arthur Szlam, Jason Weston, and Rob Fergus. End-to-end memory networks. In Advances in Neural Information Processing Systems 28 (NIPS), pp. 2440-2448. Curran Asso- ciates, Inc., 2015.
Johan Thapper and Stanislav Živný. The limits of SDP relaxations for general-valued CSPs, In 32nd Annual ACM/IEEE Sympossum on Logic in Computer Science, LICS '17, pp. 27:1-27:12, Piscataway, NJ, USA, 2017. IEEE Press.
Jonathan J Tompson, Arjun Jain, Yann LeCun, and Christoph Bregler. Joint training of a con- volutional network and a graphical model for human pose estimation. In Advances in Neural Information Processing Systems 27 (NIPS' pp. 1799-1807. Curran Associates, Inc., 2014.
Sebastian Tschiatschek. Aytunc Sahin, and Andreas Krause. Differentiable submodular maximiza- tion. In Proc. International Joint Conference on Artificial Intelligence (IJCAI), July 2018.
Ioannis Tsochantaridis, Thorsten Joachims, Thomas Hofmann, and Yasemin Altun. Large margin methods for structured and interdependent output variables. J. Mach. Learn. Res., 6: 6:1453-1484, 2005.
12

---

Published as a conference paper at ICLR 2020
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly, Pointer networks. In Advances in Neural Information Processing Systems 28 (NIPS' pp. 2692-2700. Curran Associates, Inc., 2015.
Po-Wei Wang, Priya L. Donti, Bryan Wilder, and Zico Kolter. SATNet: Bridging deep learning and logical reasoning using differentiable satisfiability solver. arXiv, 1905.12149. 2019. URL
http://axiv.org/abbs/ 12144
Bryan Wilder, Eric Ewing, Bistra Dilkina, and Milind Tambe. End to end learning and optimization graphs. In H. Wallach, Н. Larochelle, A. Beygelzimer, F. d Alche- Buc, E. Fox, and R. Garnett (eds.). Advances in Neural Information Processing Sys- tems 32, pp. 4674-4685. Curran Associates, Inc., 2019. URL http://apers.iipsccc/aapa 8715-end- to- -oeenddttenn------ end-learning-- and-opiimizationn on- on-graphs.pdf.
Mang Ye, Andy J. Ma, Liang Zheng. Jiawei Li, and Pong C. Yuen. Dynamic label graph matching for unsupervised video re-identification. IEEE International Conference on Computer Vision (ICCV'17. IEEE Computer Society, Oct 2017.
Shuai Zheng, Sadeep Jayasumana, Bernardino Romera- Pareeee, Vibhav Vineet, Zhizhong Su, Da- long Du, Chang Huang, and Philip H. S. Torr. Conditional random fields as recurrent neural networks. In IEEE International Conference on Computer Vision (ICCV'15, pp. 1529-1537. IEEE Computer Society, 2015.
A APPENDIX
A.1 GUIDELINES FOR SETTING THE VALUES X.
In practice, has to be chosen appropriately, but found its exact choice uncritical (no precise tun- ing was required). Nevertheless, note that should cause a noticeable disruption the optimization problem from equation (3), otherwise it is too likely that y(w) ya (w) resulting in gradient. In other words, À should roughly be the magnitude that brings the two terms the definition of w/ in Prop. to the same order:
AL
where (-) stands for the average. This again justifies that is a true hyperparameter and that there reason expect values around À - 0
A.2 PROOFS
Proof of Proposition 1. Let us write L(D) and VL + (D). for brevity. Thanks to the linearity of c and the definition of f, we have
c(ύ. y) + Af(()) = dyy X(L + VL 0)) = (1 + XVL + AL AVLJ = c(w', ())))= +
where Co = AL - A Lo and w' = ú + LVL as desired. The conclusion about the points minima then follows.
Before prove Theorem make preliminary observations. To start with, due to the definition of the solver, we have the fundamental inequality
c(w, v) 2 cl w. w(w)) for every W and y E E
(6)
Observation 1. The function w + c(w, v(w)) is continuous and piecewise linear.
Since c's are linear and distinct, c(w, y(w)), as their pointwise minimum, has the desired properties.
Proof.
13

---

Published as a conference paper at ICLR 2020
Analogous fundamental inequality
c(w, v) + (f(1) c(w,yx(w) + Xʃ (vx(w) for every E W and Y
follows from the definition of the solution to the optimization problem (3).
counterpart Observation reads as follows.
Observation 2. The function + c(w, yx(w)) + (f(xxw)) is continuous and piecewise affine.
Proof. The function under inspection pointwise minimum of distinct affine functions w c(w, + Xf(y) as ranges Y.
As consequence of above-mentioned fundamental inequalities, we obtain the following two-sided estimates on Sa-
Observation 3. The following inequalities hold for w E W
f(yx(w)) & fx(w) I f(v(w)).
Proof. Inequality (6) implies that c(w, v(w)) - c(w, v2()) I 0 and the first inequality then follows simply from the definition of fx- As for the second one, suffices apply (7) y (w)).
Now, let us introduce few notions that will be useful later the proofs. For fixed X, W partitions into maximal connected sets P which yx (www) is constant (see Fig. 7). We denote this collection of sets by WA and set W = Wo-
For IR and yn # 1/2 Y, denote
Fx 82) {w W c(w, + Xf(11) c(w, (22 + *f(22))
We write F(y1, 92) (811 12), for brevity. For technical reasons, we also allow negative values
of X here.
f(ys)
f(s)
(yx(w))
f(ea)
f(ya)
f(n))
I (v(w))
f(n1)
f(((w))
f f(va)
f
P
P
f12z)
f(22)
F Fu V2)
F 82) F F(y1, Us)
W
F v2)
W
(a) The situation for polytope on which y(w) attains yı E The boundary P is composed segments lines F(y1, ) for lo 5.
We the
The situation is captured for rela- tively small Each line Fx (y1, yx is par- allel to corresponding F U6) and encom- passes convex polytope in WA.
Figure 7: The family WA of all maximal connected sets P on which yA constant.
Note, that if W R then Fx hyperplane since c's are linear. In general, W may just be proper subset of R and, in that case, Fx is just the restriction of hyperplane onto W. Consequently, may happen that Fx(11 y2) will be empty for some pair of y/1, y2 and some E R. To emphasize this fact, we say "hyperplane in W Analogous considerations should be taken into account for all other linear objects. The note "in W stands for the intersection of these linear object with the set W.
14

---

Published as a conference paper at ICLR 2020
Observation 4. Let P Wx and let yx(w)= y for P. Then P is convex polytope in W, where the facets consist of parts of finitely many hyperplanes Ex(y, yk) in W for some {yke) C Y.
Proof. Assume that W RR The values of ya may only change on hyperplanes of the form
(v. s/) for some y' E Y. Then P is an intersection of corresponding half-spaces and therefore P a convex polytope. If W is a proper subset of IR the claim follows by intersecting all the objects with W.
Let Y1, 1/2 E Y be distinct. If nonempty. the hyperplanes F(11, 122 and Fx (1)1)32) are parallel and their distance equal [A]K (y1, 92), where
Observation 5.
[(()) s(22)1
K K(y1 92)
11y1 -22ll
Proof. If define function c(w) c(w, v1) c(w, 822) w(y1 12) and constant C f(92) - f(y1), then our objects rewrite to
Fly1 y2) {w W c(w) = 0} and Fx 92) {ur W c(w) = AC}.
Since is linear, these sets are parallel and 32) intersects the origin. Thus, the required distance is the distance of the hyperplane (1 y2) from the origin, which equals to |ACI/Ily 32ll-
As the set Y is finite, there is uniform upper bound K on all values of (111, U2). Namely
K
max K K31 822..
(8)
A.2.1 PROOF THEOREM 1
Proof of Property A1. Now, Property AI follows, since
fx(w) = X [[((w,ux(w) + xf(vx(w)) x c(w,v(w)) v(w)
and fx is difference of continuous and piecewise affine functions.
Proof of Property A2. Let < a I x be given. We show that W C W which is the same as showing W C way. Assume that W that is, by the definition of W and fx.
eq
c(w, v(w)) + (y((w = c(w, y2) + (2f(22),
(9)
in which we denoted y/ = yA, (w). Our goal is to show that
c(w, v(w) + An (v(w)) = c(w. vn) + (
(10)
where y1 = yx, (w) this equality then guarantees that W Observe that (7) applied to X A and y y(w), yields the inequality "z" in (10).
Let us show the reversed inequality. By Observation applied to A₁. we have (y(wr) 2 ((1)
(11)
We now use (7) with À = d2 and y y1. followed by equality (9) to obtain
c(w, - (11( = c(w, + Aef( + (A1 - f c(w, U2) )2f(v2) + (h1 (2)
cw,,y(w) + (zf(((w)) + (A1 (2)f((1)
c(w,y(w) >n,(((()) + (A2 A))(F(((w)) f(0r)
2 c(w, w(w) A A)((1())
where the last inequality holds due (11).
15

---

Published as a conference paper at ICLR 2020
Next, we have to show that War + 0 as À + 0+, i.e. that for almost every w E W, there is a such that w & W To this end, let W be given. We can assume that y(w) is unique solution of solver (I), since two solutions, say 31 and y2, coincide only on the hyperplane F(y1, 92) in W, which is of measure zero. Thus, since Y is finite, the constant
c min yEY v
{o(w, y) - c(w, y(w))}
is positive. Denote
d max ( - f(v))-
(12)
vEY
If > set x < c/d. Then, for every y E Y such that (y((1)) [(v), we have
A c(w,y) y) www))
f(((w) f(y)
which rewrites
((w) + (f(((w)) c(w, y) + Af(y).
(13)
For the remaining y's, (13) holds trivially for every > O. Therefore, y(w) solution of the minimization problem (3), whence vx(w) = y(w). This shows that w E WA as we wished. If d then / (v(w)) f(y) for every y E Y and (13) follows again.
Proof of Property A3. Let Ø1 + y2 E Y be given. We show that on the component of the set
{w E y(w)- = y/1 and yx = W/2
(14)
the function fx agrees with d-interpolator, where 5 < CA and C >> 0 is an absolute constant. The claim follows as there are only finitely many sets and their components of the form (14) in W.
Let us set
h(w) = c(w, y1) - c(w. 8/2
for w E W
and
g(w) = f(22
1 X
M(r).
The condition on tells us that h is a non-constant affine function. It follows by the definition of Fly y2) and Fx (311.132 that
h(w) = 0 if and only if w E F(11882)
(15)
and
hww) = (f((2)) (w1) if and only if w E Fx(1,
(16)
By Observation 5, the sets F and F' are parallel hyperplanes. Denote by G the nonempty intersec- tion of their corresponding half-spaces in W. We show that g a d-interpolator y1 and y2, with 8 being linearly controlled by X.
on G between
We have already observed that g is the affine function ranging from f(y)) on the set Fx U2)
to f12) - on the set F(y1, y2). It remains to show that g attains both the values f(y1) and f(12) most 8-far from the sets P1 and Pz, respectively, where Ps E W denotes a component of the set {w E W v(w) }. 1,2.
Consider /1 first. By Observation 4, there are 21. 24 E Y, such that facets of P1 are parts of hyperplanes F1 FM,, =z) in W. Each of them separates W into two half-spaces, say W and WE, where W. is the half-space which contains P1 and W is the other one. Let us denote
Ca (w) = c(w. vn) - c(w, zx) for w E W and h = 1, I,
Every is non-zero linear function which is negative on W, and positive on W By the definition of y1, we have
for w P1 and for is 1...., c(w, vn) Af(v)) c(w, 2x) + (f(x))
that is
cx(w)= & (({(z)) ((11) for Pi and for k 1 1,...,f.
16

---

Published as a conference paper at ICLR 2020
(ws)) (2())
f(n)
P.
P
f
PA
W
F(y).
FX 92)
FF
F 422
(a) The facets of Pt consist of parts of hyper- planes F(yn, =u) in W. Each facet F(yn, zu) has its corresponding shifts F3 and F-A. from which only one intersects P. The polytope P is bounded by those outer shifts.
(h) The interpolator attains the value {V1) on part of Fx(yn, y2) border of the domain G. The value (122 attained part of F(gh, y2) the second border the strip G.
Figure 8: The polytopes P1 and PA and the interpolator g.
Now, denote
W = { w W (w)) S f)f(()))
f(y))} -(xn))))(( for k 1....,
Each W. is half-space in W containing W and hence P1. Let us set P. = N W Clearly, Pi S PA (see Fig. 8). By Observation 5, the distance of the hyperplane {w E W cx(w) = Aff(z)) f(y1))} from Pi is at most AK, where K is given by (8). Therefore, since all the facets of PA are most AK far from P1, there constant C such that each point of PA most C'A far from P1.
Finally, choose any W1 E P n FX 92). By (16), we have g(w1) f(y1), and by the definition of PA, is no farther than C'A away from Pt.
Now, let treat y/2 and define the Pa analogous PAA. where each occurrence of yı replaced by V/- Any Wa E PA n FI M2) has desired properties. Indeed, (15) ensures that g(w2) f and We most CA far away from Pz.
A.3 DETAILS OF EXPERIMENTS
A.3.1 WARCRAFT SHORTEST PATH
The maps for the dataset have been generated with a custom random generation process by using 142 tiles from the Warcraft II tileset (Guyomarch, 2017). The costs for the different terrain types range from 0.8-9.2. Some example maps of size 18 x 18 are presented in Fig. 9a together with histogram of the shortest path lengths. We used the first five layers of ResNet18 followed by max-pooling operation to extract the latent costs for the vertices.
Optimization was carried via Adam optimizer (Kingma & Ba, 2014) with scheduled learning rate drops dividing the learning rate by 10 at epochs 30 and 40. Hyperparameters and model details listed in Tab.
Table 5: Experimental setup for Warcraft Shortest Path.
k
Optimizer(LR)
Architecture subset of ResNet18
Epochs
Batch Size
12, 18. 24, 30
Adam(5 10 10"
50
70
20
17

---

Published as a conference paper at ICLR 2020
18x
rel. friquency
0.10
0.05
0.00
shortest path length
(a) Three random example maps.
(b) the shortest path distribution the training All possible path lengths (18-35) oceur.
Figure 9: Warcraft SP(18) dataset.
A.3.2 MNIST MIN-COST PERFECT MATCHING
The dataset consists of randomly generated grids of MNIST digits that are sampled from subset of 1000 digits of the full MNIST dataset. We trained a fully convolutional neural network with two convolutional layers followed by max max-pooling operation that outputs a k x grid of vertex costs for each example. The vertex costs transformed into the edge costs via the known cost function and the edge costs are then the inputs to the Blossom V solver (Edmonds, 1965) as implemented in (Kolmogorov, 2009).
Regarding the optimization procedure, we employed the Adam optimizer along with scheduled learning rate drops dividing the learning rate by 10 epochs 10 and 20, respectively. Other training details are in Tab. 6. Lower batch sizes were used to reduce GPU memory requirements.
Table Experimental setup for MNIST Min-cost Perfect Matching.
Architecture
k
Optimizer(I.R)
Epochs
Batch Size
X
[channels, kernel size, stride]
4,
Adam(10-9)
[20, 5, 1], [20, 5, 1]]
30
70
10
16
Adam(10-3)
[50, 5, 1], [50, 5, 1]
30
40
10
24
Adam(10-)
[500, 5, 1], [50, 5, 1]]
30
30
10
A.3.3
GLOBE TRAVELING SALESMAN PROBLEM
For the Globe Traveling Salesman Problem we used a convolutional neural network architecture of three convolutional layers and two fully connected layers. The last layer outputs vector of dimension 3k containing the 3-dimensional representations of the respective countries' capital cities. These representations are projected onto the unit sphere and the matrix of pairwise distances fed to the TSP solver.
The high combinatorial complexity of TSP has negative effects the loss landscape and results in many local minima and high sensitivity to random restarts. For reducing sensitivity to restarts, we Adam parameters 3 0.5 (as done for example in GAN training (Radford et al., 2015)) and c 10
The local minima correspond to solving planar TSP as opposed spherical TSP. For example, all cities are positioned to almost identical locations, the network can still make progress but it will never have the incentive to spread the cities apart in order to reach the global minimum. mitigate that, we introduce a repellent force between epochs 15 and 30. In particular, we set
Lyep
E e 11=1== i7j
where 2; E 3 for = = ........k. are the positions of the cities on the unit sphere. The regularization constants C2 were chosen as 3.0. 6.0. and 20.0 for (5, 10, 20, 40).
For fine-tuning we also introduce scheduled learning rate drops where we divide the learning rate by 10 epochs 80 and 90.
18

---

Published as a conference paper at ICLR 2020
Table 7: Experimental setup for the Globe Traveling Salesman Problem.
Architecture
k
Optimizer(LR)
[channels, kernel size, stride],
Epochs
Batch Size
A
linear layer size
5, 10, 20
Adam(100
[20, 4, 2]. [50, 4, 2]. 500
100
50
20
40
Adam(5 x 10-5)
[20, 4, 2], (50, 4, 2]. 500)
100
50
20
In Fig. 5b, we compare the true city locations with the ones learned by the hybrid architecture. Due to symmetries the sphere, the architecture can embed the cities any rotated or flipped fashion. We resolve this by computing "the most favorable" isometric transformation of the suggested locations. In particular, we solve the orthogonal Procrustes problem (Gower & Dijksterhuis, 2004)
R arg min |RX -
R=1
where X are the suggested locations, Y the true locations, and Rº the optimal transformation apply. We report the resulting offsets in kilometers in Tab. 8.
Table 8: Average errors of city placement on the Earth.
k
5
10
20
40
Location offset (km)
69 + 11
19
+ 5
11
58 + 7
A.4 TRAVELING SALESMAN WITH APPROXIMATE SOLVER
Since approximate solvers often appear in practice where the combinatorial instances are too large to solved exactly in reasonable time, we test our method also this setup. In particular, we use the approximate solver (OR-Tools (ort, 2019)) for the Globe TSP. We draw two conclusions from the numbers presented below in Tab.
ii) The choice of the solver matters. Even if OR-Tools is fed with the ground truth represen- tations (i.e. true locations) it does not achieve perfect results on the test set (see the right column). We expect, that also in practical applications, running a suboptimal solver (e.g. differentiable relaxation) substantially reduces the maximum attainable performance.
(ii) The suboptimality of the solver didn't 't harm the feature extraction the point of our method. Indeed, the learned locations yield performance that close the upper limit of what the solver allows (compare the middle and the right column).
Table 9: Perfect path accuracy for Globe TSP using the approximate solver OR-Tools (ort, 2019). The maximal achievable performance is in the right column, where the solver uses the ground truth city locations.
Embedding OR-tools
OR-tools GT locations
k-
Train %
Test %
Test %
5
99.8 + 0.0
99.3 = 0.1
100.0
10
84.3 0.2
84.4 + 0.2
88.6
20
49.2 + 0.2
48.6 + 0.8
54.4
40
14.6 + 0.1
15.1 + 0.3
15.2
19


Reviews:
[{"review_id": "SyepKWTAKB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper shows how end-to-end learning can be done through\ncombinatorial solvers by using the derivative of\ncontinuous surrogate function in the backward pass.\nOne elegant part of the method is that no modification\nor relaxation is done to the combinatorial solver in\nthe forward pass and that the backward pass just requires\nanother call to the blackbox solver.\n\nThe idea of constructing continuous surrogate functions\nand using them for differentiating through solvers with\npiecewise-constant output spaces is thought-provoking and\nI can see it inspiring many new directions of work.\nFor example looking at Figure 2 for intuition, one could\nimagine other ways of making the solution space continuous.\nThe solution space of linear programs over continuous spaces,\nas considered in [Elmachtoub & Grigas], the Sudoku example in\n[Amos & Kolter], and related papers, is also piecewise constant and\nit seems like a similar method could be used to bring more\ninformative derivative information to linear programs ---\nhave you considered this as a future direction?\n\nOne of my concerns with this work is that the ResNet baseline in the\nexperimental results seems like too much of a straw man for the tasks.\nI do not see why they should have the capacity to generalize well.\nThis paper shows the ResNet baseline achieve near-zero\ntest accuracy but doesn't compare to other relevant baselines\nthat are mentioned in the related work section:\nfor example [Bello et al, Deudon et al., Kool et al.] for the TSP.\n\nAnd one smaller comment: If one wanted to squeeze the performance even\nmore, would starting the training process with a large \\lamdba\nand annealing it to zero help?\n\n----\n\nElmachtoub, A. N., & Grigas, P. Smart \"predict, then optimize\". arXiv 2017.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Hke2mmXCYB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a straightforward method for training black box solvers of a restricted kind (namely those with inputs in R^n and linear cost functions). The proposed algorithm is tested on path finding, the travelling salesman problem, and a min-cost-perfect-matching problem, with promising results.\n\nI would recommend accepting this paper. It is a well written paper with a novel idea supported by good experimental results.\n\nThe caveat is that I did not have the time to thoroughly review all the mathematical details. From a high-level they looked correct, and the math is sufficiently illustrated with figures and examples that it is easy for a reader to follow in detail given enough time.\n\nThe main shortcomings I see are that there are no experimental results comparing this method against any existing results; the authors do compare against their own ResNet18 implementation, but this is not ideal.\n\nI found the discussion a bit cryptic: Why are approximate solvers needed for real-world problems? Are there no real-world problems where exact solvers are still applicable?", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "ByxYxfZaKr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "=== Summary ===\nThe authors propose a method for efficiently backpropagating through unmodified blackbox implementations of exact combinatorial solvers with linear objective functions. \nThe gradient of such exact combinatorial solvers exists almost everywhere but is zero. The authors remark that the loss has the same gradient wrt to the solver's input as its linearization around the solver's input.  They therefore propose to interpolate the loss' linearization with a continuous (piecewise affine) function and use the gradient of this interpolation to backpropagate through the solver. This gradient is obtained efficiently by simply calling the solver on a single perturbed input (the perturbation depends on the incoming gradient, ie the gradient of the loss wrt to the solver's output).\nThe authors further study the properties of this piecewise affine interpolation and characterize its interpolation behavior as a function of a hyperparameter which controls the trade-off between \"how informative the gradient is\" and \"how faithful the interpolation is to the original solver\".\nThe authors validate their method with experiments on synthetic tasks that have both a visual processing aspect and a combinatorial aspect:\n    - Shortest Path on Warcraft II terrain maps\n    - TSP between country capitals where the inputs to the convnet are country flags\n    - Min-cost perfect matching from Mnist digits.\nSpecifically, they feed the output of a convnet to the relevant solver (depending on the task) and learn end-to-end by backpropagating through the solver with their proposed method. They show that their method successfully solves the tasks where baseline ConvNet architectures fail.\n\n=== Recommendation ===\n\nThis paper addresses an important problem and presents a novel approach.\n\nMethods for combining combinatorial optimization algorithms and machine learning usually rely on modifiying or relaxing the combinatorial problem itself which prevents using solvers as-is. \nIn contrast, the presented method allows to efficiently backpropagate through unmodified implementations of blackbox exact solvers with a linear objective. AFAIK this is the first method that allows this.\n\nA weakness of the paper is that the experiments only validate proof of concept (as noted by the authors). They are small-scale and only compare against conventional ConvNets baselines (as opposed to other approaches to backpropagate through relaxed combinatorial problems).\nAdditionally, the characterization of the interpolation (whose gradient is used) doesn't directly explain why the gradient of the interpolation is a reasonable choice.\n\nOverall, I recommend for acceptance.\n\n=== Questions / Comments ===\n- The authors show properties related to the interpolation behavior of the proposed interpolation function. What is the actual point/benefit of satisfying these properties? Are there arguments for why this is important besides the experimental results?  Is the point that since lambda controls how \"faithful vs informative\" the gradient is , there must be a range of values for lambda for which the method works? \n- It would be interesting to have experiments with non-exact solvers\n- It would be interesting to optimize directly for the combinatorial objective in the experiments (using a policy gradient for example) rather than perform supervised learning on the solutions.\n- Consider adding related work subsection on argmin optimization and meta-learning.\n\n\n\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a method for efficiently training neural networks combined with blackbox implementations of exact combinatorial solvers.

Reviewers and AC agree that it is a well written paper with a novel idea supported by good experimental results. Experimental results are of small scale and can be further improved, but the authors acknowledged this aspect well.

Hence, I recommend acceptance.
Decision: Accept (Spotlight)