Learning Cut Generating Functions for Integer Programming
Authors: Hongyu Cheng, Amitabh Basu
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our empirical results show that the selected CGF can outperform the GMI cuts for certain distributions. |
| Researcher Affiliation | Academia | Hongyu Cheng Dept. of Applied Mathematics & Statistics Johns Hopkins University Baltimore, MD 21218 hongyucheng@jhu.edu Amitab h Basu Dept. of Applied Mathematics & Statistics Johns Hopkins University Baltimore, MD 21218 basu.amitabh@jhu.edu |
| Pseudocode | Yes | Algorithm 1 shows how to compute the function values πf,µ(r) (the cutting plane coefficients), in time that is linear in the dimension k. |
| Open Source Code | Yes | The code and data used in all experiments are available at https://github.com/Hongyu-Cheng/Learn CGF. |
| Open Datasets | Yes | Instances were generated using the so-called Chvátal distribution from [Balcan et al., 2021b]... The packing instances were generated using the distribution from [Tang et al., 2020]. |
| Dataset Splits | No | The paper mentions training and test sets but does not explicitly describe a separate validation set or its split details. |
| Hardware Specification | Yes | The experiments were run on a Linux machine equipped with a 12-core Intel i7-12700F CPU and 32GB of RAM. |
| Software Dependencies | Yes | We solved the integer programming problems using Gurobi 11.0.1 [Gurobi Optimization, LLC, 2023], with default cuts, heuristics, and presolve settings turned off. |
| Experiment Setup | Yes | The parameters for the cut generating functions were selected to minimize the average branch-and-cut tree size on the training set of size 100... We fixed p = q = 2 and performed a grid search with a step size of 0.1 to select the best parameter µ {0, 0.1, . . . , 0.9, 1}2... We uniformly sampled 121 different µ on the simplex k... All cuts are generated from the first row of the simplex tableau with a non-integer right-hand side, and the k-row cut is generated from the first k such rows. |