End-to-End Constrained Optimization Learning: A Survey

In plain words

Many real tasks, such as routing vehicles, scheduling power plants or allocating supplies, are optimization problems: pick the best choice among many, while obeying rules. Classical solvers handle these well, but they can be slow when the same kind of problem keeps coming back, or when the problem's numbers come from data.

This review looks at two ways machine learning and solvers meet. In the first, a model learns to produce good answers to a known kind of problem, so the solver is no longer needed at run time. In the second, a model predicts the numbers that feed a solver, and it is trained on how good the solver's decision turns out to be. The authors say that the first group has already been surveyed but the end-to-end methods lack a critical overview, and that the second is an emerging area that needs shared benchmarks. They end with open questions.

TL;DR

• A survey of how neural models and constrained optimization solvers are combined end to end.
• It separates predicting solutions to fixed problems (with constraints, or on graphs) from predict-and-optimize, where a solver is part of training.
• It reports no experiments of its own and no numbers; quantitative claims come from the works it cites.
• Open problems: constraint satisfaction at prediction time, solver runtime in the loop, limited problem types, and missing benchmarks.

Problem

Constrained optimization (CO) drives transportation, supply chains, energy, scheduling and resource allocation §1. Many CO problems are NP-hard, so solving them exactly can take too long when they recur, must run in real time, or depend on empirical data §1. Machine learning is a natural candidate to help, but the survey notes that the end-to-end branch of this work lacked a cohesive and critical analysis §1. The survey restricts itself mainly to problems with linear constraints and a linear or quadratic objective, with continuous or integer variables §2.

Method

The survey is a taxonomy, not a method. Its top-level split §4 fig. 1:

1. ML-augmented CO §5. A learned model helps a solver make its own decisions, for example which branching variable to pick in branch-and-bound, when to apply a primal heuristic, or which constraints to keep. The solver stays in charge of the solution.
2. End-to-end CO learning (E2E-COL) §4. A model is trained to produce solutions or decisions directly. It has two branches:
   • Predicting CO solutions §6. The model maps a problem instance to a complete solution, with no solver at inference time.
     • Learning with constraints §6.1: the model is trained with constraint information, either through Lagrangian duality or by adjusting target solutions toward feasibility with an external solver.
     • Learning solutions on graphs §6.2: the solution is a combinatorial structure, such as a permutation, a tour or a set of nodes. It is trained either with labelled solutions §6.2.1 or with reinforcement learning §6.2.2, using the problem's own objective as the reward signal.
   • Predict-and-optimize §7. A partly specified optimization problem is completed by parameters predicted from data. The problem is a layer of the network, and training minimises the quality of its decisions, usually as regret. Section 7 groups the methods by problem class: quadratic §7.1, linear §7.2 and combinatorial §7.3.

Section 3 reviews the building blocks the surveyed methods use: feed-forward networks, sequence models with attention and pointer networks, reinforcement learning, and graph neural networks written as a fixed-point mapping §3. It gives the equations for these blocks but no implementation details.

The core training problem of predict-and-optimize is a parameterised optimization problem, whose objective and feasible set depend on a parameter vector. The learner is trained so that the solution matches a target solution or so that the objective is good, which the survey calls regret §7. Regret is the gap between the objective achieved with the predicted parameters and the objective achieved with the true ones §7. The base form of the constrained problem is the one in §2 eq. 1.

# Predict-and-optimize training step (generic)  [§7] [fig. 2]
# Input:  features (B, d); true parameters (B, n)
# Output: scalar training loss

def training_step(features, true_parameters):
    # 1. Predict the unspecified parameters from data  [§7]
    predicted_parameters = model(features)          # (B, n)

    # 2. Solve the decision problem for each sample  [§7]
    predicted_solutions = solve_argmin(predicted_parameters)

    # 3. Compare with the solution from the true parameters  [§7]
    target_solutions = solve_argmin(true_parameters)
    loss = regret_or_solution_loss(
        predicted_solutions, target_solutions, predicted_parameters
    )

    # 4. Backpropagate through the solver: differentiate it or use a
    # surrogate, as in [§7.1] [§7.2] [§7.3]
    loss.backward()
    return loss

The pseudocode is a summary in our words. The survey does not give this code.

Hyperparameters

No experiments are reported, so no hyperparameters are stated. The survey gives no learning rates, batch sizes, network sizes, regularization weights or solver settings §1–§8. Values that the surveyed methods need, such as the size of the quadratic regularizer in §7.2 or the barrier weight in §7.2, are not stated in the survey.

Results

This survey has no experiments of its own. It reports the cited works' claims in words and gives no numbers, so every entry below is "not stated" in this card. All claims are author-reported in the cited papers.

The survey reports no benchmark comparison across predict-and-optimize methods. It cites one study that compared two approaches on knapsack and reached no firm conclusion §8.

Paper vs code

No official code. The paper and its LaTeX source link no repository or project page. Two GitHub repository searches (for the survey's title terms and for "predict-and-optimize constrained") returned no repository by the authors. The survey is a review, so there is no implementation of its own to compare with.

Pitfalls

• No numbers at all. Words such as "competitive", "stronger" and "outperform" describe the cited works only. Do not read them as measured gains; check the cited paper before implementing any method.
• Predict-and-optimize needs a usable gradient through the solver. The argmin of a discrete problem is piecewise constant in its parameters, so its gradient is not useful §7. The methods in §7 either differentiate a smoothed or continuous version of the problem, or replace the gradient with a surrogate or a perturbation. The survey does not say which choice works best.
• Regularizer and barrier weights are not stated. The LP method adds a small quadratic term §7.2 and the interior point method adds a log-barrier §7.2. Neither gives a value, and the survey does not discuss how to choose one. Both change the problem being solved, so their values matter.
• Uniqueness is assumed. The survey notes that predict-and-optimize treats the solution as a function of the parameters, and that non-unique optima are typically not considered §7.
• Solver calls per step. Methods that put a MILP or a black-box solver in the training loop must solve each instance in every forward pass §7.3. The survey gives no figures for this cost.
• Feasibility is not guaranteed. The survey states that current prediction methods cannot reliably guarantee the constraints hold on their outputs §8. Plan a projection or repair step if feasibility is required.
• Scope. The survey mainly covers linear constraints and linear or quadratic objectives §2. It notes that most reported experiments use linear programs §8, so claims for other problem classes rest on few sources.
• Source notes. The LaTeX source contains several disabled blocks, including a comparison table of predict-and-optimize frameworks and figures for ML-augmented CO and for end-to-end learning. The compiled paper does not show them, so this card does not use them.

Lineage

• Builds on: classical solver theory for linear, quadratic and mixed-integer programs, and the sequence and graph neural network architectures it reviews §2 §3.
• Surveyed predecessors and related reviews: the authors cite earlier surveys of ML-augmented CO §1 §5; they position their work as the review of the end-to-end branch.
• Superseded by: not stated.