Beyond Local Selection: Global Cut Selection for Enhanced Mixed-Integer Programming
Shuli ZengSijia ZhangShaoang LiFeng Wu, Xiang-Yang Li · 2025
Read Beyond Local Selection: Global Cut Selection for Enhanced Mixed-Integer Programming by Shuli ZengSijia ZhangShaoang LiFeng Wu, Xiang-Yang Li (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-15847.txt.
Introduction
Solvers for hard planning problems cut away weak options to shrink the search, and picking the right cuts matters. Shuli Zeng and co-authors argue in 2025 that cuts should be picked with the whole search in view. Older methods use fixed rules, and newer learning methods look at one node at a time. Both miss the wider context of the search tree.
Their method, called Global Cut Selection, draws the search tree as a two-sided graph. A graph network joined with trial-and-error learning then builds a picking strategy. Cuts are applied across all nodes, not just one. Tests on fake and large real problems beat both rule-based and learning-based rivals. The work targets mixed-integer programming, a core tool in logistics and planning.
Catalog record
| CREATOR | Shuli ZengSijia ZhangShaoang LiFeng Wu, Xiang-Yang Li |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 54 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-15847
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Beyond Local Selection: Global Cut Selection for Enhanced Mixed-Integer Programming Shuli ZengSijia ZhangShaoang LiFeng Wu, Xiang-Yang Li Abstract 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. 1 Introduction Mixed-integer programming (MIP) is a widely used optimization framework for solving various important real-world applications, such as supply chain management Paschos 2014 , production planning Jünger et al. 2009 and scheduling Chen 2010 . Solving MIPs is very challenging because they are NP-hard problems Bixby 1992 . State-of-the-art MIP solvers, such as Gurobi Gurobi Optimization, LLC 2024 and SCIP Bestuzheva et al. 2021a , typically employ branch-and-bound algorithms Land and Doig 2010 . A key technique for improving the efficiency of B&B is the use of cutting planes, which help prune the search space by tightening LP relaxations. Research on cutting planes can be categorized into two primary areas: cut generation Guyon et al. 2010 and cut selection Turner et al. 2022 . Cut generation involves creating valid linear inequalities that tighten the LP relaxations Achterberg 2007 . However, adding all generated cuts incurs substantial computational costs Wesselmann and Stuhl 2012 . To address this, cut selection strategies have been developed to choose a suitable subset of the generated cuts Wesselmann and Stuhl 2012 . Our paper focuses on the cut selection problem, which plays a crucial role in the overall performance of the solver Achterberg 2007 ; Tang et al. 2020 ; Paulus et al. 2022 . MIP solvers commonly rely on expert-designed, hard-coded heuristics Turner et al. 2023 for selecting cutting planes. However, such heuristics often fail to fully exploit the specific structural features of the given integer programming problems, such as production scheduling and packing. To further enhance the efficiency of MIP solvers, recent methods propose to use machine learning to learn cut selection strategies Wang et al. 2023 . These methods offer promising approaches to learning more effective methods by capturing latent features from specific types of problems. Previous learning-based research Tang et al. 2020 ; Huang et al. 2022 ; Wang et al. 2023 in this area has primarily concentrated on local strategies, focusing on the selection of cutting planes at individual node in search tree. However, global decisions, such as determining which nodes should receive which cutting planes and when to apply them throughout the entire search process, have largely been overlooked. The study by Berthold et al. Berthold et al. 2022 shows that choosing between adding cutting planes only at the root node or at all nodes can improve the SCIP solver’s performance by approximately 11% on the MIPLIB 2017 dataset Gleixner et al. 2021 . Because local strategies, such as score-based policies Tang et al. 2020 ; Huang et al. 2022 or hierarchical network selections Wang et al. 2023 , fail to leverage more global information, they can limit the overall efficiency of the selection strategy, particularly for large-scale problems. Through our experiments, we observed that simply extending a learning-based cut selection strategy from the root node to all nodes can lead to a 30% decrease in performance. Furthermore, as the problem size grows, the performance gap becomes increasingly pronounced. We posit that effective cut selection requires a strategy that considers the entire search tree. Learning at the individual node level often fails to capture inter-node dependencies and global search tree structure, both of which are critical for optimal decision-making. Moreover, without a global representation, it becomes difficult to track the history of previously selected cutting planes. This limitation is significant because the effects of cutting planes are not independent; their combined impact on the search process can vary substantially. Thus, a lack of historical and contextual information hinders the ability to identify combinations of cuts that work well together. In principle, a branch-and-cut algorithm could leverage information from the entire search tree for cut selection. However, a search tree can easily consist of thousands of nodes, generating an immense and often redundant volume of data that is challenging to represent in a single model. Consequently, prior works Achterberg 2007 ; Baltean-Lugojan et al. 2019 ; Huang et al. 2022 ; Paulus et al. 2022 have typically limited their focus to information from the current node alone. For example, Wang et al. Wang et al. 2023 manually extracted 13-dimensional features based on one cut and the root node. This approach, however, is insufficient for effective cut selection across all nodes, as it lacks a broader context of the search tree. The resulting strategy treats each node in isolation, akin to the root node, which can hinder performance. To address the challenges in cut selection, we propose a new approach to represent global tree information tailored to the problem of cutting plane selection. Specifically, we introduce the Global Cut Selection (GCS) framework, which incorporates innovative strategies for feature extraction and decision-making. First, the method represents the entire search tree using all leaf nodes. By analyzing the common and distinct parts of each leaf node, it embeds the information from all leaf nodes into a single graph. Additionally, GCS tracks the history of each added cutting plane on the graph, allowing the network to make more informed decisions based on past data. A Graph Neural Network (GNN) then aggregates this information to select cutting planes, while a Transformer network considers the relationships between all cutting planes for optimal selection. This approach ensures that the selection process leverages the full context of the search tree, leading to more effective and efficient cutting plane decisions. The contributions of this paper are summarized as follows: • We propose GCS, a reinforcement learning (RL) framework for adding cutting planes at all nodes, and empirically demonstrate its advantages over single-node selection methods. • GCS leverages the information of the entire search tree to inform cutting plane selection. GCS represents the search tree as a bipartite graph, which serves as the input to the network, rather than relying solely on the information from the current node as in previous work. • We conducted extensive experiments on both small and large datasets, demonstrating that GCS consistently outperforms previous state-of-the-art (SOTA) strategies in terms of solving speed, node reduction, and generality. 2 Background Mixed integer programming (MIP). The general form of a MIP is given by z^{*}=\min_{\mathbf{x}}\left\{\mathbf{c}^{T}\mathbf{x}\mid\mathbf{A}\mathbf{x}\leq\mathbf{b},\mathbf{x}\in\mathbb{R}^{n},x_{j}\in\mathbb{Z},\forall j\in I\right\} (1) where \mathbf{x}\in\mathbb{R}^{n} is the set of n decision variables, \mathbf{c}\in\mathbb{R}^{n} formulates the linear objective function, \mathbf{A}\in\mathbb{R}^{m\times n} and \mathbf{b}\in\mathbb{R}^{m} formulate the set of m constraints, with \mathbf{A} representing the constraint matrix and \mathbf{b} the vector of constraint bounds,