Research map / Image generation / Autoregressive and latent generation
MILP-FBGen: LP/MILP Instance Generation with Feasibility/Boundedness
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.
Proposes MILP-FBGen, a diffusion-based generator of LP/MILP instances that rewrites constraint/variable vectors of the incidence matrix and samples b and c so generated instances are provably feasible and bounded.
Problem
LP/MILP instance scarcity for ML methods; existing generators either fail to keep generated instances feasible and bounded or drift from the original data distribution in structure and hardness.
Approach
A diffusion model regenerates selected constraint or variable vectors of the incidence matrix (structure-preserving generation), then right-hand side b and objective c are sampled within bounds derived from known feasible primal and dual solutions, which guarantees feasibility and boundedness by construction.
Key results
- MILP-FBGen achieves 100% feasibility on all datasets and replacement ratios, while G2MILP's feasibility falls to 16% on WA and 81.6% on Anonymous.
- On MIRP with initial basis prediction (1:1 augmentation), MILP-FBGen reduces HiGHS solving time from 125.57s baseline to 86.07s (31.46% gain), exceeding G2MILP (21.70%) and DIG-MILP (10.78%) on PDS and MIRP comparisons.
- In hyperparameter tuning, MILP-FBGen-searched configurations reduce PDS solving time by 19.41% versus the baseline, while DIG-MILP degrades MIRP performance by -246.22%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| generate instances with MILP-FBGen rather than G2MILP | LP/MILP instance generation · SC, MIK, MIRP, PDS, Anonymous, and WA | feasibility ratio: 100% | Helped |
| augment MIRP training data with MILP-FBGen instances | initial basis prediction · MIRP | TimeH(s): 125.57 -> 86.07 | Helped |
| augment PDS training data with MILP-FBGen instances | initial basis prediction · PDS | TimeH(s): 78.21 -> 75.70 | Helped |
| augment WA training data with MILP-FBGen instances | predict and search · WA | absolute primal gap: 0.16 -> 0.08 | Helped |
| augment Anonymous training data with MILP-FBGen instances | predict and search · Anonymous | absolute primal gap: 358.31 -> 355.16 | Helped |
| augment MIRP training data with MILP-FBGen instances | hyperparameter tuning · MIRP | TimeH(s): 29.25 -> 28.04 | Helped |
| augment PDS training data with MILP-FBGen instances | hyperparameter tuning · PDS | TimeH(s): 36.68 -> 29.56 | Helped |
| use task-oriented rather than random constraint selection (ablation) | MILP-FBGen · MIRP initial basis prediction | TimeH(s): 86.07 -> 83.41 | Helped |
| use task-oriented rather than random constraint selection (ablation) | MILP-FBGen · PDS initial basis prediction | TimeH(s): 75.70 -> 73.55 | Helped |
| remove the Eq. 8 sampling bounds when generating b and c (ablation) | MILP-FBGen · MIK | Gap(%): 6.47 -> 20.12 | Hurt |
| replace diffusion with VAE in the structure-preserving generation module (ablation) | MILP-FBGen · MIK | Gap(%): 6.47 -> 12.35 | Hurt |
| increase the augmented-data amount from 1:1 to 1:3 | MILP-FBGen · MIRP initial basis prediction | TimeH(s): 86.07 -> 92.07 | Hurt |
Surprising findings
- DIG-MILP's generated instances substantially degrade hyperparameter tuning performance on MIRP, indicating that feasibility guarantees alone do not ensure useful training data.
- Bowly generated instances are far too easy, with solving times around 0.014s versus 0.790s for the SC training set.
Limitations
- Reverse diffusion sampling is time-consuming, as acknowledged in the conclusion.
- Task-oriented selection is limited to node-level regression or classification tasks.
- Instance-level tasks such as hyperparameter tuning rely on the dataset-level procedure rather than the node-level selection strategy.
Experimental setup
Datasets: Set Covering Mixed-integer Knapsack MIRP PDS Workload Apportionment Anonymous
Benchmarks: Set Covering Mixed-integer Knapsack MIRP PDS Workload Apportionment Anonymous
Metrics: solving time solving time gap feasibility ratio structural similarity score primal gap gain over baseline
Baselines: Bowly G2MILP DIG-MILP
Builds on: G2MILP DIG-MILP Ecole denoising diffusion probabilistic models Bowly instance generator
Closest papers by meaning
- MILP-StuDio: MILP Instance Generation via Block Structure Decomposition (NeurIPS 2024 · similarity 0.88)
- ACM-MILP: Adaptive Constraint Modification via Grouping and Selection for Hardness-Preserving MILP Instance Generation (ICML 2024 · similarity 0.86)
- Towards Foundation Models for Mixed Integer Linear Programming (ICLR 2025 · similarity 0.84)
- RoME: Domain-Robust Mixture-of-Experts for MILP Solution Prediction across Domains (NeurIPS 2025 · similarity 0.84)
- CAMBranch: Contrastive Learning with Augmented MILPs for Branching (ICLR 2024 · similarity 0.84)
- Generative Marginalization Models (ICML 2024 · similarity 0.83)
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.