Research map / Learning theory and algorithms / Combinatorial and search optimization
MILP-StuDio: MILP Instance Generation via Block Structure Decomposition
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-StuDio, which decomposes MILP constraint coefficient matrices into block units and generates new instances via reduction, mix-up, and expansion operators to preserve feasibility and hardness.
Problem
Generating MILP instances that preserve mathematical properties (feasibility, computational hardness) is hard; existing generators such as G2MILP break block structures in constraint coefficient matrices, yielding trivial or infeasible instances.
Approach
Detect block structures in constraint coefficient matrices (via GCG structure detector), decompose instances into block units stored in a structure library, and generate new instances by removing, substituting, or appending block units so the block structure is preserved.
Key results
- On FA, MILP-StuDio (eta=0.01) achieves similarity 0.663 versus 0.358 for G2MILP, with 100% feasibility, whereas G2MILP gives 1.7% feasible instances.
- In predict-and-search, PS+MILP-StuDio attains the best gap on IP (0.13 vs 0.27 for Gurobi) and WA (0.03 vs 0.05), and the best FA solving time (7.07s vs 7.36s for Gurobi).
- Generation time for 1,000 WA instances is about 3x faster than G2MILP, and MILP-StuDio-generated data raises GNN branching accuracy on IP to 0.800 vs 0.640 for the baseline GNN.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Generate training instances with MILP-StuDio instead of G2MILP at η=0.01 | MILP instance generation · FA | graph similarity: 0.358 -> 0.663 | Helped |
| Generate training instances with MILP-StuDio instead of G2MILP at η=0.01 | MILP instance generation · IP | graph similarity: 0.717 -> 0.661 | Hurt |
| Generate training instances with MILP-StuDio instead of G2MILP at η=0.01 | MILP instance generation · WA | graph similarity: 0.854 -> 0.980 | Helped |
| Train PS with MILP-StuDio-generated instances (η=0.05) rather than the original training data alone | PS · CA | Time: 0.94 -> 0.78 | Helped |
| Train PS with MILP-StuDio-generated instances (η=0.05) rather than the original training data alone | PS · FA | Time: 7.19 -> 7.07 | Helped |
| Train PS with MILP-StuDio-generated instances (η=0.05) rather than the original training data alone | PS · IP | gap_abs: 0.24 -> 0.13 | Helped |
| Train PS with MILP-StuDio-generated instances (η=0.05) rather than the original training data alone | PS · WA | gap_abs: 0.25 -> 0.03 | Helped |
| Train the branching GNN with MILP-StuDio-generated instances (η=0.05) | GNN branching policy · FA | branching accuracy: 0.545 -> 0.605 | Helped |
| Train the branching GNN with MILP-StuDio-generated instances (η=0.01) | GNN branching policy · IP | branching accuracy: 0.640 -> 0.800 | Helped |
| Increase the modification ratio from η=0.01 to η=0.10 (ablation) | MILP-StuDio · CA | graph similarity: 0.997 -> 0.946 | Hurt |
| Increase the modification ratio from η=0.01 to η=0.10 (ablation) | MILP-StuDio · FA | graph similarity: 0.663 -> 0.618 | Hurt |
| Increase the modification ratio from η=0.01 to η=0.10 (ablation) | MILP-StuDio · IP | graph similarity: 0.661 -> 0.493 | Hurt |
Surprising findings
- Higher graph structural similarity does not necessarily correspond to better downstream benefit; reduction and expansion operators give lower similarity but comparable downstream performance.
- Bowly-generated FA instances are computationally trivial, so no branching samples could be collected from them.
Limitations
- Performance depends on the GCG structure detector; extremely complex structures are poorly detected.
- Method is designed for instances with block structures and relies on structure detection before generation.
Experimental setup
Datasets: combinatorial auctions (CA) capacitated facility location (FA) item placement (IP) workload appointment (WA)
Benchmarks: CA FA IP WA
Metrics: graph structural similarity (JS divergence based) average solving time feasible ratio objective value absolute primal gap branching imitation accuracy
Baselines: Bowly G2MILP Gurobi SCIP GNN
Builds on: G2MILP Predict-and-Search GNN branching policy Generic Column Generation (GCG) structure detector
Closest papers by meaning
- ACM-MILP: Adaptive Constraint Modification via Grouping and Selection for Hardness-Preserving MILP Instance Generation (ICML 2024 · similarity 0.91)
- MILP-FBGen: LP/MILP Instance Generation with Feasibility/Boundedness (ICML 2024 · similarity 0.88)
- Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction (AAAI 2025 · similarity 0.87)
- RoME: Domain-Robust Mixture-of-Experts for MILP Solution Prediction across Domains (NeurIPS 2025 · similarity 0.86)
- Towards Foundation Models for Mixed Integer Linear Programming (ICLR 2025 · similarity 0.86)
- Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming (ICLR 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.