Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning Valid Dual Bounds in Constraint Programming: Boosted Lagrangian Decomposition with Self-Supervised Learning
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 Lagrangian multipliers with a GNN via self-supervised training through differentiable LD dual bounds, replacing or bootstrapping sub-gradient optimization in CP branch-and-bound for MKP and shift scheduling.
Problem
Lagrangian decomposition gives valid dual bounds in constraint programming, but sub-gradient optimization of multipliers at every search node is computationally expensive, limiting practicality.
Approach
A graph neural network (ResGatedConv-based) directly predicts Lagrangian multipliers for a COP instance, trained self-supervisedly by minimizing the LD dual bound with a locally valid gradient; validity holds regardless of model accuracy.
Key results
- On MKP with 100 items, CP+Learning(root)+SG solves 49/50 instances vs 41/50 for CP+SG, with average time 1.1K s vs 2.4K s.
- On MKP with 50 items, CP+Learning(all) reduces average time from 158 s (CP+SG) to 36 s.
- On SSP 10 symbols/80 states, CP+Learning(all) solves 20/50 vs 13/50 for CP+SG, with time 1.3K s vs 3.3K s.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace sub-gradient optimization with learned bounds at every search node (ablation) | CP+Learning(all) · MKP, 50 items | time (sec.): 158 to 36 | Helped |
| Use learned bounds only at the root, then bootstrap sub-gradient optimization (ablation) | CP+SG · MKP, 100 items | instances solved: 41/50 -> 49/50 | Helped |
| Use learned bounds only at the root, then bootstrap sub-gradient optimization (ablation) | CP+SG · MKP, 100 items | time (sec.): 2.4K -> 1.1K | Helped |
| Use learned bounds only at the root, then bootstrap sub-gradient optimization (ablation) | CP+SG · MKP, 100 items | nodes: 4.1K -> 2.1K | Helped |
| Apply learned bounds at every node instead of using sub-gradient optimization (ablation) | CP+SG · MKP, 100 items | instances solved: 41/50 -> 25/50 | Hurt |
| Apply learned bounds at every node instead of using sub-gradient optimization (ablation) | CP+SG · SSP, 10 symbols and 20 states | instances solved: 28/50 -> 24/50 | Hurt |
| Apply learned bounds at every node instead of using sub-gradient optimization (ablation) | CP+SG · SSP, 10 symbols and 80 states | time (sec.): 3.3K -> 1.3K | Helped |
| Use learned bounds at the root to initialize sub-gradient optimization (ablation) | CP+SG · SSP, 10 symbols and 20 states | time (sec.): 473 -> 453 | Helped |
| Use learned bounds at the root to initialize sub-gradient optimization (ablation) | CP+SG · SSP, 20 symbols and 20 states | instances solved: 27/50 -> 22/50 | Hurt |
| Fine-tune the learned model on instances from a similar distribution (ablation) | CP+Learning(all) · MKP OOD benchmark, Weish instances | instances best: 25/30 | Helped |
| Fine-tune the learned model on instances from a similar distribution (ablation) | CP+Learning(root)+SG · MKP OOD benchmark, Weish instances | geometric mean time: 60 -> 44 | Helped |
| Use learned bounds at every node rather than root-only learning plus sub-gradient (ablation) | CP+Learning(all) vs CP+Learning(root)+SG · MKP, 100 items | instances solved: 25/50 vs 49/50 | Mixed |
Surprising findings
- Learning alone (without sub-gradient) produces weaker bounds and larger search trees than sub-gradient, yet still reduces execution time by skipping sub-gradient iterations.
- Without fine-tuning, the learned approach performs worse than the baseline on out-of-distribution Weish instances.
Limitations
- Learning alone gives weaker bounds and more search nodes than sub-gradient optimization, and fails to help on the hardest configurations.
- Out-of-distribution performance without fine-tuning is worse than the baseline; learned bounds lack guarantees in tightness, though remain valid.
- Evaluated only on two synthetic combinatorial problems with a specific CP solver (Gecode).
Experimental setup
Datasets: synthetic MKP instances (Pisinger protocol) synthetic SSP instances Weish MKP benchmark (fine-tuning/OOD)
Benchmarks: MKP 30/50/100 items (synthetic) SSP 10/20 symbols and 20/80 states (synthetic) Weish MKP instances (fine-tuning)
Metrics: number of instances solved within 2-hour timeout execution time (seconds) number of nodes explored dual bound gap
Baselines: CP CP+SG
Builds on: Lagrangian decomposition sub-gradient optimization ResGatedConv Lagrangian relaxation in CP
Closest papers by meaning
- Predicting Lagrangian Multipliers for Mixed Integer Linear Programs (ICML 2024 · similarity 0.90)
- Near-Optimal Solutions of Constrained Learning Problems (ICLR 2024 · similarity 0.87)
- Constrained Bi-Level Optimization: Proximal Lagrangian Value Function Approach and Hessian-free Algorithm (ICLR 2024 · similarity 0.86)
- Learn2Aggregate: Supervised Generation of Chvatal-Gomory Cuts Using Graph Neural Networks (AAAI 2025 · similarity 0.86)
- Geometric Algorithms for Neural Combinatorial Optimization with Constraints (NeurIPS 2025 · similarity 0.86)
- Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints (ICML 2025 · similarity 0.85)
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.