Mixed-Integer Linear Programming (MILP) is a fundamental optimization paradigm in combinatorial optimization and has been widely applied across real-world domains. Due to its NP-hard nature, obtaining optimal solutions for large-scale or highly constrained MILP instances remains computationally prohibitive. Learning-based solution prediction has therefore emerged as a promising approach to provide high-quality variable assignments for solver acceleration. However, existing methods typically adopt a one-shot prediction paradigm that predicts the marginal probabilities of all variables simultaneously. As a result, the conditional dependencies among variables are only implicitly captured through message passing, with the burden of modeling the combinatorial structure falling entirely on the representational capacity of graph neural networks. To address this limitation, we propose the Structure-Aware Hierarchical Solution Prediction (SHSP) framework that replaces the parallel marginal decoding of one-shot methods with a novel hierarchical conditional decoding mechanism. Specifically, SHSP constructs a variable coupling graph from the constraint structure, decodes variables sequentially along a hierarchy of increasing coupling strength, and conditions each hierarchy on previously predicted assignments. To mitigate error accumulation during the decoding process, SHSP further incorporates a confidence-aware mask-and-repair mechanism to identify and correct unreliable intermediate predictions. We integrate SHSP with multiple learning-guided search methods and evaluate it on four standard MILP benchmarks. Experimental results demonstrate that SHSP significantly outperforms existing one-shot prediction baselines, achieving a 54% average reduction in solution gap.
SHSP/
├── Apollos/ # Apollo-style iterative inference
│ └── Apollo_shsp.py
├── ND/ # Neural Diving inference
│ └── ND_shsp.py
├── PaS/ # Predict-and-Search inference
│ └── PaS_shsp.py
├── batching/ # Coupling graph and VCS batch preparation
│ ├── coupling_graph.py
│ ├── COUPLING_GRAPH_README.md
│ └── prepare_hierarchical_batches_vcs.py
├── configs/ # Hydra training configs
│ ├── config.yaml
│ ├── base/default.yaml
│ └── model/shsp_gcn.yaml
├── data_modules/ # PyTorch Lightning data modules
├── model_modules/ # PyTorch Lightning SHSP-GCN module
├── networks/ # SHSP-GCN network definition
├── dataset/ # Generated training data
├── instances/ # Raw MILP instances
├── ckpts/ # Checkpoints used by inference
├── logs/ # Training and inference outputs
├── gurobi.py # Data generation from raw instances
├── helper.py # MILP-to-bipartite-graph utilities
└── train_unified.py # Training entry point
Python 3.12 is expected. The project includes pyproject.toml and uv.lock.
Using uv:
cd /path/to/SHSP
uv syncA valid Gurobi license is required.
The examples below use Set Cover (SC) as the problem name. BG denotes bipartite graph files generated from MILP instances.
The default training layout is:
dataset/
├── SC_train/
│ ├── BG/
│ │ └── instance_1.bg
│ ├── solution/
│ │ └── instance_1.sol
│ └── batches_vcs/
│ └── instance_1_batches_2_vcs_low.pt
└── SC_valid/
├── BG/
├── solution/
└── batches_vcs/
The default inference layout is:
instances/
└── SC_test/
├── instance_1.lp
└── instance_2.mps
The default checkpoint path for inference is:
ckpts/shsp/SC_shsp.ckpt
gurobi.py reads raw .lp / .mps instances, solves them with Gurobi, and writes:
BG/*.bg
solution/*.sol
logs/*.log
Default input/output paths:
instances/{problem}_train -> dataset/{problem}_train
instances/{problem}_valid -> dataset/{problem}_valid
Example:
cd /path/to/SHSP
python gurobi.py \
--problem SC \
--nWorkers 4 \
--maxTime 3600 \
--maxStoredSol 10 \
--train \
--validIf --train, --valid, and --test are all omitted, the script processes train and valid by default.
SHSP-GCN training requires precomputed VCS hierarchical batch assignments. The released default is:
n_batches = 2
method = low
This means variables are ordered by VCS from low to high and split into hierarchical batches (hierarchies).
Example:
cd /path/to/SHSP
python batching/prepare_hierarchical_batches_vcs.py \
--problem SC \
--n_batches 2 \
--method low \
--data_dir ./dataset \
--instance_dir ./instances \
--splits train validOutput files are written to:
dataset/SC_train/batches_vcs/
dataset/SC_valid/batches_vcs/
with names such as:
instance_1_batches_2_vcs_low.pt
The coupling-graph construction used by VCS is documented in batching/COUPLING_GRAPH_README.md.
Default training uses:
problem: SC
model.type: shsp_gcn
model.n_batches: 2
model.batch_method: vcs_low
training.epochs: 500
logging.use_wandb: false
Run training with defaults:
cd /path/to/SHSP
python train_unified.pyCommon overrides:
python train_unified.py \
problem=SC \
data_dir=./dataset \
model.n_batches=2 \
model.batch_method=vcs_low \
training.epochs=500 \
loss.weight_norm=100 \
gpu=0Training outputs are saved under:
logs/shsp/{problem}/{date}/{time}/
Checkpoints are saved under the run directory:
logs/shsp/{problem}/{date}/{time}/checkpoints/
The training checkpoint monitor is val/accuracy; the top checkpoints and last.ckpt are saved.
All inference scripts default to:
instances: ./instances/{problem}_test
checkpoint: ./ckpts/shsp/{problem}_shsp.ckpt
n_batches: 2
batch_method: vcs_low
The active fixing strategy follows the structure-aware variable fixing described in the paper. Instead of selecting variables only by prediction confidence, SHSP first keeps structurally influential variables according to Variable Coupling Strength (VCS), then applies confidence thresholds to decide which variables can be fixed. The selected variables are finally capped by the per-step fixing budgets used by the downstream solver.
Fixing-related parameters:
highvcs_filter_fixing = true
Enables the released structure-aware fixing rule. Candidate variables are first filtered by high VCS, so only strongly coupled variables are considered for fixing.
min_fixing_vcs_var = 0.5
Controls the high-VCS filter by selecting the VCS threshold position after sorting binary variables from high to low VCS. For example, 0.5 keeps variables whose VCS is at least the median-style threshold, while 0.6 roughly keeps the top 60% high-VCS variables. Ties at the threshold may make the selected set slightly larger.
highvcs_fix_one_threshold = 0.9
highvcs_fix_zero_threshold = 0.1
After the high-VCS filter, variables with predicted probability greater than or equal to highvcs_fix_one_threshold are candidates to be fixed to 1, while variables with predicted probability less than or equal to highvcs_fix_zero_threshold are candidates to be fixed to 0. The selected candidates are ranked by prediction probability and capped by the fixing budgets k_1 and k_0, which are upper bounds on the numbers of variables fixed to 1 and 0, respectively.
The budgets k_0, k_1, and the trust-region radius delta are internal inference hyperparameters.
cd /path/to/SHSP
python ND/ND_shsp.py \
-p SC \
-n 1 \
-g 0 \
--time_limit 1000Use --model_path ./ckpts/shsp/SC_shsp.ckpt to specify a checkpoint explicitly.
python PaS/PaS_shsp.py \
-p SC \
-n 1 \
-g 0 \
--time_limit 1000python Apollos/Apollo_shsp.py \
-p SC \
-n 1 \
-g 0Use --time_limits 100,100,100,100 to specify the time limit for each Apollo step explicitly.
Inference logs are written under:
logs/neural_diving_shsp/{problem}/{date}/{time}/
logs/predict_and_search_shsp/{problem}/{date}/{time}/
logs/apollo/{problem}/{date}/{time}/
Each inference run writes a compact test.log.
For Neural Diving and Predict-and-Search:
instance_name ObjVal coupling_graph_time solver_time
For Apollo:
instance_name step ObjVal coupling_graph_time solver_time
Per-instance Gurobi logs are stored under lp_logs/. Apollo also saves the updated .lp file after each step.
This project is built upon the following projects:
- Apollo-MILP — Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming (ICLR 2025).
- Predict-and-Search MILP Method — the Predict-and-Search_MILP_method on which Apollo-MILP is based.