PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Gwen maudet, Mathis Da Cunha, Grégoire Danoy

arXiv:2610.29311v1cs.LGmath.OC

TL;DR

Cutting planes strengthen LP relaxations and improve bound quality, but each added constraint increases LP-solving burden, requiring a balance between cut strength and computational cost. GPSCS evolves interpretable cut-scoring functions from cut and context features and uses statistical score-dropout detection to determine how many top-ranked cuts to add. GPSCS outperforms the default SCIP configuration and the most practically applicable neural-network baseline for cut selection.

  • Problem

    Cutting planes strengthen LP relaxations and improve bound quality, but each added constraint increases LP-solving burden, requiring a balance between cut strength and computational cost.

    Source: §1 · p. 1

  • Method

    GPSCS evolves interpretable cut-scoring functions from cut and context features and uses statistical score-dropout detection to determine how many top-ranked cuts to add.

    Source: §1 · p. 2, Selection Procedure According to a Cut… · p. 4, Definition of the Cut Scoring Policy… · p. 5

  • Results

    GPSCS outperforms the default SCIP configuration and the most practically applicable neural-network baseline for cut selection.

    Source: §6 · p. 7

  • Takeaways & Limitations

    The statistical cut-quantity rule is solver-agnostic, while GP scoring learns instance-class-specific rankings suited to repeated solving within a problem family.

    Source: §6 · p. 7

Abstract

from arXiv · show

Cutting planes (cuts) remove fractional solutions from mixed-integer linear programs (MILPs) without excluding any feasible integer solutions, making them a key ingredient in modern MILP solvers. Current state-of-the-art solvers rely on fine-tuned handcrafted cut strategies, which, despite their effectiveness, remain inherently static and can be suboptimal. More recently, learning-based approaches have been proposed to design adaptive cut strategies; however, most of these methods are based on neural networks, offering limited interpretability and providing no guarantees of convergence. In this paper, we propose \emph{Genetic Programming and Statistics-based Cut Selection} (GPSCS), the first learning-based framework that explicitly generalizes handcrafted cut selection heuristics into a fully interpretable policy. First, a genetic programming model evolves a symbolic scoring function that ranks candidate cuts using features derived from the cuts and the solving context. Second, a lightweight statistics-based mechanism adaptively determines the number of top-ranked cuts to add at each separation round by detecting significant score dropouts. We evaluate GPSCS within the SCIP solver on seven classes of synthetic and real-world benchmark instances, with a strong emphasis on generalization: evaluation instances are on average 41 times harder than those used for training. Experimental results show that GPSCS improves average solving time by $6\%$ compared to SCIP's default cut selection strategy and achieves a two-fold speedup over both a recent neural-network-based approach and a no-cut baseline, demonstrating strong robustness and generalization across heterogeneous MILP families.

1 Introduction

Cuts strengthen LP relaxations but trade off better bounds against greater LP-solving cost. GPSCS learns interpretable cut rankings and adaptively chooses how many cuts to retain, and its evaluation reports improvements over standard solver and neural baselines.

1 Introduction

  • Adding cuts can tighten the LP relaxation, but each additional constraint increases LP-solving burden, so selection must balance bound strength and computational cost.The aim is to select a small subset of effective cuts.Source: §1 · p. 1
  • Handcrafted cut heuristics use fixed scoring rules and cut counts, while neural approaches offer limited interpretability and no convergence guarantees.The paper frames its objective as learning a complete cutting strategy tailored to a class of MILP instances.Source: §1 · p. 1
  • GPSCS combines GP-evolved scoring functions based on problem-, node-, and cut-level features with statistical dropout detection to choose how many cuts to retain.The dropout mechanism identifies score breakpoints among non-parallel cuts.Source: §1 · p. 2
  • GPSCS improves average solving time over SCIP’s default cut strategy and achieves a two-fold speedup over HEM and NoCuts.Evaluation covers seven synthetic and real-world benchmark classes; evaluation instances require 41 times more solving time on average than training instances.Source: §1 · p. 2
  • The paper defines a feature-based scoring space, uses GP to search it, and evaluates adaptive cut counts against four alternatives across seven benchmark classes.The introduction also reports potential convergence issues for HEM on certain instance classes.Source: §1 · p. 2

2 Background

The background explains how branch-and-bound uses LP relaxations and pruning, how cuts can strengthen bounds at a computational cost, and how genetic programming evolves program-like candidate solutions.

2 Background

  • Branch-and-bound recursively partitions the feasible region, using LP relaxation bounds to prune subtrees or branching to create child subproblems.A subtree is pruned when its lower bound is no better than the incumbent solution.Source: §2 · p. 2
  • Cut selection ranks candidate inequalities and determines how many to add; too many constraints can increase formulation size and degrade LP-solving performance.Cuts strengthen LP bounds while preserving feasible integer solutions.Source: Cut Selection Strategy · pp. 2–3
  • Genetic programming evolves a population of program-encoded candidates through selection, crossover, and mutation until a stopping condition is met.Its population-based stochastic process allows individuals in a generation to be evaluated independently.Source: Cut Selection Strategy · p. 3

3 Related Work

Prior work spans handcrafted cut heuristics and learned adaptive strategies, with limitations in fixed choices, interpretability, or training demands. GPSCS positions GP-based interpretable scoring and statistical dropout as an alternative for ranking cuts and setting their quantity.

Handcrafted Heuristics

  • Fixed global weights for cut metrics are reported as suboptimal on heterogeneous instance distributions, motivating adaptive, instance-aware scoring.SCIP’s metrics include efficacy, directed cutoff distance, objective parallelism, and integer support; normalized violation is another metric.Source: Handcrafted Heuristics · p. 3
  • Fixed cut limits can be suboptimal because choosing the number of cuts must balance LP strengthening against computational overhead.SCIP typically uses larger limits at the root and smaller limits elsewhere, often retaining most cuts.Source: Handcrafted Heuristics · p. 3

ML Approaches

  • Learned cut-selection methods range from single-cut imitation or RL to HEM, which jointly ranks cuts and chooses quantity but uses black-box neural policies.HEM’s large decision space and sparse, delayed solving-time feedback make training demanding and potentially unstable, without guaranteed convergence.Source: ML Approaches · pp. 3–4

Positioning

  • GPSCS applies GP to cut selection, evolving executable, human-readable scoring functions from cut, node, and instance features to generalize handcrafted rules.The paper states that GP had not previously been explored for cut selection.Source: Positioning · p. 4
  • GPSCS uses statistical score-drop detection to retain top-ranked cuts, assuming sharp score drops indicate lower-ranked cuts unlikely to add value.The scoring function is assumed to reflect cut quality.Source: Positioning · p. 4

4 GP-based Cut Selection Strategy

GPSCS combines a GP-learned, interpretable cut-ranking function with filtering and score-dropout detection to select cuts at each separation round. Its scoring space extends handcrafted rules with cut, node, and instance features.

Selection Procedure According to a Cut Scoring Function

Prioritization of Orthogonal Cuts

  • Prioritizing non-parallel cuts separates geometric filtering from scoring, simplifying the learning task while reducing redundant cut directions.The filtering step is handled separately because cut parallelism can be computed explicitly.Source: Prioritization of Orthogonal Cuts · p. 4

Definition of the Cut Scoring Policy Space

  • The policy space combines cut- and context-related variables into symbolic expressions that score and rank candidates, subsuming handcrafted scoring strategies.Features include cut quality, node depth, and instance size; arithmetic and nonlinear operators allow varied scoring functions.Source: Definition of the Cut Scoring Policy… · p. 5

GP Framework

  • GP evolves candidate scoring functions using average training-instance solving time as fitness, with a 500-second penalty for instances reaching the time limit.A double-tournament selection design also limits excessive tree growth and mitigates overfitting.Source: GP Framework · p. 5

Training and Deployment

  • During training and deployment, the scoring function ranks cuts before the same filtering and dropout-based selection procedure is applied.At each branch-and-bound node, cuts are ranked, filtered to promote orthogonality, and selected using dropout detection.Source: Training and Deployment · p. 5

5 Experiments

Across seven benchmark classes, GPSCS achieved the lowest average solving time among the compared methods, despite evaluation instances being much harder than training instances. The experiments also compare GPSCS variants, assess generalization, and examine training and evaluation settings.

Experimental Setup

  • All methods ran in SCIP 9.2.2 with default solver components unchanged except for cut selection, and evaluation instances were solved sequentially under a 500-second limit.Each class used instances selected from those solvable within 300 seconds for the training/evaluation split.Source: Experimental Setup · pp. 5–6
  • The evaluation used seven classes, with 50 training and 50 evaluation instances per class and larger or harder evaluation instances.Three classes were synthetic; four came from established benchmarks and represented heterogeneous real-world instances.Source: §5 · p. 5, Experimental Setup · p. 6
  • Comparisons included NoCuts, SCIP, HEM, and five GP variants, including alternatives for cut quantity and cross-class transfer.GPSCS, WGPSCS, and GPSAll used a maximum dropout z-score threshold of 1; GP training used 15 independent runs, retaining the best training-set scoring function.Source: Experimental Setup · p. 6

Performance Evaluation

  • GP runs produced different symbolic expressions but consistent performance, with standard deviations below 0.06 seconds on synthetic instances.Learned functions differed substantially across problem classes, while some cut-quality features recurred across policies.Source: Performance Evaluation · pp. 6–7
  • GPSCS had the lowest average solving time across all seven classes, was fastest on three, and improved over SCIP by 6% on average.Evaluation instances were on average 41 times harder than training instances in solving time.Source: Performance Evaluation · p. 7, Table 2 · p. 7
  • Except on MAXSAT, HEM's solving times were generally at least twice those of the best-performing methods and often comparable to NoCuts.When NoCuts reached the 500-second limit, HEM also failed, even where GPSCS and SCIP solved instances within 25 seconds.Source: Performance Evaluation · p. 7
  • GPSCS outperformed GPNP, which required 5% more solving time on average, while GPRL consistently underperformed the other GP variants.The statistics-based cutoff selected about 10% fewer cuts than retaining all non-parallel cuts; GPSAll was competitive but slightly below GPSCS and GPNP.Source: Performance Evaluation · p. 7

6 Conclusions

The paper presents GPSCS as an explicit, interpretable strategy that jointly learns cut ranking and quantity selection. Its experiments show better performance than SCIP and the tested neural-network baseline, while the authors identify distinct deployment roles for its two components.

Conclusions

  • GPSCS combines nonlinear cut- and context-feature scoring with non-parallel cut prioritization and statistical dropout detection to choose how many cuts to add.The approach jointly addresses cut ranking and cut quantity decisions.Source: §6 · p. 7
  • GPSCS outperformed default SCIP and the tested neural-network baseline, while experiments indicated potential convergence issues in the NN-based RL framework.The authors relate the potential issues to delayed, sparse rewards in large decision spaces.Source: §6 · p. 7
  • The statistical cut-quantity rule is solver-agnostic and independent of problem class, whereas GP ranking functions are learned for specific instance classes.The paper identifies repeated solving of large collections from the same family as a suitable setting for the class-specific scoring mechanism.Source: §6 · p. 7
  • The authors conclude that embedding existing cutting-plane expertise in the learning design can produce interpretable strategies with faster and more stable convergence.They present population-based methods such as GP as complementary to neural-network approaches for improving solver performance.Source: §6 · p. 7

Références

The references cover optimization foundations, MILP solver and benchmark resources, and machine-learning approaches to combinatorial optimization and cut selection.

Optimization and cutting planes

  • The list includes foundational optimization and cutting-plane works, including Achterberg (2007) and Dey and Molinaro (2018).Source: Références · p. 8

Solvers and benchmarks

  • Solver and benchmark references include SCIP, Gurobi, CPLEX, and the StrIPlib library.Source: Références · p. 8

Learning-based optimization

  • Learning-related references span machine learning for combinatorial optimization, genetic programming for branch-and-bound, and learned cut selection.Examples include Maudet and Danoy (2025), Paulus et al. (2022), and Wang et al. (2023).Source: Références · p. 8
Loading 2610.29311v1…