Efficient Operations On MDDs for Building Constraint Programming Models
Authors: Guillaume Perez, Jean-Charles Régin
IJCAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We apply our approach to the regular constraint and obtain competitive results with dedicated algorithms. We also experiment our technique on a large scale problem: the phrase generation problem and we show that our approach gives equivalent results to those of a specific algorithm computing a complex automaton. Before concluding, we present some experiments showing some strong improvements brought by our algorithms. |
| Researcher Affiliation | Academia | Guillaume Perez and Jean-Charles Régin Université Nice-Sophia Antipolis, I3S UMR 7271, CNRS, France guillaume.perez06@gmail.com; jcregin@gmail.com |
| Pseudocode | Yes | Algorithm 1 p Reduce of an MDD., Algorithm 2 Complementary Operation., Algorithm 3 Generic Apply Function. |
| Open Source Code | No | The paper states 'The algorithms have been implemented on the top of ortools solver from Google [Perron, 2013] version 3158.', but does not provide a link or explicit statement about the availability of their own source code. |
| Open Datasets | Yes | We select some problems from the Solver Competition archive [Lecoutre, 2009]. |
| Dataset Splits | No | The paper does not explicitly state any training/validation/test dataset splits. It only mentions test sets or results on problems. |
| Hardware Specification | Yes | The experiments have been made on a 6 cores server (Intel 3930) having 64GB of memory and running under Windows 7. |
| Software Dependencies | Yes | The algorithms have been implemented on the top of ortools solver from Google [Perron, 2013] version 3158. |
| Experiment Setup | Yes | More precisely, first we define mdd4 the MDD containing all the sequences of 4 words from the contracted corpus...Then, we repeatedly define mdda for each sequence of 4 variables in the ordered set: x1, ...x20. That is we define 16 MDDs. Next, we successively intersect the MDDs. This means that we intersect the MDD defined on x1, .., xi with the MDD defined on xi 2, ..., xi+1 for obtaining the MDD defined on x1, .., xi+1. For intersecting a pair of MDDs defined on different variables we modify them by adding variables accepting all the possibles values. More precisely, the MDD defined on x1, .., xi is transformed into the MDD defined on x1, .., xi+1 where each values of xi+1 is compatible with any path of the first MDD. This corresponds to a duplication of the last layer. |