Predict+Optimize for Packing and Covering LPs with Unknown Parameters in Constraints
Authors: Xinyi Hu, Jasper C.H. Lee, Jimmy H.M. Lee
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experimentation demonstrates the superior empirical performance of our method over classical approaches. We evaluate the proposed interior point based method with post-hoc correction (Int Opt-C) on 3 benchmarks: a maximum flow transportation problem with unknown edge capacities, an alloy production problem with unknown chemical composition in the raw materials, and a fractional knapsack problem with unknown rewards and weights. We compare our method with 5 classical regression methods (Friedman, Hastie, and Tibshirani 2001) including ridge regression (Ridge), k-nearest neighbors (k-NN), classification and regression tree (CART), random forest (RF), and neural network (NN). All of these methods train the prediction models with their classic loss function. |
| Researcher Affiliation | Academia | Xinyi Hu1, Jasper C.H. Lee2, Jimmy H.M. Lee1 1Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong 2Department of Computer Sciences & Institute for Foundations of Data Science, University of Wisconsin Madison, WI, USA |
| Pseudocode | No | The paper describes algorithmic approaches and mathematical derivations but does not include any explicitly labeled pseudocode or algorithm blocks. |
| Open Source Code | Yes | Our implementation is available at https://github.com/dadahxy/AAAI Post Hoc Regret. |
| Open Datasets | Yes | We conduct experiments on 3 real-life graphs: POLSKA (Orlowski et al. 2007) with 12 vertices and 18 edges, USANet (Lucerna et al. 2009) with 24 vertices and 43 edges, and G EANT (LLC 2018) with 40 vertices and 61 edges. Given that we are unable to find datasets specifically for this max-flow problem, we follow the experimental approach of Demirovic et al. (2019; 2019; 2020) and use real data from a different problem (the ICON scheduling competition) as numerical values required for our experiment instances. ... Since we could not find any real data on the concentration of metals in ores, we again use real data from a different problem (a knapsack problem (Paulus et al. 2021)) as numerical values in our experiment instances. |
| Dataset Splits | Yes | For experiments on POLSKA and USANet, out of the available 789 instances, 610 are used for training and 179 for testing the model performance, while for experiments on G EANT, out of the available 620 instances, 490 are used for training and 130 for testing the model performance. ... For experiments on both of the two alloys productions, 350 instances are used for training and 150 instances for testing the model performance. ... We use 700 instances for training and 300 instances for testing the model performance. ... All of these methods train the prediction models with their classic loss function. The methods of k-NN, RF and NN as well as our method have hyperparameters, which we tune via cross-validation... |
| Hardware Specification | Yes | All models are trained with Intel(R) Xeon(R) CPU @ 2.20GHz. |
| Software Dependencies | No | Ridge, k-NN, CART and RF are implemented using scikit-learn (Pedregosa et al. 2011). The neural network is implemented using Py Torch (Paszke et al. 2019). To compute the optimal solution of an LP under the true parameters, we use the LP solver from Gurobi (Gurobi Optimization, LLC 2023). The paper lists software libraries and solvers with citations, but does not provide specific version numbers for these software components (e.g., 'PyTorch 1.9' or 'scikit-learn 0.24'). |
| Experiment Setup | Yes | The methods of k-NN, RF and NN as well as our method have hyperparameters, which we tune via cross-validation: for k-NN, we tried k {1, 3, 5}; for RF, we try different numbers of trees in the forest {10, 50, 100}; for both NN and our method, we treat the learning rate, epochs and weight decay as hyperparameters. We include the final hyperparameter choices in Appendix B. For both NN and our method, we use a 3-layer fully-connected network with 16 neurons per hidden layer. For NN and our method, we use a 5-layer fully connected network with 512 neurons per hidden layer. |