PaperlayerView exact revision on arXiv

Source-linked AI summary

Differentiation of Blackbox Combinatorial Solvers

Marin Vlastelica, Anselm Paulus, Vít Musil, Georg Martius, Michal Rolínek

arXiv:1912.02175v2cs.LGstat.ML

TL;DR

Deep learning and combinatorial optimization remain difficult to combine because combinatorial solver components are nondifferentiable and differentiable relaxations can be suboptimal. The paper introduces an efficient backward pass for blackbox solvers with linear objectives, enabling unmodified solvers to serve as neural-network components. Experiments with Gurobi, Blossom V, and Dijkstra show successful training on TSP, min-cost perfect matching, and shortest-path tasks.

  • Problem

    Combining data-driven feature extraction with combinatorial optimization is limited by solver nondifferentiability and the suboptimality of differentiable relaxations.

  • Method

    The method computes an efficient backward pass through blackbox combinatorial algorithms or solvers optimizing linear objective functions, using a continuous interpolation derived from their minimization structure.

  • Results

    Architectures containing unmodified Gurobi, Blossom V, and Dijkstra implementations train without sophisticated tweaks and solve tasks beyond conventional neural networks’ capabilities.

  • Takeaways & Limitations

    The approach provides a unified way to embed combinatorial algorithms into neural networks, with practical implementation and training using standard deep-learning techniques.

  • Takeaways & Limitations

    Embedding approximate solvers would break some theoretical guarantees, although their empirical performance may still allow the fusion to work in practice.

Abstract

from arXiv · show

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. The code is available at https://github.com/martius-lab/blackbox-backprop.

1 INTRODUCTION

The paper addresses the difficulty of combining data-driven feature extraction with discrete optimization by differentiating through blackbox combinatorial solvers. Its method enables unmodified solvers to become neural-network building blocks, with experiments showing successful training and performance beyond conventional neural networks.

  • Motivation: Hybrid architectures combine deep learning’s data-driven feature extraction with classical combinatorial algorithms for tasks requiring global consistency.Examples include multi-object tracking and other computer-vision problems with combinatorial sub-tasks.
  • Problem: Differentiable modifications can sacrifice runtime, performance, or optimality guarantees because continuous outputs solve relaxations of discrete problems.The paper identifies this as a barrier to incorporating optimized, theoretically grounded algorithms directly into neural networks.
  • Contribution: The proposed method computes a backward pass for blackbox combinatorial algorithms or solvers that optimize linear objective functions, at the cost of one hyperparameter.This turns suitable solvers into composable neural-network components.
  • Technical approach: The backward pass efficiently differentiates a continuous interpolation derived from the solver’s minimization structure.Its computational cost matches the forward pass and requires one solver call.
  • Experiments: Experiments embed Gurobi, Blossom V, and Dijkstra’s algorithm into trainable architectures for TSP, min-cost perfect matching, and shortest-path tasks.The resulting architectures train without sophisticated tweaks and solve tasks beyond conventional neural networks’ capabilities.

2 RELATED WORK

Related work connects combinatorial algorithms and deep learning through applied hybrid systems, algorithmic structural priors, specialized neural building blocks, and learned solver heuristics.

  • Motivated by applied problems: Applied work uses hybrid approaches for computer-vision problems with strong combinatorial structure, including tracking, segmentation, pose estimation, stereo matching, and re-identification.These systems commonly involve Markov random fields and related combinatorial algorithms.
  • Motivated by “bridging the gap”: Foundational work bridges combinatorics and deep learning through algorithmic structural priors, including Turing-machine layouts and message-passing behavior.Graph neural networks are presented as an example of the latter direction.
  • Specialized building blocks: Another line of work supplies neural-network building blocks specialized for SAT, mixed-integer programs, sparse inference, and submodular maximization.This approach targets particular combinatorial problem classes rather than general blackbox solver differentiation.
  • Learning to improve solvers: A complementary direction uses deep learning to improve state-of-the-art combinatorial solvers by learning heuristics, including for TSP, NP-hard problems, and SAT.Here, learning improves solver behavior rather than embedding the solver as a differentiable neural component.

3 METHOD

The method differentiates blackbox combinatorial solvers by replacing their piecewise constant output function with a continuous interpolation whose gradient is informative. For linear objectives, the backward pass requires one solver call on perturbed input and balances gradient informativeness against faithfulness through λ.

  • Forward and backward pass: For linear objectives c(w, y) = w · φ(y), the backward pass perturbs the solver input by λ times the loss gradient and returns the resulting interpolation gradient.The perturbed output yλ is obtained by calling the original solver on the modified input, so the backward pass costs one solver call.
  • Solver formulation: The framework applies to general solver output spaces and includes shortest-path solvers whose outputs are edge-indicator vectors with costs given by the corresponding inner product.The solver definition imposes no assumptions on the constraint set or output-space structure beyond the stated finite-output formulation.
  • Solver formulation: Combinatorial solvers map continuous inputs to discrete minimizers, making their output function piecewise constant with an unhelpful zero gradient almost everywhere.This behavior is illustrated for shortest path, where edge-weight perturbations usually preserve the optimal path but occasionally change it drastically.
  • Continuous interpolation: The method constructs a continuous, piecewise-affine interpolation fλ of the solver-induced piecewise constant function f.Its construction leverages the minimization structure of the underlying combinatorial problem rather than generic zero-order gradient estimation.
  • Continuous interpolation: λ controls the trade-off between the interpolation’s gradient informativeness and its faithfulness to the original piecewise constant function.Increasing λ enlarges the region with meaningful gradients but can make the interpolation less faithful and displace interpolators farther from the corresponding solver regions.
  • Continuous interpolation: The interpolation consists of finitely many affine interpolators whose displacement is bounded linearly by λ.A δ-interpolator connects output values associated with two solver solutions, with endpoint displacement bounded by δ ≤ Cλ.

4 EXPERIMENTS

The experiments test whether neural architectures containing exact blackbox combinatorial solvers can be trained by standard methods on shortest-path, TSP, and matching tasks. Across these tasks, the hybrid models learn useful representations and generalize beyond conventional neural-network baselines.

  • Experimental setup: The experiments validate that architectures containing exact blackbox solvers can be trained with standard methods.The study uses three synthetic tasks designed to separate feature extraction from combinatorial optimization.
  • Warcraft shortest path: The shortest-path architecture maps terrain images to vertex costs, then uses Dijkstra’s algorithm and Hamming loss against the optimal path.The datasets contain 10000 Warcraft II terrain-map examples for k ∈ {12, 18, 24, 30}.
  • Warcraft shortest path: Shortest-path models achieve high-accuracy, generalizing predictions, while ResNet18 fails to generalize even for k = 12.Accuracy measures the percentage of predicted paths with optimal costs because multiple shortest paths may exist.
  • Globe traveling salesman problem: The TSP architecture converts flag inputs into spherical country-capital representations, computes pairwise distances, and predicts the optimal tour adjacency matrix.The experiments consider TSP(k) for k ∈ {5, 10, 20, 40}.
  • MNIST min-cost perfect matching: The matching task converts MNIST digit grids into edge weights and uses a min-cost perfect-matching solver to predict selected edges.Each example contains k^2 digits arranged in a k × k grid.
  • MNIST min-cost perfect matching: The matching architecture generalizes well, including on larger noisy instances, whereas ResNet18 performs reasonably only for PM(4).Noise arises because many distinct matchings can be optimal.

5 DISCUSSION

The discussion presents the method as a unified approach for embedding combinatorial algorithms into neural networks and identifies approximate solvers as an important future direction. Approximate solvers are common in practice but weaken some theoretical guarantees.

  • Discussion: The paper provides a unified mathematically sound algorithm for embedding combinatorial algorithms into neural networks.Its practical implementation is described as straightforward, and training succeeds with standard deep-learning techniques.
  • Discussion: The paper illustrates min-cost perfect matching through a 4 × 4 MNIST grid whose correct matching has cost 348.The reported cost is decomposed into horizontal and vertical edge contributions.
  • Discussion: A future direction is embedding approximate solvers, which are common in practice but break some of the method’s theoretical guarantees.The authors note that strong empirical performance may nevertheless allow the fusion to work well in practice.

A.1 GUIDELINES FOR SETTING THE VALUES OF λ.

λ should be large enough to noticeably disrupt the optimization problem while remaining easy to choose without precise tuning. Values near λ →0+ are not expected to be appropriate.

  • λ should noticeably disrupt the optimization problem; otherwise y(w) is likely to equal yλ(w), producing a zero gradient.The intended scale roughly balances the two terms defining w′ in Proposition 1.
  • The exact choice of λ was empirically uncritical, so precise tuning was unnecessary.
  • λ is a genuine hyperparameter, with no reason to expect useful values near λ →0+.

A.2 PROOFS

The proofs characterize the solver’s piecewise-constant regions and their perturbed geometric structure. They establish convex-polytopal regions, parallel boundaries, and uniform distance bounds controlled by λ.

  • The relevant objective functions are continuous and piecewise affine because they are pointwise minima of finitely many affine functions.
  • The solver partitions W into maximal connected regions Wλ on which yλ(w) is constant.W denotes the unperturbed collection W0.
  • The formulation permits negative λ and interprets linear objects as intersections with W when W is a proper subset of R^N.
  • Each region P ∈ Wλ is a convex polytope whose facets lie on finitely many hyperplanes Fλ(y, yk) in W.
  • For distinct solutions, F(y1, y2) and Fλ(y1, y2) are parallel when nonempty, with distance |λ|K(y1, y2).The distance follows from the linear cost difference and the finite solution set provides a uniform upper bound K.

A.2.1 PROOF OF THEOREM 1

Theorem 1 is proved by analyzing how perturbed solver regions relate to unperturbed regions and by constructing affine interpolators across shifted decision boundaries. The resulting approximation error is controlled linearly by λ.

  • For almost every w ∈ W, the disagreement set Wλdif shrinks to the empty set as λ →0+.The exception consists of points where the unperturbed solver has multiple solutions, which lie on measure-zero hyperplanes.
  • For sufficiently small λ, the perturbed and unperturbed solver outputs agree at points with a unique unperturbed solution.
  • On each relevant component, fλ agrees with a δ-interpolator satisfying δ ≤ Cλ for an absolute constant C > 0.
  • The interpolator g connects f(y1) on Fλ(y1, y2) to f(y2) on F(y1, y2) across parallel hyperplanes.
  • The values of g occur within distance Cλ of the corresponding unperturbed solution regions P1 and P2.

A.3.1 WARCRAFT SHORTEST PATH

The experiments embed combinatorial solvers in neural architectures for shortest paths, matching, and spherical TSP. The approximate-solver study shows that solver choice limits attainable performance, while feature extraction remains effective near that limit.

  • A.3.1 WARCRAFT SHORTEST PATH: The Warcraft shortest-path dataset uses 142 Warcraft II tiles, terrain costs from 0.8–9.2, and ResNet18 features to predict latent vertex costs.Maps include randomly generated 18 × 18 examples.
  • A.3.1 WARCRAFT SHORTEST PATH: The MNIST matching setup predicts a k × k grid of vertex costs, transforms them into edge costs, and passes them to Blossom V.
  • A.3.1 WARCRAFT SHORTEST PATH: The Globe TSP architecture predicts k three-dimensional capital-city representations, projects them onto the unit sphere, and feeds pairwise distances to the TSP solver.
  • A.3.1 WARCRAFT SHORTEST PATH: The approximate-solver experiment uses OR-Tools for Globe TSP and compares learned representations with the solver’s maximal achievable performance.
  • A.3.1 WARCRAFT SHORTEST PATH: Even with ground-truth city locations, OR-Tools does not achieve perfect test-set results, showing that solver choice constrains attainable performance.
  • A.3.1 WARCRAFT SHORTEST PATH: The learned locations achieve performance close to the upper limit allowed by the approximate solver, so solver suboptimality did not harm feature extraction.
Loading 1912.02175v2…