Learning to Pivot as a Smart Expert
Authors: Tianhao Liu, Shanwen Pu, Dongdong Ge, Yinyu Ye
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 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. |
| Researcher Affiliation | Academia | 1Research Institute for Interdisciplinary Sciences, Shanghai University of Finance and Economics 2Stanford University liu.tianhao@163.sufe.edu.cn, 2019212802@live.sufe.edu.cn, ge.dongdong@mail.shufe.edu.cn, yyye@stanford.edu |
| Pseudocode | No | The paper describes methods and algorithms verbally and with mathematical formulations, but it does not contain any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any explicit statement about releasing open-source code for the methodology it describes, nor does it include a link to a code repository for its own work. |
| Open Datasets | Yes | Benchmarks We have chosen a diverse set of LP problem tests, including a NETLIB subset (Gay 1985) and LP relaxations from four combinatorial optimization (CO) classes. These CO problems, inspired by Gasse et al. (2019), may differ in scale. |
| Dataset Splits | Yes | In the training process, we utilize 5 unique seeds for both data generation and model training. We apply identical hyperparameters for each CO benchmark, drawing upon 50,000 pivot samples from 1,000 instances for training, and 10,000 samples from 200 instances for validation. To assess the model s applicability in realworld scenarios, we test it on 200 new instances, underlining its ability to generalize on each benchmark. |
| Hardware Specification | Yes | All tests are conducted on an AMD Ryzen 7 5700X CPU and NVIDIA RTX 3060 12GB GPU. |
| Software Dependencies | Yes | We presolve NETLIB instances with Gurobi 10.0.2 and CO instances with SCIP 8.0.3. |
| Experiment Setup | Yes | In the training process, we utilize 5 unique seeds for both data generation and model training. We apply identical hyperparameters for each CO benchmark, drawing upon 50,000 pivot samples from 1,000 instances for training, and 10,000 samples from 200 instances for validation. |