Automatic Dominance Breaking for a Class of Constraint Optimization Problems
Authors: Jimmy Lee, Allen Zhong
IJCAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experimentation confirms runtime improvements of up to three orders of magnitude against manual methods. |
| Researcher Affiliation | Academia | Jimmy H.M. Lee and Allen Z. Zhong Department of Computer Science and Engineering The Chinese University of Hong Kong Shatin, N.T., Hong Kong {jlee, zwzhong}@cse.cuhk.edu.hk |
| Pseudocode | Yes | 1 int: n; int: l; int: d; 2 array [1..l] of var 1..n: F; 3 array [1..l] of var 1..d: v1; 4 array [1..l] of var 1..d: v2; 5 constraint increasing(F); ... The above code template shows our basic nogood generation model in Mini Zinc [Nethercote et al., 2007]. |
| Open Source Code | Yes | All models and experimental data are available at https://github. com/Allen Zzw/Automatic-Dominance-Breaking. |
| Open Datasets | Yes | We use instances from https://people.eng.unimelb.edu.au/ pstuckey/dom-jump/ where the number of items n = 100, 150, 200, 250, 300. ... For n = 20, 25, 30, 35, 40, we generate random instances with 10 halls and n applications, 1 sa ea 100, 200 ra, ch 1000 and 10 pa ea sa+1. ... For n {35, 40, 45, 50}, we generate random graphs with n vertices by independently sampling each edge with probability p = 0.1 whose weights are random integers in [1, 10]. |
| Dataset Splits | No | The paper mentions generating instances and benchmarks but does not specify explicit training, validation, or test dataset splits (e.g., percentage-based or k-fold cross-validation). |
| Hardware Specification | No | The paper does not specify any particular hardware (e.g., CPU, GPU models, or memory) used for running the experiments. |
| Software Dependencies | Yes | We use Mini Zinc 2.2.3 [Nethercote et al., 2007] to model both the problems and nogood generation respectively, and the back-end solver is Chuffed [Ohrimenko et al., 2009]. |
| Experiment Setup | Yes | Our experiments use four benchmarks, 10 instances for each problem configuration. ... but subjecting to a uniform timeout limit of 3600s for all benchmark instances. ... We attempt to generate and augment the basic models with all nogoods of length up to 2 (2-dom), 3 (3-dom) and 4 (4-dom). |