Mixed-integer linear programs (MILP) model many real-world decision problems, motivating machine-learning methods that exploit recurring structure to accelerate MILP solving. MILPs can admit many equivalent formulations: integrality-preserving changes of variables and the addition of redundant constraints can alter their formulations while preserving the optimization problem. We leverage these reformulations as a source of self-supervision for learning general-purpose representations of MILP variables and constraints. We characterize the affine reformulations that are valid for every input instance, and distinguish re-descriptions, which leave variables unchanged, from substitutions, which transform them predictably. Building on equivariant self-supervised learning, we introduce ReMILP (reformulation-contrastive MILP representation learning), which jointly trains a graph neural network and a hypernetwork to predict how variable embeddings transform under changes of variables. Without solver-derived labels, ReMILP learns representations that exhibit the intended invariance and equivariance on unseen problem classes. Across binary solution, constraint activity and integrality gap prediction, these representations carry task-relevant information when frozen and provide a useful initialization for fine-tuning.
Figures & tables
Figure 1: ReMILP pre-training overview . (1) Independent re-descriptions ( Theorem 4.2 ) form two views of the same MILP instance M0 , with a substitution ( Theorem 4.1 ) applied to the second view Equation 10 . (2) A shared two-layer GAT encodes their bipartite graphs. (3) The hypernetwork uses local substitution parameters and the variable partner embedding to produce a linear operator predicting hi(M′) from hi(M) Equation 11 . (4) The pre-training contrastive loss makes this prediction the preferred match to hi(M′) over predictions from other descriptors and embeddings of other variables Equation 13 .
Invariance ↑
Equivariance ↑
Encoder
Top-1
MRR
Top-1
MRR
Random
0.289±0.009
0.375±0.011
0.091±0.011
0.121±0.013
FORGE †
0.120±0.040
0.171±0.049
0.017±0.003
0.026±0.004
ReMILP (ours)
0.383±0.093
0.454±0.089
0.081±0.014
0.105±0.016
ReMILP+hyper (ours)
–
–
0.162±0.005
0.276±0.004
Table 1: Invariance and equivariance properties. Nearest-neighbor retrieval after re-description (invariance) or substitution (equivariance) on D-MIPLIB. For equivariance, “+ hyper” uses the hypernetwork prediction. Other rows use the original embedding. Mean ± sd over 3 seeds.
Task
Type
ReMILP (ours)
FORGE †
Binary solution
ILP
0.887±0.016
0.918±0.007
MILP
0.688±0.050
0.755±0.012
Constraint activity
ILP
0.871±0.007
0.882±0.018
MILP
0.855±0.028
0.863±0.024
Table 2: Downstream node-level performance under frozen encoders . Test KL divergence normalized by the corresponding random encoder result for each instance family and aggregated using the geometric mean. Values below 1 indicate improvement over the random encoder ( ↓ ).
Figure 2: Fine-tuning on binary solution and constraint activity prediction. Test KL throughout fine-tuning, aggregated by geometric mean across the corresponding D-MIPLIB families and normalized by the final performance of the encoder trained from scratch (“Supervised”).
Figure 5
Appendix figures & tables10 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Fine-tuning ReMILP with and without substitutions on the node-level tasks, 20 000 steps. Each panel shows the geometric mean over the pairs of a group of the test KL at the checkpoint selected on validation, divided by the value the supervised model of the same seed reaches at the end of its budget. Shaded bands are one standard deviation over three seeds, and the horizontal line marks parity with the best supervised model.
Figure 5: Fine-tuning ReMILP with and without substitutions on the integrality gap: test MAE, mean and one standard deviation over three seeds, 100 000-step budget on the full training set.
Problem class
Abbreviation
Easy
Medium
Hard
Combinatorial Auctions
CA
✓
✓
Maximum Independent Set
IS
✓
✓
Set Covering
SC
✓
✓
✓
Minimum Vertex Cover
VC
✓
✓
✓
Generalized Independent Set Problem
GISP
✓
✓
✓
Capacitated Facility Location Problem
CFLP
✓
✓
Appendix
Table 4: Instance families used from Distributional MIPLIB.
Model
Hyperparameter
Search space
Selected
ReMILP
Temperature τ
[0.05,0.5] , log
0.090
Negatives of each type K
{7,15,31,63}
63
Fraction of transformed variables κ=∣I∣/n
{0.01,0.02,0.05}
0.05
Fraction of redundant constraints ρ=mm′−1
{0,0.05,0.1,0.2}
0.2
Constraints combined per redundant row
{2,3}
2
Bound bλ on λi,μi
[1.5,6] , log
4.01
Appendix
Table 5: Pre-training search space and selected values. Ranges marked log are sampled on a logarithmic scale.
Class
Difficulty
Random
ReMILP
FORGE †
IS
easy
0.588±0.000
0.588±0.000
0.588±0.000
medium
0.599±0.000
0.599±0.000
0.599±0.000
CA
easy
0.242±0.001
0.212±0.001
0.217±0.005
medium
0.243±0.001
0.210±0.001
0.216±0.005
SC
easy
0.057±0.000
0.044±0.002
0.047±0.002
medium
0.060±0.000
0.047±0.002
0.052±0.003
Appendix
Table 6: Binary solution prediction. Frozen encoders, test KL per instance family, mean ± one standard deviation over three seeds. A value is bold when it is not within one standard deviation of the runner up.
Class
Difficulty
Random
ReMILP
FORGE †
IS
easy
0.583±0.000
0.583±0.000
0.583±0.000
medium
0.595±0.000
0.595±0.000
0.595±0.000
CA
easy
0.384±0.004
0.312±0.002
0.318±0.008
medium
0.394±0.003
0.313±0.002
0.321±0.008
SC
easy
0.389±0.012
0.286±0.003
0.287±0.003
medium
0.322±0.008
0.227±0.004
0.229±0.005
Appendix
Table 7: Constraint activity prediction. Frozen encoders, test KL per instance family, mean ± one standard deviation over three seeds. Heads trained for 50 000 steps. The upper block holds the pairs with no continuous variables. A value is bold when not within one standard deviation of the runner up.
Figure 6: Fine-tuning on binary solution prediction. Part 1 of 2. Test KL of the checkpoint selected on validation, one panel per instance family, mean and one standard deviation over three seeds. Each panel carries its own vertical scale.
Figure 7: Fine-tuning on binary solution prediction. Part 2 of 2. Test KL of the checkpoint selected on validation, one panel per instance family, mean and one standard deviation over three seeds. Each panel carries its own vertical scale.
Figure 8: Fine-tuning on constraint activity prediction. Part 1 of 2. Test KL of the checkpoint selected on validation, one panel per instance family, mean and one standard deviation over three seeds. Each panel carries its own vertical scale.
Figure 9: Fine-tuning on constraint activity prediction. Part 2 of 2. Test KL of the checkpoint selected on validation, one panel per instance family, mean and one standard deviation over three seeds. Each panel carries its own vertical scale.