Research map / Learning theory and algorithms / Combinatorial and search optimization
Neur2BiLO: Neural Bilevel Optimization
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.
Neur2BiLO embeds a neural network approximation of the leader's or follower's value function, trained by supervised regression, into a MIP to quickly heuristically solve mixed-integer non-linear bilevel problems.
Problem
Mixed-integer non-linear bilevel optimization is hard to solve exactly and scales poorly; specialized methods do not generalize across problem classes, especially in data-driven settings where similar instances are solved repeatedly.
Approach
Train a ReLU neural network (MILP-representable) to predict either the leader's objective or the follower's optimal value from instance features and leader decisions, then optimize the leader's decision by solving a single-level MIP with that surrogate, adding a slack variable and follower constraints (value function reformulation) for bilevel feasibility.
Key results
- On KIP with n<=30, NN^l and NN^u take about 1% of B&C's time (avg 1.06s vs 95.43s) with MRE 1.86% vs 0.00% for B&C.
- On KIP with n=100, NN^u achieves MRE 0.66% in about 27s, versus 7.64% MRE for B&C at a 3,600s limit.
- On DNDP, NN^u reaches MRE 4.58% in 0.02s, while NN^l reaches MRE 0.64% in 3.46s, versus MKKT MRE-30 of 0.40%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use NN^l instead of B&C | KIP, n≤30 · KIP, n≤30 | Time: 1.06 vs 95.43 | Helped |
| Use NN^l instead of B&C | KIP, n=100 · KIP, n=100 | MRE: 0.66 vs 7.64 | Helped |
| Use NN^u instead of B&C | CNP · CNP | Time: 0.43 vs 2,941.79 | Helped |
| Use NN^u instead of NN^l | DNDP · DNDP | MRE: 0.64 vs 4.58 | Hurt |
| Use NN^u instead of NN^l | DNDP · DNDP | Time: 3.46 vs 0.02 | Helped |
| Lower the slack penalty from λ=1 to λ=0.1 (ablation) | NN^l and GBT^l on DNDP · DNDP | MRE | Helped |
Surprising findings
- On KIP with n<=30 the exact B&C baseline attains 0.00% error, while the learned approximations are not optimal, yet are around 100x faster.
- On DNDP, NN^u is much faster than any other method but has noticeably worse solution quality than NN^l.
Limitations
- Heuristic: no optimality guarantee; the upper-level approximation may return infeasible solutions when only follower feasibility is assumed.
- Performance depends on regression accuracy; the absolute-error guarantee holds only for interdiction-type problems with identical leader/follower objectives.
- No benchmark with coupling constraints in the leader problem was evaluated.
Experimental setup
Datasets: Knapsack interdiction instances from prior work (180 instances) Generated KIP instances with n=100 (100 per size) CNP instances sampled via prior procedure DRP most challenging instances from prior work DNDP Sioux Falls instances
Benchmarks: Knapsack interdiction (KIP) Critical node problem (CNP) Donor-recipient problem (DRP) Discrete network design problem (DNDP)
Metrics: mean relative error solving time
Baselines: B&C (branch-and-cut) G-VFA MKKT B&C+ ISNN
Builds on: value function reformulation branch-and-cut for bilevel integer programs DeepSets ISNN (input-supermodular neural networks)
Closest papers by meaning
- Learning to Solve Bilevel Programs with Binary Tender (ICLR 2024 · similarity 0.86)
- Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis (ICLR 2025 · similarity 0.86)
- Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis (ICLR 2024 · similarity 0.86)
- TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization (ICML 2025 · similarity 0.85)
- BILBO: BILevel Bayesian Optimization (ICML 2025 · similarity 0.85)
- Generalized Smooth Bilevel Optimization with Nonconvex Lower-Level (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.