The cutting plane method is a key technique for successful branch-and-cut and
branch-price-and-cut algorithms that find the exact optimal solutions for
various vehicle routing problems (VRPs). Among various cuts, the rounded
capacity inequalities (RCIs) are the most fundamental. To generate RCIs, we
need to solve the separation problem, whose exact solution takes a long time to
obtain; therefore, heuristic methods are widely used. We design a
learning-based separation heuristic algorithm with graph coarsening that learns
the solutions of the exact separation problem with a graph neural network
(GNN), which is trained with small instances of 50 to 100 customers. We embed
our separation algorithm within the cutting plane method to find a lower bound
for the capacitated VRP (CVRP) with up to 1,000 customers. We compare the
performance of our approach with CVRPSEP, a popular separation software package
for various cuts used in solving VRPs. Our computational results show that our
approach finds better lower bounds than CVRPSEP for large-scale problems with
400 or more customers, while CVRPSEP shows strong competency for problems with
less than 400 customers.

设计了一种基于图嵌入的知识学习方法，将其应用于割平面算法来解决带约束车辆路径问题，与传统求解器相比，一定规模上有更好的上界。

圆容量不等式的神经分离算法

A Neural Separation Algorithm for the Rounded Capacity Inequalities

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.

应用深度强化学习技术提升整数规划问题求解算法中割平面方法 (Cutting Plane Method) 的性能表现。通过对算法的智能自适应选择，和其在分支定界算法 (Branch-and-Cut algorithm) 中的应用，表现出在各种不同规模的样例和不同的整数规划问题中，训练出来的深度 RL 代理能显著的超过人类设计的启发式方法。

强化学习用于整数规划：学习剪切

Reinforcement Learning for Integer Programming: Learning to Cut

We present a novel binary convex reformulation of the sparse regression
problem that constitutes a new duality perspective. We devise a new cutting
plane method and provide evidence that it can solve to provable optimality the
sparse regression problem for sample sizes n and number of regressors p in the
100,000s, that is two orders of magnitude better than the current state of the
art, in seconds. The ability to solve the problem for very high dimensions
allows us to observe new phase transition phenomena. Contrary to traditional
complexity theory which suggests that the difficulty of a problem increases
with problem size, the sparse regression problem has the property that as the
number of samples $n$ increases the problem becomes easier in that the solution
recovers 100% of the true signal, and our approach solves the problem extremely
fast (in fact faster than Lasso), while for small number of samples n, our
approach takes a larger amount of time to solve the problem, but importantly
the optimal solution provides a statistically more relevant regressor. We argue
that our exact sparse regression approach presents a superior alternative over
heuristic methods available at present.

本文提出了一种新的二元凸重构稀疏回归问题的方法，并提供了一种新的切平面方法来解决高维数据时出现的问题。实验证明，与当前最先进的算法相比，本方法能够在秒内解决样本数和回归器数均在 10 万个数量级的稀疏回归问题，并且可以观察到新的相变现象。