Learning to Pivot as a Smart Expert

Abstract

Linear programming has been practically solved mainly by simplex and interior point methods. Compared with the weakly polynomial complexity obtained by the interior point methods, the existence of strongly polynomial bounds for the length of the pivot path generated by the simplex methods remains a mystery. In this paper, we propose two novel pivot experts that leverage both global and local information of the linear programming instances for the primal simplex method and show their excellent performance numerically. The experts can be regarded as a benchmark to evaluate the performance of classical pivot rules, although they are hard to directly implement. To tackle this challenge, we employ a graph convolutional neural network model, trained via imitation learning, to mimic the behavior of the pivot expert. Our pivot rule, learned empirically, displays a significant advantage over conventional methods in various linear programming problems, as demonstrated through a series of rigorous experiments.

References in corpus (7)

• Exact Combinatorial Optimization with Graph Convolutional Neural Networks
• Hybrid Models for Learning to Branch
• On Representing Linear Programs by Graph Neural Networks
• Cardinal Optimizer (COPT) User Guide
• An Enhanced ADMM-based Interior Point Method for Linear and Conic Optimization
• Learning To Dive In Branch And Bound
• (Machine) Learning to Improve the Empirical Performance of Discrete Algorithms