Source-linked AI summary
Reinforcement Learning for Integer Programming: Learning to Cut
Yunhao Tang, Shipra Agrawal, Yuri Faenza
TL;DR
Integer programming is widely useful but difficult to solve, making heuristic design important. This paper learns adaptive cutting-plane selection with deep reinforcement learning and reports improvements across IP tasks, including when embedded in Branch-and-Cut.
Problem
Integer programs are broadly applicable but often hard to solve, and their commonly used heuristics are human-designed.
Method
The paper formulates adaptive Gomory-cut selection as deep reinforcement learning and uses the learned policy within cutting plane and Branch-and-Cut methods.
Results
Across packing, binary packing, planning, and maximum-cut tasks, the RL agent improves over human-designed heuristics and further improves Branch-and-Cut performance.
Takeaways & Limitations
The results provide evidence that RL can learn effective cutting-plane strategies and support integrating machine learning into integer-programming solvers.
Takeaways & Limitations
Without countermeasures, numerical errors and aggressive learned cuts caused the agent to cut off the optimal solution in up to 20% of instances.
Abstract
from arXiv · showhide
Integer programming (IP) is a general optimization framework widely applicable to a variety of unstructured and structured problems arising in, e.g., scheduling, production planning, and graph optimization. As IP models many provably hard to solve problems, modern IP solvers rely on many heuristics. These heuristics are usually human-designed, and naturally prone to suboptimality. The goal of this work is to show that the performance of those solvers can be greatly enhanced using reinforcement learning (RL). In particular, we investigate a specific methodology for solving IPs, known as the Cutting Plane Method. This method is employed as a subroutine by all modern IP solvers. We present a deep RL formulation, network architecture, and algorithms for intelligent adaptive selection of cutting planes (aka cuts). Across a wide range of IP tasks, we show that the trained RL agent significantly outperforms human-designed heuristics, and effectively generalizes to 10X larger instances and across IP problem classes. The trained agent is also demonstrated to benefit the popular downstream application of cutting plane methods in Branch-and-Cut algorithm, which is the backbone of state-of-the-art commercial IP solvers.
1. Introduction
Integer programming is broadly applicable but difficult to solve, motivating learned heuristics. The paper develops a deep RL agent for adaptive cut selection and evaluates it across IP classes and within Branch-and-Cut.
- Integer programming models discrete and combinatorial optimization problems, including scheduling, production planning, and graph optimization.
- IP instances are often hard to solve, so efficient heuristics are crucial and machine learning offers a way to tune them.
- The paper uses an RL agent as a subroutine in Gomory’s cutting plane method, combining learned selection with a widely applicable algorithmic framework.
- The proposed formulation limits the action space by selecting among Gomory cuts, while balancing state-space size against method generality.
- The deep RL architecture addresses slow LP-based state transitions and uses representations designed to generalize across ordering and instance size.
- Experiments across packing, binary packing, planning, and maximum cut show improvements over human-designed heuristics, including further gains when combined with Branch-and-Cut.
2. Background on Integer Programming
The cutting plane method repeatedly tightens a linear relaxation while preserving integer-feasible solutions until an integer optimum is obtained. Its efficiency depends on selecting effective cuts, and Branch-and-Cut combines cutting with branching.
- An IP minimizes a linear objective over integer points satisfying finitely many linear constraints, while its linear relaxation drops integrality constraints.
- The cutting plane method adds inequalities that preserve all integer-feasible solutions while removing the current fractional LP solution.
- Repeatedly solving tightened relaxations decreases the integrality gap and can terminate when the LP optimum is integer and therefore optimal for the IP.
- Integrality Gap Closure measures the fraction of the initial gap closed by a chosen stopping iteration, while optimal values are used only for evaluation.
- Gomory cuts are generated from fractional tableau rows, are valid for integer points, and offer up to n candidate cuts per iteration.
- Branch-and-Cut alternates cutting with branching, splitting fractional solutions into subproblems and using heuristics to choose which child node to process.
3. Deep RL Formulation and Solution Architecture
The paper formulates sequential cutting-plane selection as an RL problem and develops architectures and training procedures suited to variable-sized IPs. It also addresses numerical errors that can cause learned policies to remove optimal integer solutions.
- 3.1. Formulating Cutting Plane selection as RL: The RL objective maximizes discounted cumulative rewards, encouraging rapid reduction of the integrality gap.The discount factor weights immediate and later objective-value improvements.
- 3.1. Formulating Cutting Plane selection as RL: The cutting-plane selection problem is formulated as an MDP whose states encode the current LP, objective, solution, and candidate Gomory cuts.The agent chooses a cut, receives a reward from consecutive LP objective values, and transitions after resolving the augmented LP.
- 3.1. Formulating Cutting Plane selection as RL: Gomory cuts define a discrete action space, while representing each action as an inequality limits choices to available candidate cuts.Using Gomory cuts avoids the exponentially large action sets possible for some other cut classes.
- 3.2. Policy Network Architecture: An attention network makes cut selection order-agnostic by embedding constraints and candidates, scoring candidate interactions, and applying softmax probabilities.Each candidate score aggregates inner products with all constraints currently in the LP.
- 3.2. Policy Network Architecture: An LSTM embeds inequalities with varying numbers of variables so the same policy architecture can handle IP instances of different sizes.The LSTM hidden state replaces the original inequality representation before attention-based scoring.
- 3.3. Training: Evolutionary Strategies: The policy rollout repeatedly solves the LP, samples a candidate cut, appends it, computes the reward, and stops when the solution is integer-valued or the iteration limit is reached.This procedure constructs successive states and candidate-cut sets during execution.
- 3.3. Training: Evolutionary Strategies: Evolution strategies train the policy by perturbing parameters, estimating performance from rollouts, and updating parameters with an approximate policy gradient.Training can average estimators across multiple IP instances, with simple parameter updates and worker communication.
- 3.4. Testing: Numerical errors can make aggressive learned cutting remove the optimal integer solution, so testing terminates after consecutive cuts make little LP-objective progress.Without countermeasures, the agent cut the optimal solution in as many as 20% of instances.
4. Experiments
The experiments evaluate RL for cut selection across IP classes, instance sizes, generalization settings, and integration with Branch-and-Cut. RL improves cut efficiency and integrality-gap closure relative to human-designed heuristics, while also benefiting B&C and producing interpretable cuts.
- Experimental setup: The evaluation spans packing, production planning, binary packing, and maximum-cut problems, using randomly generated training and test instances.Small and medium problems use 30 training and 20 test instances; larger problems double these numbers.
- Efficiency of cuts: RL achieves close to several factors of improvement in the number of Gomory cuts required to reach optimality on small instances.The comparison uses Random, Max Violation, Max Normalized Violation, and Lexicographical Rule baselines.
- Integrality gap closure: On instances of roughly 1000 and 5000 variables-times-constraints, RL closes a significantly higher fraction of the integrality gap than competing methods after 50 and 250 cuts, respectively.The larger instances cannot generally be solved to optimality by cutting planes alone, so performance is measured using IGC.
- Generalization: An RL policy trained on 10X smaller instances performs extremely competitively on larger test instances, and a policy trained on packing performs comparably on larger maximum-cut instances.The cross-class transfer compares packing-trained RL/10X with an agent trained on maximum cut.
- Impact on Branch-and-Cut: Using RL-selected cuts in Branch-and-Cut substantially improves efficiency, even though the RL agent was not designed jointly with branching.Figure 5 measures child nodes expanded until termination, with 10 cuts added at each node.
- Interpretability of cuts: RL produces more cuts resembling lifted cover inequalities than the baselines, suggesting potential for discovering effective cutting-plane strategies.The comparison uses three increasingly loose criteria for closeness to lifted cover inequalities.
5. Conclusions
The paper presents deep RL for automatically learning cutting-plane strategies, with evidence of generalization across tasks not seen during training. The authors view these results as a step toward integrating machine learning into IP solvers.
- The RL agent learns an effective cutting-plane strategy by repeatedly solving randomly generated training instances without solved-instance supervision.
- Generalization across varied tasks provides evidence that the agent learns an intelligent algorithm for selecting cutting planes.
- The empirical results are presented as a step toward integrating machine-learning techniques into integer-programming solvers.
A. Experiment Details
The cutting-plane procedure starts from an LP relaxation, converts it to standard form, and uses the final simplex tableau to generate Gomory cuts from fractional variables. Slack-variable elimination produces an equivalent cut in the original variable space for the policy network.
- The procedure considers the first cutting-plane iteration and starts from an LP relaxation defined by A, b, c, and x.
- The simplex algorithm converts inequalities into equalities by introducing nonnegative slack variables.
- At convergence, the simplex method returns an optimal tableau, whose row for a fractional variable generates a Gomory cut.
- Multiplying the constraints by r and subtracting them from the slack-variable cut yields an equivalent cutting plane.
- Removing slack variables leaves a cut in the original variable space and reduces the neural network's parameterization size.
A.2. Integer programming formulations of benchmark problems
The appendix specifies benchmark formulations, instance generation, size conventions, and baseline rules for selecting Gomory cuts. It covers production planning, Max Cut, packing, and binary packing.
- A.2. Integer programming formulations of benchmark problems: Benchmark instances include packing, production planning, binary packing, and Max Cut, spanning resource-allocation and graph-optimization problems.
- A.2. Integer programming formulations of benchmark problems: Max Cut assigns variables to edges and nodes, uses nonnegative edge weights, and imposes constraints linking edge selections to node assignments.
- A.2. Integer programming formulations of benchmark problems: Max-Cut graphs are randomly generated by sampling edges, with edge weights uniformly drawn as integers from 0 to 10.
- A.2. Integer programming formulations of benchmark problems: Packing restricts A, b, and c to nonnegative coefficients, while binary packing adds constraints xi ≤1 for every variable.
- A.2. Integer programming formulations of benchmark problems: Packing coefficients and right-hand sides are randomly generated, with objective coefficients sampled as integers from 1 to 10; binary packing uses corresponding ranges from 5 to 30 and 10n to 20n.
- A.2. Integer programming formulations of benchmark problems: Production planning uses production, binary production-choice, and storage variables over a time horizon, with demand and cost parameters.
- A.2. Integer programming formulations of benchmark problems: Production-planning instances use initial storage 0, final storage 20, big M = 100, and uniformly sampled integer parameters from 1 to 10.
- A.2. Integer programming formulations of benchmark problems: Instance size is reported as n × m, where n counts variables and m counts constraint rows; cut-selection baselines include Random, MV, MNV, and Lexicographic rules.
A.4. Hyper-parameters
The policy architecture combines attention and recurrent encoding for variable-sized instances, while a simpler attention-only policy handles fixed-size instances. Training uses evolutionary-strategy optimization with Adam and distributed trajectory collection.
- The attention embedding uses a two-layer tanh network with 64 units per layer, and the LSTM encodes variable-sized inputs into a 10-dimensional hidden vector.
- The LSTM-plus-attention policy embeds the instance and applies attention, enabling generalization across different numbers of variables.
- The single-attention policy processes only fixed-size instances and is used in the IGC experiments.
- Evolutionary-strategy training uses Adam with learning rate α = 0.01, perturbation standard deviations selected from {0.002, 0.02, 0.2}, and typically N = 10 perturbations.
- Trajectory collection is distributed across parallel workers on a Linux machine with 60 virtual CPUs.
B. Branch-and-Cut Details
The implementation uses simple branching and node-selection rules to isolate the quality of RL-generated cuts, while tracking improving upper and lower bounds until a small ratio threshold is reached.
- The B&C implementation uses simple rules so experiments evaluate cutting-plane quality rather than overall search speed.
- Branching rule: At each node, branching selects the most fractional variable of the LP optimum.
- Priority queue: A FIFO queue performs breadth-first search and improves the B&C lower bound.
- The upper bound decreases as feasible integer solutions accumulate, while the lower bound increases as unpruned-node LP objectives improve.
- The procedure terminates when the ratio r falls below 0.0001.
C. Test Time Considerations
At test time, the method uses stopping and action-selection choices to control numerical errors and exploit the learned cut distribution, alongside an interpretation study on knapsack cuts.
- Stopping criterion: The trained policy may generate invalid cuts because aggressive training can exploit numerical errors and cut off the optimal solution.
- Stopping criterion: The test-time stopping rule halts cutting when the average recent improvement falls below a threshold, preventing invalid cuts.The reported settings are H = 5 and η = 0.001, which eliminated observed numerical errors in the reported tasks.
- Stopping criterion: Smaller H or larger η makes cutting more conservative, whereas larger H and smaller η make it more aggressive.
- Greedy action: At test time, greedy selection chooses the candidate cut with the highest policy probability.This choice is related to one-step-lookahead beam search.
- Cut interpretation: The interpretation study evaluates whether RL selects structurally effective cuts using cover-inequality criteria on knapsack instances.The criteria assess lifted-cover and related strengthening properties, with scores averaged across generated cuts.
- Evaluation setup: The study trains on 100 knapsack instances and evaluates on 20 independently generated instances.
E. Additional results on Large-scale Instances
On large-scale instances, the RL agent generally outperforms baseline heuristics in B&C, although performance can be comparable to selected heuristics on some problem classes.
- Large-scale B&C results use percentile plots of nodes required to reach specified IGC levels, with a 1000-node threshold across problem classes.
- Random packing uses a relatively low IGC because large instances are substantially more difficult to solve.
- The RL agent significantly exceeds other baseline heuristics overall.
- On planning problems, other heuristics barely reach the IGC within the node budgets.
- On Max Cut problems, RL can perform similarly to the MNV heuristic.
F. Comparison of Distributed Agent Interface
The distributed-agent discussion motivates scalable training and contrasts general learner–actor interfaces with evolution strategies, while large-scale B&C results are reported separately.
- Scaling RL training to powerful computational architectures requires a distributed agent.
- Figure 7 reports percentile plots of B&C nodes expanded for large-scale instances under the same setup as Figure 5.
- A general distributed design uses one learner and multiple actors that send trajectory data for parameter updates.
- Communication: Evolution strategies simplify communication by requiring actors to send trajectory returns rather than partial state-action-reward trajectories.
- Updates: Evolution strategies require only forward-mode computations, avoiding backward-mode engineering for efficient batching over irregular spaces.
G. Considerations on CPU Runtime
The runtime analysis evaluates whether RL’s higher-quality cuts offset policy overhead under fixed-cut and solver-runtime constraints. RL adds no significant runtime compared with fast heuristics at T = 50 and generally reduces runtime in difficult branch-and-cut instances.
- Runtime, rather than cut count alone, is the practically meaningful solver budget, especially at test time.Training-time runtime constraints are hardware-sensitive, whereas practitioners typically impose runtime limits during testing.
- Fixed-cut runtime: At T = 50 cuts, RL cutting-plane selection does not significantly increase CPU runtime compared with other fast heuristics.RL increases average runtime in some cases and decreases it in others.
- Fixed-cut runtime: At T = 50, most instances receive the same number of cuts, so runtime differences primarily reflect per-iteration and policy costs rather than fewer cuts.Optimality is usually not reached within the maximum cut budget in this experiment.
- Branch-and-cut runtime: In difficult branch-and-cut instances, RL’s reduced iteration count outweighs its potentially higher per-iteration runtime.The runtime benefit comes from expanding fewer nodes when high-quality cuts improve the search.
- Branch-and-cut runtime: Table 7 measures normalized branch-and-cut runtime to reach a target IGC level, using RL as the 100% reference.Only test instances reaching the target within node budgets are included; otherwise the runtime is reported as N/A.