# Solving a Class of Cut-Generating Linear Programs via Machine Learning

arXiv: https://arxiv.org/abs/2310.19920 · HTML: https://mlsanity.com/paper/2310.19920/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 29 references that are in the map.
- First posted on arXiv 30 Oct 2023.

## Builds on (most cited first, 4 of 4)

- [Reinforcement Learning for Integer Programming: Learning to Cut](https://mlsanity.com/paper/1906.04859/) (2019)
- [Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies](https://mlsanity.com/paper/2002.05120/) (2020)
- [Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond](https://mlsanity.com/paper/2106.04033/) (2021)
- [On the Structure of Decision Diagram-Representable Mixed Integer Programs with Application to Unit Commitment](https://mlsanity.com/paper/2207.06650/) (2022)

## Built on by (most cited first, 2 of 2)

- [All You Need is an Improving Column: Enhancing Column Generation for Parallel Machine Scheduling via Transformers](https://mlsanity.com/paper/2410.15601/) (2024)
- [A Graphical Global Optimization Framework for Parameter Estimation of Statistical Models with Nonconvex Regularization Functions](https://mlsanity.com/paper/2505.03899/) (2025)

## Abstract (arXiv)

Cut-generating linear programs (CGLPs) play a key role as a separation oracle to produce valid inequalities for the feasible region of mixed-integer programs. When incorporated inside branch-and-bound, the cutting planes obtained from CGLPs help to tighten relaxations and improve dual bounds. However, running the CGLPs at the nodes of the branch-and-bound tree is computationally cumbersome due to the large number of node candidates and the lack of a priori knowledge on which nodes admit useful cutting planes. As a result, CGLPs are often avoided at default settings of branch-and-cut algorithms despite their potential impact on improving dual bounds. In this paper, we propose a novel framework based on machine learning to approximate the optimal value of a CGLP class that determines whether a cutting plane can be generated at a node of the branch-and-bound tree. Translating the CGLP as an indicator function of the objective function vector, we show that it can be approximated through conventional data classification techniques. We provide a systematic procedure to efficiently generate training data sets for the corresponding classification problem based on the CGLP structure. We conduct computational experiments on benchmark instances using classification methods such as logistic regression. These results suggest that the approximate CGLP obtained from classification can improve the solution time compared to that of conventional cutting plane methods. Our proposed framework can be efficiently applied to a large number of nodes in the branch-and-bound tree to identify the best candidates for adding a cut.