Implementation and Evaluation of a Compact-Table Propagator in Gecode

In constraint programming, which is a programming paradigm for solvingcombinatorial(optimisation) problems, relations among variables are expressed using constraints —one suchuseful constraint is Table, which expresses the possible combinations that thevariables cantake as a set of tuples. All constraints have a propagation algorithm, whose purpose istoimplement the reasoning for a particular constraint. Gecode [7], which is anopen-sourceconstraint-programming solver written in C++ with state-of-the-art performance,currently hastwo propagation algorithms for the Table constraint, and one for a closely relatedconstraintcalled Regular. In this bachelor dissertation, a new propagation algorithm for theTableconstraint, called compact-table, first proposed in [6], is for the first time designedandoptimised for, and implemented and evaluated in Gecode. The implementation isevaluated on alarge variety of benchmarks, and the results indicate that compact-table outperformstheexisting propagators for Table in Gecode, as well as the propagator for the Regularconstraint.These results suggest that compact-table should be included in Gecode