Research map / Learning theory and algorithms / Combinatorial and search optimization
ACM-MILP: Adaptive Constraint Modification via Grouping and Selection for Hardness-Preserving MILP Instance Generation
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 ACM-MILP, a VAE-based MILP instance generator that groups strongly related constraints via Louvain community detection and selects low-probability (instance-specific) communities to modify, preserving computational hardness.
Problem
Generating realistic MILP instances when real data is scarce; existing learning-based generators (G2MILP) randomly modify single constraints, which breaks constraint interrelations and alters hardness and feasibility.
Approach
Group constraints into communities with Louvain on the bipartite graph, then use VAE latent Gaussian probabilities to select the least generic communities for collective replacement, so instance-specific constraints are modified together while generic structure is kept.
Key results
- On SC, ACM-MILP (η=0.1) solving time error 0.4% vs G2MILP 6.0% relative to training set (Table 2).
- On CA, ACM-MILP branching-node error at η=0.05 is 13.8% vs G2MILP 69.1% (Table 3).
- In SMAC3 tuning with 20 training instances, ACM-MILP-generated instances give the best tuned solving time on SC (3.804s) and CA (0.871s) versus training set tuning (3.852s, 1.336s).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ACM-MILP instead of G2MILP | MILP instance generation · MIS | solving-time relative error to training set: 15.6% -> 8.3% | Helped |
| Use ACM-MILP instead of G2MILP | MILP instance generation · SC | solving-time relative error to training set: 1.3% -> 0.6% | Helped |
| Use ACM-MILP instead of G2MILP | MILP instance generation · CA | solving-time relative error to training set: 57.8% -> 6.8% | Helped |
| Use ACM-MILP instead of G2MILP | MILP instance generation · MIS | branching-node relative error to training set: 43.9% -> 11.1% | Helped |
| Use ACM-MILP instead of G2MILP | MILP instance generation · SC | branching-node relative error to training set: 1.5% -> 0.5% | Helped |
| Use ACM-MILP instead of G2MILP | MILP instance generation · CA | branching-node relative error to training set: 69.1% -> 13.8% | Helped |
| Tune Gurobi using ACM-MILP-generated instances instead of using the default configuration | Gurobi · MIS test set | solving time (second): 0.458±0.007 -> 0.460±0.008 | No clear effect |
| Tune Gurobi using ACM-MILP-generated instances instead of using the default configuration | Gurobi · SC test set | solving time (second): 4.222±0.044 -> 3.804±0.019 | Helped |
| Tune Gurobi using ACM-MILP-generated instances instead of using the default configuration | Gurobi · CA test set | solving time (second): 0.926±0.004 -> 0.871±0.004 | Helped |
| Add constraint grouping to ACM-MILP rather than modifying one constraint at a time (ablation) | ACM-MILP · MIS | solving-time relative error to training set: 24.1% -> 17.1% | Helped |
| Add adaptive constraint selection rather than selecting communities randomly (ablation) | ACM-MILP · MIS | solving-time relative error to training set: 20.3% -> 17.1% | Helped |
| Add constraint grouping to ACM-MILP rather than modifying one constraint at a time (ablation) | ACM-MILP · SC | solving-time relative error to training set: 4.8% -> 0.4% | Helped |
Surprising findings
- Bowly-generated instances show zero branching nodes on all datasets, indicating trivially easy instances despite statistical matching.
- Random single-constraint modification at η=0.2 on MIS increases branching nodes by over 16000%, showing how fragile unstructured modifications are.
Limitations
- Statistical distribution similarity is comparable to or lower than G2MILP on MIS and CA, so gains are concentrated in hardness rather than graph statistics.
- Evaluated only on three synthetic MILP datasets with a single solver (Gurobi).
Experimental setup
Datasets: Maximum Independent Set (synthetic) Set Covering (synthetic) Combinatorial Auction (synthetic)
Benchmarks: MIS SC CA
Metrics: JS-divergence-based graph statistics similarity Gurobi solving time relative error Gurobi branching node relative error solving-time correlation across hyperparameter configs SMAC3 tuned solving time
Baselines: Bowly G2MILP Random
Builds on: G2MILP VAE Louvain
Closest papers by meaning
- MILP-StuDio: MILP Instance Generation via Block Structure Decomposition (NeurIPS 2024 · similarity 0.91)
- 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.87)
- Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming (ICLR 2025 · similarity 0.86)
- Towards Foundation Models for Mixed Integer Linear Programming (ICLR 2025 · similarity 0.86)
- Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters (ICML 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.