Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.15847 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913747514163200 |
|---|---|
| author | Zeng, Shuli Zhang, Sijia Li, Shaoang Wu, Feng Li, Xiang-Yang |
| author_facet | Zeng, Shuli Zhang, Sijia Li, Shaoang Wu, Feng Li, Xiang-Yang |
| contents | In mixed-integer programming (MIP) solvers, cutting planes are essential for Branch-and-Cut (B&C) algorithms as they reduce the search space and accelerate the solving process. Traditional methods rely on hard-coded heuristics for cut plane selection but fail to leverage problem-specific structural features. Recent machine learning approaches use neural networks for cut selection but focus narrowly on the efficiency of single-node within the B&C algorithm, without considering the broader contextual information. To address this, we propose Global Cut Selection (GCS), which uses a bipartite graph to represent the search tree and combines graph neural networks with reinforcement learning to develop cut selection strategies. Unlike prior methods, GCS applies cutting planes across all nodes, incorporating richer contextual information. Experiments show GCS significantly improves solving efficiency for synthetic and large-scale real-world MIPs compared to traditional and learning-based methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_15847 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Beyond Local Selection: Global Cut Selection for Enhanced Mixed-Integer Programming Zeng, Shuli Zhang, Sijia Li, Shaoang Wu, Feng Li, Xiang-Yang Artificial Intelligence In mixed-integer programming (MIP) solvers, cutting planes are essential for Branch-and-Cut (B&C) algorithms as they reduce the search space and accelerate the solving process. Traditional methods rely on hard-coded heuristics for cut plane selection but fail to leverage problem-specific structural features. Recent machine learning approaches use neural networks for cut selection but focus narrowly on the efficiency of single-node within the B&C algorithm, without considering the broader contextual information. To address this, we propose Global Cut Selection (GCS), which uses a bipartite graph to represent the search tree and combines graph neural networks with reinforcement learning to develop cut selection strategies. Unlike prior methods, GCS applies cutting planes across all nodes, incorporating richer contextual information. Experiments show GCS significantly improves solving efficiency for synthetic and large-scale real-world MIPs compared to traditional and learning-based methods. |
| title | Beyond Local Selection: Global Cut Selection for Enhanced Mixed-Integer Programming |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2503.15847 |