A Divide and Conquer Algorithm for Predict+Optimize with Non-convex Problems
Authors: Ali Ugur Guler, Emir Demirović, Jeffrey Chan, James Bailey, Christopher Leckie, Peter J. Stuckey3749-3757
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We evaluate on 0-1 knapsack problems and a scheduling problem, and compare with the previous state of the art competing approaches. We show our divide and conquer approach achieves identical results to the DP model at knapsack benchmarks and scales better for larger problems. We also demonstrate that for hard non-convex problems DNL performs better than a non-linear exact model SPO-Forest (Elmachtoub, Liang, and Mc Nellis 2020) and is more robust compared to state of the art surrogate models SPO-Relax (Mandi et al. 2020), QPTL (Wilder, Dilkina, and Tambe 2019), Int Opt (Mandi and Guns 2020), DP (Demirovic et al. 2020)). |
| Researcher Affiliation | Academia | 1 University of Melbourne, 2 TU Delft, 3 RMIT University, 4 Monash University |
| Pseudocode | Yes | Algorithm 1: DNL algorithm 1: procedure COORDINATE DESCENT(θ) 2: For Model Parameters β and features θ 3: β initialize with regression 4: for all θbatch θ do 5: for all βi β do 6: Define constants, Ci, for coordinate descent 7: Ci P j =i θj βj 8: T Extract Transition Points(θi, βi, Ci) 9: βopt Compare Transitions(T, θi, Ci) 10: βi step towards βopt |
| Open Source Code | Yes | 1https://github.com/Patyrn/Divide-and-Learn |
| Open Datasets | Yes | We use the dataset from the ICON energy challenge (Simonis et al. 2014) for both knapsack and scheduling problems. The same dataset was used in previous work on PPO (Mandi et al. 2020; Demirovic et al. 2020). |
| Dataset Splits | Yes | We split the dataset into 70% training set, 10% validation set and 20% test set, resulting in 552, 79 and 157 optimization problems for training, validation and testing. |
| Hardware Specification | Yes | The models are trained with Intel(R) Xeon(R) Gold 6254 CPU @ 3.10GHz processors using 8 cores with 3.10 Ghz clock speed. |
| Software Dependencies | Yes | We use Gurobi Optimization 2022 to solve knapsack and scheduling problems. |
| Experiment Setup | Yes | For the knapsack problems max training time is set to 4000 seconds ( 1 hour). For scheduling problems max training time is set to 12000 seconds ( 3.3 hours). Refer to Appx. B for detailed hyper parameter configurations. We use early stopping for all PPO models (Bishop 2006), and use the iteration with the least validation regret. We warmstart model parameters with regression (Pratt and Jennings 1996). |