mlsanityData to 7 Oct 2026

Learning Backdoors for Mixed Integer Linear Programs with Contrastive Learning

arXiv 2401.10467 ↗First posted 19 Jan 2024cs.AI cs.LG math.OCcited by 5

Not on the map. Why?

Abstract (arXiv)

Many real-world problems can be efficiently modeled as Mixed Integer Linear Programs (MILPs) and solved with the Branch-and-Bound method. Prior work has shown the existence of MILP backdoors, small sets of variables such that prioritizing branching on them when possible leads to faster running times. However, finding high-quality backdoors that improve running times remains an open question. Previous work learns to estimate the relative solver speed of randomly sampled backdoors through ranking and then decide whether to use the highest-ranked backdoor candidate. In this paper, we utilize the Monte-Carlo tree search method to collect backdoors for training, rather than relying on random sampling, and adapt a contrastive learning framework to train a Graph Attention Network model to predict backdoors. Our method, evaluated on several common MILP problem domains, demonstrates performance improvements over both Gurobi and previous models.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 23 of its 47 references that are in the map. First posted on arXiv 19 Jan 2024.

Builds on

23 of 47 references.

References · 23

  1. 2017Graph Attention Networkscited by 8,854
  2. 2018Representation Learning with Contrastive Predictive Codingcited by 7,662
  3. 2018Learning deep representations by mutual information estimation and maximizationcited by 1,265
  4. 2020Graph Contrastive Learning with Augmentationscited by 1,203
  5. 2021How Attentive are Graph Attention Networks?cited by 818
  6. 2020A Survey on Contrastive Self-supervised Learningcited by 553
  7. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 313
  8. 2018An efficient framework for learning sentence representationscited by 197
  9. 2020Solving Mixed Integer Programs Using Neural Networkscited by 178
  10. 2019Reinforcement Learning for Integer Programming: Learning to Cutcited by 108
  11. 2020Hybrid Models for Learning to Branchcited by 95
  12. 2022Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learningcited by 58
11 more
  1. 2020Contrastive Losses and Solution Caching for Predict-and-Optimizecited by 52
  2. 2021Learning to Schedule Heuristics in Branch-and-Boundcited by 45
  3. 2022A Survey for Solving Mixed Integer Programming via Machine Learningcited by 44
  4. 2021Learning a Large Neighborhood Search Algorithm for Mixed Integer Programscited by 41
  5. 2023A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programmingcited by 40
  6. 2023Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learningcited by 37
  7. 2022Learning to Compare Nodes in Branch and Bound with Graph Neural Networkscited by 30
  8. 2022Augment with Care: Contrastive Learning for Combinatorial Problemscited by 22
  9. 2018Learning to Search via Retrospective Imitationcited by 13
  10. 2021Finding Backdoors to Integer Programs: A Monte Carlo Tree Search Frameworkcited by 12
  11. 2021Learning Pseudo-Backdoors for Mixed Integer Programscited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 2; 2026: 3.

5 papers.

  1. 2025FORGE: Foundational Optimization Representations from Graph Embeddingscited by 2
  2. 2025ID-PaS+ : Identity-Aware Predict-and-Search for General Mixed-Integer Linear Programscited by 1
  3. 2026Fusing Backdoors, Machine Learning, and Optimization for Large-Scale Parametric Mixed-Integer Programscited by 0
  4. 2026FunL2O: LLM-Guided Feature Function Design for Learning to Optimizecited by 0
  5. 2026BiFE: Search-Efficient Discovery of CPU-Only Branching Policies via LLM-based Bi-Fidelity Evolutioncited by 0