Generating custom propagators for arbitrary constraints.

*(English)*Zbl 1405.68326Summary: Constraint Programming (CP) is a proven set of techniques for solving complex combinatorial problems from a range of disciplines. The problem is specified as a set of decision variables (with finite domains) and constraints linking the variables. Local reasoning (propagation) on the constraints is central to CP. Many constraints have efficient constraint-specific propagation algorithms. In this work, we generate custom propagators for constraints. These custom propagators can be very efficient, even approaching (and in some cases exceeding) the efficiency of hand-optimised propagators.

Given an arbitrary constraint, we show how to generate a custom propagator that establishes GAC in small polynomial time. This is done by precomputing the propagation that would be performed on every relevant subdomain. The number of relevant subdomains, and therefore the size of the generated propagator, is potentially exponential in the number and domain size of the constrained variables.

The limiting factor of our approach is the size of the generated propagators. We investigate symmetry as a means of reducing that size. We exploit the symmetries of the constraint to merge symmetric parts of the generated propagator. This extends the reach of our approach to somewhat larger constraints, with a small run-time penalty.

Our experimental results show that, compared with optimised implementations of the table constraint, our techniques can lead to an order of magnitude speedup. Propagation is so fast that the generated propagators compare well with hand-written carefully optimised propagators for the same constraints, and the time taken to generate a propagator is more than repaid.

Given an arbitrary constraint, we show how to generate a custom propagator that establishes GAC in small polynomial time. This is done by precomputing the propagation that would be performed on every relevant subdomain. The number of relevant subdomains, and therefore the size of the generated propagator, is potentially exponential in the number and domain size of the constrained variables.

The limiting factor of our approach is the size of the generated propagators. We investigate symmetry as a means of reducing that size. We exploit the symmetries of the constraint to merge symmetric parts of the generated propagator. This extends the reach of our approach to somewhat larger constraints, with a small run-time penalty.

Our experimental results show that, compared with optimised implementations of the table constraint, our techniques can lead to an order of magnitude speedup. Propagation is so fast that the generated propagators compare well with hand-written carefully optimised propagators for the same constraints, and the time taken to generate a propagator is more than repaid.

##### MSC:

68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |

##### Keywords:

constraint programming; constraint satisfaction problem; propagation algorithms; combinatorial search
Full Text:
DOI

##### References:

[1] | Bessiere, C., Handbook of constraint programming, 29-83, (2006), Elsevier Science Inc. New York, NY, USA, Ch. Constraint Propagation |

[2] | Jefferson, C.; Miguel, A.; Miguel, I.; Tarim, A., Modelling and solving English peg solitaire, Comput. Oper. Res., 33, 10, 2935-2959, (2006) · Zbl 1086.90070 |

[3] | Bessière, C.; Régin, J.-C.; Yap, R.; Zhang, Y., An optimal coarse-grained arc consistency algorithm, Artif. Intell., 165, 165-185, (2005) · Zbl 1132.68691 |

[4] | Bessière, C.; Régin, J.-C., Arc consistency for general constraint networks: preliminary results, (IJCAI(1), (1997)), 398-404 |

[5] | Cheng, K. C.; Yap, R. H., An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints, Constraints, 15, 2, 265-304, (2010) · Zbl 1204.68188 |

[6] | Lecoutre, C., STR2: optimized simple tabular reduction for table constraints, Constraints, 16, 4, 341-371, (2011) · Zbl 1244.90232 |

[7] | Gent, I. P.; Jefferson, C.; Miguel, I.; Nightingale, P., Data structures for generalised arc consistency for extensional constraints, (AAAI’07: Proceedings of the 22nd National Conference on Artificial Intelligence, (2007), AAAI Press), 191-197 |

[8] | Pesant, G., A regular language membership constraint for finite sequences of variables, (Proceedings of the 10th International Conference on the Principles and Practice of Constraint Programming (CP 2004), (2004)), 482-495 · Zbl 1152.68573 |

[9] | Cheng, K. C.K.; Yap, R. H.C., Maintaining generalized arc consistency on ad-hoc n-ary Boolean constraints, (Proceeding of the 2006 Conference on ECAI 2006, (2006), IOS Press Amsterdam, The Netherlands), 78-82 |

[10] | Lecoutre, C.; Szymanek, R., Generalized arc consistency for positive table constraints, (Principles and Practice of Constraint Programming - CP 2006, (2006)), 284-298 · Zbl 1335.90096 |

[11] | Katsirelos, G.; Walsh, T., A compression algorithm for large arity extensional constraints, (Principles and Practice of Constraint Programming (CP 2007), (2007)), 379-393 |

[12] | Lecoutre, C.; Likitvivatanavong, C.; Yap, R. H.C., A path-optimal GAC algorithm for table constraints, (ECAI 2012 - 20th European Conference on Artificial Intelligence, (2012)), 510-515 · Zbl 1327.68220 |

[13] | Mairy, J.-B.; Van Hentenryck, P.; Deville, Y., An optimal filtering algorithm for table constraints, (CP 2012 - 18th International Conference on Principles and Practice of Constraint Programming, (2012)), 496-511 |

[14] | Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to algorithms, (2001), MIT Press/McGraw-Hill · Zbl 1047.68161 |

[15] | Gent, I. P.; Jefferson, C.; Miguel, I.; Nightingale, P., Generating special-purpose stateless propagators for arbitrary constraints, (Proceedings of 16th International Conference on Principles and Practice of Constraint Programming (CP 2010), (2010)), 206-220 |

[16] | Gent, I. P.; Jefferson, C.; Miguel Minion, I., A fast, scalable, constraint solver, (Proceedings 17th European Conference on Artificial Intelligence (ECAI 2006), (2006)), 98-102 |

[17] | I.P. Gent, C. Jefferson, S. Linton, I. Miguel, P. Nightingale, Finite state automata for the paper Generating Custom Propagators for Arbitrary Constraints, Tech. Rep. CIRCA Preprint 2013/7, University of St Andrews, 2013. · Zbl 1405.68326 |

[18] | Beldiceanu, N.; Carlsson, M.; Debruyne, R.; Petit, T., Reformulation of global constraints based on constraints checkers, Constraints, 10, 4, 339-362, (2005) · Zbl 1103.68804 |

[19] | Schulte, C.; Tack, G., View-based propagator derivation, Constraints, 18, 1, 75-107, (2013) · Zbl 1328.68202 |

[20] | Gent, I. P.; Smith, B. M., Symmetry breaking in constraint programming, (Horn, W., Proceedings of ECAI-2000, (2000), IOS Press), 599-603 |

[21] | Bosch, R.; Trick, M., Constraint programming and hybrid formulations for three life designs, Ann. Oper. Res., 130, 41-56, (2004) · Zbl 1156.90471 |

[22] | Smith, B. M., A dual graph translation of a problem in ‘life’, (Principles and Practice of Constraint Programming (CP 2002), (2002)), 402-414 |

[23] | Chu, G.; Stuckey, P. J.; de la Banda, M. G., Using relaxations in maximum density still life, (Principles and Practice of Constraint Programming (CP 2009), (2009)), 258-273 |

[24] | Linton, S., Finding the smallest image of a set, (Proceedings of ISSAC 04, (2004), ACM Press), 229-234 · Zbl 1134.05302 |

[25] | The GAP Group, GAP - Groups, Algorithms, and Programming, Version 4.5.6; 2012 (http://www.gap-system.org). |

[26] | Wallace, D., Groups, rings and fields, (1998), Springer-Verlag · Zbl 0933.00002 |

[27] | Cohen, D.; Jeavons, P.; Jefferson, C.; Petrie, K. E.; Smith, B. M., Symmetry definitions for constraint programming, Constraints, 11, 2-3, 115-137, (2006) · Zbl 1103.68809 |

[28] | Weisstein, E. W., Immigration |

[29] | Brian’s brain |

[30] | Lecoutre, C.; Hemery, F., A study of residual supports in arc consistency, (IJCAI’07: Proceedings of the 20th International Joint Conference on Artificial Intelligence, (2007), Morgan Kaufmann Publishers Inc. San Francisco, CA, USA), 125-130 |

[31] | Apt, K. R.; Monfroy, E., Constraint programming viewed as rule-based programming, Theory Pract. Log. Program., 1, 6, 713-750, (2001) · Zbl 1066.68518 |

[32] | Abdennadher, S.; Olama, A.; Salem, N.; Thabet, A., ARM: automatic rule miner, (Logic-Based Program Synthesis and Transformation, 16th International Symposium, LOPSTR 2006, (2006)), 17-25 |

[33] | Darwiche, A.; Marquis, P., A knowledge compilation map, J. Artif. Intell. Res., 17, 229-264, (2002) · Zbl 1045.68131 |

[34] | Fahle, T.; Schamberger, S.; Sellmann, M., Symmetry breaking, (Proceedings of Principles and Practice of Constraint Programming (CP 2001), (2001)), 93-107 · Zbl 1067.68631 |

[35] | Frisch, A. M.; Hnich, B.; Kiziltan, Z.; Miguel, I.; Walsh, T., Propagation algorithms for lexicographic ordering constraints, Artif. Intell., 170, 10, 803-834, (2006) · Zbl 1131.68521 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.