Exploiting Functional Constraints in Automatic Dominance Breaking for Constraint Optimization
Authors: Jimmy H.M. Lee, Allen Z. Zhong
JAIR 2023 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experimentation shows significant runtime speedup using the dominance breaking nogoods generated by our proposed method. ... We present extensive experiments to evaluate the effectiveness of the generated nogoods in solving COPs using three state-of-the-art solvers. |
| Researcher Affiliation | Academia | Jimmy H. M. Lee EMAIL Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong Allen Z. Zhong EMAIL Department of Data Science and Artificial Intelligence, Faculty of Information Technology, Monash University, Australia |
| Pseudocode | No | The high-level algorithm is as follows: 1. Choose a maximum length L for dominance breaking nogoods. 2. For each scope S X where |S| {1, . . . , L}, (a) Synthesize generation CSPs to search for pairs (θ, θ ) of assignments over S, whose constraints imply that θ θ with respect to P. (b) Solve all solutions of the generation CSPs. (c) Collect the derived nogoods from the solutions (one nogood from each solution). 3. Add all the collected nogoods to the COP before problem-solving. (This is a description, not structured pseudocode or an algorithm block.) |
| Open Source Code | Yes | Our implementations are available at https://github.com/AllenZzw/auto-dom. |
| Open Datasets | Yes | The Talent Scheduling Problem (Cheng et al., 1993) is prob039 in CSPLib (Gent & Walsh, 1999)... The Warehouse Location Problem (Van Hentenryck, 1999) is prob034 in CSPLib (Gent & Walsh, 1999)... The Team Assignment Problem appears in Mini Zinc Challenge 2018 and 2022 (Stuckey, Becket, & Fischer, 2010)... The Still Mill Slab Design Problem (Kalagnanam, Dawande, Trumbo, & Lee, 1998), which is problem 039 in CSPLib (Gent & Walsh, 1999). |
| Dataset Splits | No | The standard benchmark for optimization problems includes several instance groups of various problem sizes, with each group consisting of 20 random instances. (This describes problem instances, not training/test/validation splits for machine learning.) |
| Hardware Specification | Yes | All experiments are run on Quad Xeon Platinum 8268 2.90GHz processors. |
| Software Dependencies | Yes | implement our nogood generation method by modifying the publicly available Mini Zinc compiler with version 2.6.21. ... The augmented models are submitted to Mini Zinc using the Chuffed solver 0.10.4 ... the CP-SAT solver in OR-Tools v9.6 ... and the Gecode solver 6.3.0. |
| Experiment Setup | Yes | The timeout for the whole solving process (nogood generation + problem-solving) is set to 7200 seconds, while we reserve at most 3600 seconds for nogood generation and use the remaining time for problem-solving in L-dom. If nogood generation times out in 3600 seconds, we augment the problem model with all nogoods generated before the timeout. Otherwise, the remaining time will be used for problem-solving. ... Chuffed(User): using the Chuffed solver with the user-specified search heuristic. Chuffed(VSIDS): using the Chuffed solver with the Variable State Independent Decaying Sum search heuristic. CP-SAT(User): using the CP-SAT solver with the user-specified search heuristic. CP-SAT(Auto): using the CP-SAT solver with the underlying SAT solver s heuristics. Gecode(User): using the Gecode solver with the user-specified search heuristic. |