Resolving Over-Constrained Temporal Problems with Uncertainty through Conflict-Directed Relaxation
Authors: Peng Yu, Brian Williams, Cheng Fang, Jing Cui, Patrik Haslum
JAIR 2017 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In our benchmark experiments, BCDR has also demonstrated its efficiency on solving large-scale scheduling problems in the aforementioned domains. Thanks to its conflict-driven approach for computing relaxations, BCDR achieves one to two orders of magnitude improvements on runtime performance when compared to state-of-the-art numerical solvers. In this section, we discuss the three applications of BCDR, in the domains of deep-sea mission planning, transit vehicle scheduling, and resource-constrained project scheduling. Within each of the applications, we present the modeling of the problems, the configurations of BCDR for solving them, and the experiments for evaluating BCDR s performance compared to alternative approaches or commercial solvers. |
| Researcher Affiliation | Academia | Peng Yu EMAIL Brian Williams EMAIL Cheng Fang EMAIL Computer Science and Artificial Intelligence Laboratory, MIT 32 Vassar Street, Cambridge, Massachusetts 02139, USA Jing Cui EMAIL Patrik Haslum EMAIL Research School of Computer Science, ANU & Decisions Sciences Program, Data61 Canberra, Australia |
| Pseudocode | Yes | The pseudo code of BCDR is given in Algorithm 1. Algorithm 1: The BCDR algorithm. Algorithm 2: Function Expand On Conflict. Algorithm 3: BCDR-U for solving CCTPUs. Algorithm 4: Strong controllability checking algorithm. Algorithm 5: Modified fast DCcheck algorithm for learning conflicts from uncontrollable networks. Algorithm 6: BCDR-C algorithm for resolving cc-p CCTPs. Algorithm 7: The Reactive BCDR algorithm. Algorithm 8: Bellman-Ford algorithm with relaxed criteria on distance updates. Algorithm 9: Modifications to Function Expand On Conflict (Algorithm 2) for handling candidates with greedy relaxation. Algorithm 10: Modifications to the BCDR algorithm (Algorithm 1) for greedy continuous relaxation. |
| Open Source Code | Yes | Our Python implementation of BCDR used in these experiments, along with all the test cases created, can be found on Git Hub: https://github.com/yu-peng/cdru. |
| Open Datasets | Yes | As test cases, we use 325 partial-order schedules for RCPSP/max problems (Kolisch & Padman, 2001) with 10 18 jobs.3. Set J10 from PSPLIB (http://www.om-db.wi.tum.de/psplib/) |
| Dataset Splits | No | In total, we created 2400 test cases using randomly generated numbers of robots, risk bounds, survey locations and mission length. As test cases, we use 325 partial-order schedules for RCPSP/max problems (Kolisch & Padman, 2001) with 10 18 jobs. The paper does not specify how these datasets were split into training/validation/test sets for their own experiments. |
| Hardware Specification | Yes | All experiments presented in this section were conducted on a desktop computer with an Intel Core i7-2600 processor and 32GB of RAM. |
| Software Dependencies | Yes | The SNOPT optimizer we used is version 7.2, and the Gurobi optimizer is version 6.5.1. |
| Experiment Setup | Yes | The traversal times are computed using an average speed randomly selected between 10 and 20 kilometers per hour. The survey length at each location and the dive duration, Tact and Tdiv, are randomly sampled in [10, 90] and [60, 960] (minutes), respectively. These durations are encoded as relaxable temporal constraints. We define linear preference functions over these relaxable constraints with gradient (cost per minute) sampled between 0 and 10. The reward for each variable assignment, denoting a location selection for each survey activity, ranges from 0 to 1000. |