MDD Propagation for Sequence Constraints
Authors: D. Bergman, A. A. Cire, W. van Hoeve
JAIR 2014 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We experimentally evaluate the performance of our proposed filtering algorithm, and demonstrate that the strength of the MDD propagation increases as the maximum width is increased. In particular, MDD propagation can outperform conventional domain propagation for Sequence by reducing the search tree size and solving time by several orders of magnitude. Similar improvements are observed with respect to the current best MDD approach that applies the decomposition of Sequence into Among constraints. |
| Researcher Affiliation | Academia | David Bergman EMAIL School of Business, University of Connecticut 2100 Hillside Road, Unit 1041, Storrs, CT 06260 Andre A. Cire EMAIL Willem-Jan van Hoeve EMAIL Tepper School of Business, Carnegie Mellon University 5000 Forbes Avenue, Pittsburgh, PA 15213 USA |
| Pseudocode | Yes | Algorithm 1 Intersection(M,M ) ... Algorithm 2 MDD-Consistency(M,M ) |
| Open Source Code | No | The text does not provide a specific link to source code or an explicit statement about its release. |
| Open Datasets | Yes | All instances are available at http://www.andrew.cmu.edu/user/vanhoeve/mdd/. |
| Dataset Splits | No | We generate instances with n = 50 variables each having domain {0, 1, . . . , 10}, and 5 Sequence constraints. For each Sequence constraint, we set the length of subsequence uniform randomly between [5, n/2) as q = (rand()%((n/2) 5)) + 5. ... We generated 250 such instances in total. |
| Hardware Specification | Yes | All experiments are performed using a 2.33GHz Intel Xeon machine. |
| Software Dependencies | Yes | We have implemented our MDD propagator for Sequence as a custom global constraint in IBM ILOG CPLEX CP Optimizer 12.4, using the C++ interface. |
| Experiment Setup | Yes | To measure the impact of the different propagation methods correctly, all approaches apply the same fixed search strategy, i.e., following the given ordering of the variables, with a lexicographic value ordering heuristic. |