PaperlayerView exact revision on arXiv

Source-linked AI summary

Contrastive Losses and Solution Caching for Predict-and-Optimize

Maxime Mulamba, Jayanta Mandi, Michelangelo Diligenti, Michele Lombardi, Victor Bucarey, Tias Guns

arXiv:2011.05354v2cs.LGcs.AI

TL;DR

Predict-and-optimize must account for the effect of uncertain-input predictions on combinatorial decisions, while repeated optimization solves make training costly. The paper combines contrastive surrogate losses with a solver-agnostic solution cache. It reports similar-quality solutions with drastically reduced solution times.

  • Problem

    Prediction models trained to minimize prediction error can yield suboptimal decisions, while regret is non-continuous and repeated optimization solves make decision-focused training difficult.

    Source: §1 · p. 1, §3 · p. 2

  • Method

    The paper derives contrastive surrogate losses by treating non-optimal solutions as negative examples and uses a solution cache as an inner approximation of the feasible region.

    Source: §1 · p. 1, §5.1 · p. 4

  • Results

    The methods reach similar-quality solutions while reducing solution times drastically.

    Source: §7 · p. 7

  • Takeaways & Limitations

    Sampling new cache solutions at 5% reduces computational time without a deleterious impact on test regret in Energy-3.

    Source: §6.2 · p. 6

    The setup assumes access to correlated features and a historic dataset of feature-cost pairs.

    Source: §3 · p. 2

Abstract

from arXiv · show

Many decision-making processes involve solving a combinatorial optimization problem with uncertain input that can be estimated from historic data. Recently, problems in this class have been successfully addressed via end-to-end learning approaches, which rely on solving one optimization problem for each training instance at every epoch. In this context, we provide two distinct contributions. First, we use a Noise Contrastive approach to motivate a family of surrogate loss functions, based on viewing non-optimal solutions as negative examples. Second, we address a major bottleneck of all predict-and-optimize approaches, i.e. the need to frequently recompute optimal solutions at training time. This is done via a solver-agnostic solution caching scheme, and by replacing optimization calls with a lookup in the solution cache. The method is formally based on an inner approximation of the feasible space and, combined with a cache lookup strategy, provides a controllable trade-off between training time and accuracy of the loss approximation. We empirically show that even a very slow growth rate is enough to match the quality of state-of-the-art methods, at a fraction of the computational cost.

1 Introduction

Predict-then-optimize estimates uncertain inputs before solving, but prediction-focused training can yield suboptimal decisions and repeated NP-hard solves hinder scalability. The paper introduces contrastive losses and solution caching to address these challenges.

1 Introduction

  • Prediction models trained only to minimize prediction errors can produce suboptimal downstream decisions, motivating decision-focused training [Elmachtoub and Grigas, 2021; Wilder et al., 2019; Demirovi´c et al., 2019a].Predict-then-optimize first estimates uncertain parameters and then solves using those estimates.Source: §1 · p. 1
  • Repeatedly solving and differentiating an NP-hard problem for every training instance at every epoch creates major computational and scalability challenges.The paper identifies this repeated optimization as a bottleneck for predict-and-optimize training.Source: §1 · p. 1
  • Contrastive surrogate losses treat non-optimal solutions as negative examples, while a solution cache stores previous solutions as an inner approximation of the feasible-solution convex hull.The approach also adapts caching to solver-agnostic methods.Source: §1 · p. 1

2 Related Work

Prior decision-focused approaches address optimization and differentiation in different ways, but repeatedly solving optimization problems remains a scalability challenge. This paper positions contrastive losses with solution caching as an alternative that avoids repeated solves during training.

2 Related Work

  • Noise-contrastive estimation supports tractable parameter optimization for models requiring normalization over discrete assignments, and the paper uses it to derive tractable combinatorial-optimization formulations.The passage also situates NCE in probabilistic logic and neuro-symbolic reasoning.Source: §2 · p. 2
  • Prior work addresses differentiation through continuous relaxations, including quadratic regularization [Wilder et al., 2019], added cuts [Ferber et al., 2020], or a homogeneous self-dual formulation [Mandi and Guns, 2020].The discussion identifies numerical instability at the optimum when differentiating linear objectives.Source: §2 · p. 2
  • The SPO framework uses a convex surrogate subgradient for linear problems, while related solver-agnostic approaches compute gradients for black-box combinatorial solvers [Elmachtoub and Grigas, 2021; Poganˇci´c et al., 2020].The cited work also includes extensions for large-scale problems and decision trees [Mandi et al., 2020; Elmachtoub et al., 2020].Source: §2 · p. 2
  • Repeatedly solving optimization problems limits the scalability of existing approaches; contrastive losses with caching avoid those repeated training-time solves and extend to solver-agnostic methods.The authors state that the cached approach can also be applied to other solver-agnostic predict-and-optimize methods.Source: §2 · p. 2

3 Problem Setting

The problem setting learns predictions from features and historical cost data, with the aim of minimizing decision regret rather than prediction error alone. Standard gradient-based approaches repeatedly solve an optimization problem to obtain gradients, motivating alternative losses and caching.

3 Problem Setting

  • The model assumes access to correlated features and a historical dataset of feature-cost pairs, then fits a predictor for the unknown costs.The paper considers feasible solutions forming a discrete set specified implicitly through constraints.Source: §3 · p. 2
  • Regret compares the true cost of the solution chosen using predicted parameters with the true optimum, and is zero when the chosen solution is truly optimal or equivalent.The learning objective is to minimize expected regret over predictions.Source: §3 · p. 2
  • Because regret is non-continuous and involves differentiating through an argmin, the learning objective needs a differentiable, efficient loss that accounts for the objective and solution structure.The stated target is minimizing expected regret of the resulting predictions.Source: §3 · p. 2

3.1 Gradient-Descent Decision-Focused Learning

  • Standard gradient descent computes predictions, calls a solver for each instance and epoch, and updates model weights by backpropagation.The procedure may transform predictions before the solver call.Source: §3.1 · pp. 2–3
  • Some approaches differentiate continuous relaxations with quadratic or log-barrier task losses, while solver-agnostic methods such as SPO+ and Blackbox define subgradients using solver solutions.These approaches still require repeated optimization solves; the proposed contrastive losses are closed-form differentiable and avoid solving for every instance.Source: §3.1 · p. 3

4 A Contrastive Loss for Predict-and-Optimize

The section defines a distribution over feasible assignments whose most probable solution matches the optimization solution under predicted costs. It develops contrastive losses that avoid computing the intractable partition function, including a variant designed to prevent null-cost predictions.

4 A Contrastive Loss for Predict-and-Optimize

  • The proposed distribution makes the optimization solution under predicted costs its most probable assignment, framing learning as maximizing the likelihood of the true-cost optimum.Computing the partition function requires iterating over all feasible solutions, which is intractable for most combinatorial optimization problems.Source: §4 · p. 3

4.1 Noise-Contrastive Estimation

  • Noise-contrastive estimation avoids direct evaluation of the partition function by contrasting the target optimum with feasible non-optimal solutions used as negative samples.The loss treats the target and negative samples as constants during differentiation, yielding a subgradient.Source: §4.1 · p. 3

4.2 MAP Estimation

  • MAP estimation is a self-contrastive special case that uses one current-model maximum a posteriori assignment as its sample.The MAP assignment is the most probable solution under the current model.Source: §4.2 · pp. 3–4

4.3 Better Handling of Linear Cost Functions

  • The unmodified linear-cost loss can be minimized by predicting null costs, so the proposed variant adds a constant that preserves optimal solutions and regularizes predictions toward true costs.With the modification, the loss cannot be minimized by a null cost vector; minimizing it requires matching predicted and true costs or recovering the true-cost optimum.Source: §4.3 · p. 4

5 Negative Samples and Inner-approximations

The method reuses feasible solutions found during training as negative samples and as an inner approximation of the feasible space. A sampling probability controls the trade-off between solver use and cache-based lookup.

5.1 Negative Sample Selection

  • The cache grows by storing feasible solutions found by solver calls, and those cached solutions serve as negative samples without requiring multiple new feasible solutions per iteration.The cache is initialized with known optimal solutions; a new solver result is added only if it is not already present.Source: §5.1 · p. 4, §5.2 · pp. 4–5
  • A subset cache forms an inner approximation of the feasible space, unlike continuous relaxation, which gives an outer approximation.As the cache grows, its approximation can tighten; optimizing over the cached list requires only a linear-time argmin.Source: §5.1 · p. 4, §5.2 · p. 4

5.2 Gradient-descent with Inner Approximation

  • With probability psolve the algorithm calls the solver; otherwise it selects the cache argmin, trading computation time against approximation quality.This caching approach also applies to solver-based methods including SPO+, black-box solver differentiation, and the paper's contrastive losses.Source: §5.2 · p. 5

6 Empirical Evaluation

The evaluation compares contrastive losses and cached solver-based methods across knapsack, energy-cost scheduling, and diverse bipartite matching. Results show task-dependent regret rankings, while sampling solutions into the cache reduces training time without a reported loss in regret quality.

6.1 Experimental Settings

  • The experiments cover three NP-hard problems: knapsack, energy-cost-aware scheduling, and diverse bipartite matching, with multiple task instances.The matching task predicts edges in a citation-network graph and optimizes a maximum matching under diversity constraints.Source: §6 · p. 5, §6.1 · pp. 5–6

6.2 Results

  • LMAP (ĉ −c) performs best among contrastive loss variants for knapsack and scheduling, whereas LNCE performs slightly better than LMAP for matching.For knapsack and scheduling, the linear objective loss yields a significant gain with LMAP but no significant advantage with LNCE.Source: §6.2 · p. 6
  • Computing new cache solutions only 5% of the time significantly reduces training time without a deleterious impact on test regret in Energy-3.The authors conclude that sampling new solutions is an effective way to retain solution quality without a high computational burden.Source: §6.2 · p. 6, Figure 2 · p. 6
  • With psolve = 5%, caching SPO+ and Blackbox drastically reduces training times without significant impact on regret.The evaluation applies the inner-approximation cache to both solver-agnostic methods.Source: §6.2 · p. 6
  • Across Knapsack-120, Energy-3, and Matching-25, regret and runtime trade-offs vary: caching is competitive on the first two, while contrastive methods offer a middle ground on matching.Blackbox and Interior perform best in Knapsack-120 regret; SPO-caching and Blackbox-caching are comparable to state of the art on Energy-3; QPTL has the best but slowest Matching-25 result.Source: Figure 3 · p. 6, §6.2 · p. 7

7 Concluding Remarks

The paper presents contrastive decision-focused losses and a solution cache that acts as an inner approximation of the feasible region. It reports that caching can reduce solution times while maintaining similar solution quality.

7 Concluding Remarks

  • The methodology combines a noise-contrastive family of loss functions with a solution cache representing an inner approximation of the feasible region.The caching concept is also adapted to Blackbox and SPO+ to improve their efficiency.Source: §7 · p. 7
  • The two contributions allow solution times to be reduced drastically while reaching similar-quality solutions.The conclusion characterizes the outcome as improved efficiency without sacrificing comparable solution quality.Source: §7 · p. 7

A Predictive models

  • Knapsack and scheduling use a single-layer linear regressor trained with mean squared error, while matching uses a two-layer perceptron trained with cross entropy.The matching model has a 200-unit ReLU hidden layer and sigmoid output; all predictive models use ADAM.Source: A Predictive models · p. 9

C Problem Specification

The appendix specifies formulations for the knapsack and energy-cost-aware scheduling problems. Both use binary decision variables, with objectives and constraints reflecting their respective resource and timing settings.

C.1 Knapsack problem

  • The knapsack formulation maximizes revenue from purchasing electricity across 48 half-hour slots, subject to a fixed budget constraint.Each binary variable indicates whether a slot is purchased; slot weights represent fees.Source: §C.1 · p. 9

C.2 Energy-cost Aware Scheduling

  • The scheduling formulation minimizes total energy cost by assigning tasks to machines and start times across 48 equal-length periods.Each task has duration, start and end bounds, power usage, and resource requirements; machine resource capacities constrain schedules.Source: §C.2 · p. 9
  • Scheduling constraints require each task to be assigned once, respect its earliest start and latest end, and satisfy machine resource requirements.The formulation represents task starts with binary variables indexed by task, machine, and time.Source: §C.2 · p. 9

C.3 Diverse Bipartite Matching

The matching problem predicts links between two sets of scientific publications and seeks a high-reward matching subject to diversity constraints. Experiments vary the diversity settings across three named instances.

C.3 Diverse Bipartite Matching

  • The problem matches nodes across two sets of 50 publications, maximizing predicted link rewards while limiting each node to at most one match and enforcing similarity and diversity constraints.The reward matrix encodes predicted link likelihoods, and the formulation specifies rates for same-field and unrelated pairs.Source: §C.3 · p. 9
  • Experiments consider three variations of the matching problem, named Matching-10, Matching-25, and Matching-50, with p = q set to 10%, 25%, and 5%, respectively.Source: §C.3 · p. 9

D Hyperparameter Details

This appendix section collects regret tables for state-of-the-art methods and loss variants, caching runtimes, and hyperparameter choices across three problem settings.

D Hyperparameter Details

Loading 2011.05354v2…