undefined | Better HN

0 pointspolivier2y ago0 comments

I'm not too familiar with MDD constraints, but there may indeed be better ways to model this. In particular, I'd be very curious to see if any improvement can be achieved using regular constraints (one for each row/column).

PS: I remember meeting you during the poster display at the CP2019 conference at UCONN. We discussed the difficulty of finding solutions for the Nmbr9 game because there were too many propagators. It's a small world!

0 comments

1 comments · 1 top-level

mzl2y ago

The key point for all of MDD, smart table, compressed tables, the case constraint, and regular expression and finite automata constraints is the ability to compress don't-care information, which essentially gives one reification for a low cost.

The implementation of a regular constraint can in essence be an MDD propagator (the implementation unfolds the automata into a layered graph, which is mostly isomorphic with an MDD), however it will depend on the implementation how efficient it is. In particular, if the original finite automata is already of an MDD shape with layers, some implementations (including the one in Gecode) will create too many nodes by creating all nodes for all layers.

Fun, didn't make that connection. Yes, it is a small world.

j / k navigate · click thread line to collapse