← Back to all news
arXiv Machine Learning

Interpretable Cutting Plane Selection for Mixed-Integer Linear Programming Using Genetic Programming

The paper introduces GPSCS, a learning-based framework that uses genetic programming to evolve a symbolic scoring function for selecting cutting planes in mixed-integer linear programming. It also employs a statistics-based method to decide how many top-ranked cuts to add during each separation round. Experiments on diverse synthetic and real-world benchmarks show that GPSCS reduces solving time by 6% over SCIP’s default strategy and outperforms a neural-network approach and a no-cut baseline, indicating strong generalization and robustness.

Related stories

arXiv AI
Sep 21

Collab-Solver: Collaborative Solving Policy Learning for Mixed-Integer Linear Programming

Collab‑Solver introduces a multi‑agent policy learning framework for mixed‑integer linear programming (MILP) that enables collaborative optimization of multiple solver modules. By modeling the interaction between cut selection and branching as a Stackelberg game, the approach employs a two‑phase learning paradigm—data‑communicated policy pretraining followed by coordinated policy refinement. Experiments on synthetic and large‑scale real‑world MILP datasets show that the jointly learned policies markedly improve solving performance and generalize well across diverse instance sets.

By Siyuan Li, Yifan Yu, Zhihao Zhang, Mengjing Chen, Fangzhou Zhu, Tao Zhong, Peng Liu, Jianye Hao
agents
More like this →
Hugging Face Trending Papers
Aug 20

Learning Early-to-Final Solution Consistency for MILP Acceleration

Mixed-Integer Linear Programming (MILP) is a fundamental problem class in operations research and combinatorial optimization, with broad applications to industrial decision-making. Owing to their NP-hardness, however, modern solvers may struggle to find high-quality solutions for challenging MILP instances within practical time limits.

benchmarks
More like this →
arXiv AI
Jul 22

MILP-Evo: Closed-Loop Fully Automatic Design of MILP Solvers

arXiv:2607. 18252v1 Announce Type: new Abstract: Machine learning methods have shown that data-driven policies can accelerate mixed-integer linear programming (MILP) solvers, but many such approaches remain difficult to inspect, adapt, and deploy because the learned policy is represented as an external predictor or other opaque model.

By Jinbiao Nie, Kewei Feng, Xiaoyuan Zhang, Shan Yin, Zizhuo Wang, Bin Dong
llmsbenchmarks
More like this →
arXiv Machine Learning
Aug 27

SHSP: Structure-Aware Hierarchical Solution Prediction for Mixed-Integer Linear Programming

The paper introduces SHSP, a Structure-Aware Hierarchical Solution Prediction framework for Mixed-Integer Linear Programming. SHSP replaces one-shot marginal decoding with a hierarchical conditional decoding that sequentially predicts variables based on a coupling graph derived from constraints, and includes a confidence-aware mask-and-repair step to correct errors. Experiments on four MILP benchmarks show SHSP reduces the solution gap by an average of 54% compared to existing one-shot methods.

By Zherong Zhang, Guanlin Li, Chengrui Gao, Haopu Shang, Ke Xue, Jixiang Lu, Weiyong Yang, Chao Qian
benchmarks
More like this →
arXiv Machine Learning
Oct 3

Reformulation-Contrastive Learning for Mixed Integer Programs

The paper introduces ReMILP, a reformulation‑contrastive learning framework that uses self‑supervision from equivalent formulations of mixed‑integer linear programs (MILPs). By distinguishing re‑descriptions and substitutions, the method trains a graph neural network and a hypernetwork to predict how variable embeddings transform under changes of variables, achieving invariance and equivariance without solver‑derived labels. The learned representations prove useful for tasks such as binary solution, constraint activity, and integrality gap prediction, and serve as a strong initialization for fine‑tuning.

By Ousema Bouaneni, Mathis Le Bail, Cl\'ement Elliker, Ma\"el Jenny, Sonia Vanier
ragfine-tuning
More like this →