Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning Generalized Linear Programming Value Functions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Learns the generalized LP value function (GVF) with an input-convex Dual-Stack neural network trained unsupervised via a dual-feasibility penalty, yielding a guaranteed under-approximation usable as a fast heuristic for two-stage MILPs.
Problem
Approximating the generalized LP value function, which gives an LP's optimal value as both objective and constraint bounds vary, in a way that is cheap to generate training data for and usable inside optimization (e.g., decomposition for two-stage MILPs).
Approach
A structural representation theorem writes the GVF as a max of bilinear terms of piecewise linear functions of the objective and of the bounds; this is encoded as a Dual-Stack Model (weight-sign constrained, convex in bounds) and trained unsupervised with a penalized dual-feasibility constraint, so no LP solves are needed for labels.
Key results
- On KG instances the Dual-Stack Model reached true relative error of 0.87-1.52% versus 1.09-4.64% for DenseNet, without requiring LP labels.
- The heuristic solves KG 750 UFL instances in 0.313 s on average, versus over 90 s for the full model MILP, with a negative gap to MILP (up to -55%) on KG 750.
- On Euclidean UFL instances the heuristic was worse than the full model solver, so gains were limited to large KG instances.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| train with the unsupervised Dual-Stack Model rather than DenseNet | GVF learning · KG 500, KG 750, and Euclidean 100/200/300 test sets | True Relative Error: 1.64 % -> 1.14 %; 4.64 % -> 0.87 %; 39.29 % -> 33.88 %; 43.12 % -> 33.78 %; 33.25 % -> 31.89 % | Helped |
| train with the unsupervised Dual-Stack Model rather than DenseNet | GVF learning · KG 250 test | True Relative Error: 1.09 % -> 1.52 % | Hurt |
| train with the unsupervised Dual-Stack Model rather than Random Forest | GVF learning · all Table 1 settings | True Relative Error: 6.05 % -> 1.52 %; 6.18 % -> 1.14 %; 6.25 % -> 0.87 %; 41.41 % -> 33.88 %; 37.22 % -> 33.78 %; 39.26 % -> 31.89 % | Helped |
| use the DSM heuristic instead of the full-model solver | UFL · KG 250/500/750 | Solve Time (s): 0.070 ± 0.001 vs 3.42 ± 0.31; 0.111 ± 0.008 vs 36.07 ± 1.52; 0.313 ± 0.004 vs > 90 | Helped |
| use the DSM heuristic instead of the full-model solver | UFL · Euclidean 100/200/300 | Gap to MILP (%): 23.32 ± 6.25; 43.59 ± 9.10; 47.98 ± 8.60 | Hurt |
| use the DSM heuristic instead of the full-model solver | UFL · KG 500/750 | Gap to MILP (%): -3.79 ± 1.05; -55.44 ± 1.34 | Helped |
| use adaptive rather than linear penalty updates (ablation) | Dual-Stack Model training · KG-sym 250 | true rel error: 5.32% -> 3.91% | Helped |
| use adaptive rather than linear penalty updates (ablation) | Dual-Stack Model training · Euclidean 100 | true rel error: 19.80% -> 23.23% | Hurt |
| change the upper bound used during training from 2.0 to 100.0 (ablation) | Dual-Stack Model training · KG-sym 250 | true rel error: 5.32% -> 2.73% | Helped |
| change the upper bound used during training from 2.0 to 100.0 (ablation) | Dual-Stack Model training · Euclidean 100 | true rel error: 19.80% -> 99.06% | Hurt |
Surprising findings
- The heuristic underperforms the full MILP on Euclidean instances, which the authors attribute to harder-to-learn GVFs.
- Test lower-bound satisfaction differs substantially from training lower-bound satisfaction, indicating weaker generalization of the under-approximation guarantee to unseen objectives.
Limitations
- Penalty-based training is occasionally unstable and sensitive to penalty update strategy.
- Lower-bound guarantee for unseen objectives is not ensured; test lower-bound satisfaction is much lower than training.
- Heuristic only applies to two-stage MILPs with continuous second-stage variables and is weaker on some instance classes.
Experimental setup
Datasets: UFLLIB Koerkel-Ghosh instances Euclidean uncapacitated facility location instances OR-Library capacitated facility location (cap61/cap62)
Benchmarks: UFL Euclidean instances UFL KG instances SCFL cap61/cap62
Metrics: true relative error lower bound percentage (constraints satisfied) solve time provable gap gap to MILP
Baselines: ReLU DenseNet Random Forest Regressor SCIP Benders heuristic
Builds on: Benders decomposition Blair-Jeroslow value function theory input-convex neural networks DenseNet
Closest papers by meaning
- Learning Initial Basis Selection for Linear Programming via Duality-Inspired Tripartite Graph Representation and Comprehensive Supervision (ICML 2025 · similarity 0.87)
- Generalization Guarantees for Learning Score-Based Branch-and-Cut Policies in Integer Programming (NeurIPS 2025 · similarity 0.87)
- Predicting Lagrangian Multipliers for Mixed Integer Linear Programs (ICML 2024 · similarity 0.86)
- Learning to Generate Projections for Reducing Dimensionality of Heterogeneous Linear Programming Problems (ICML 2025 · similarity 0.86)
- On the Power of Small-size Graph Neural Networks for Linear Programming (NeurIPS 2024 · similarity 0.86)
- Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction (AAAI 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.