C

Part C

Case studies

Christian Schulte, Guido Tack, Mikael Z. Lagerkvist

This part presents a collection of modeling case studies. The case studies are ordered (roughly) according to their complexity.

Basic models. The basic models use classic constraint programming problems in order to demonstrate how typical modeling tasks are done with Gecode. The basic models are:

  • Golomb rulers shows a simple problem with a single distinct constraint and a few rel constraints. As the problem is so well known, it might serve as an initial case study of how to model with Gecode.

  • Magic sequence shows how to use counting constraints (count).

  • Photo alignment shows how to use reified constraints for solving an overconstrained problem.

  • Locating warehouses shows how to use element, linear, and global counting (count) constraints.

  • Nonogram shows how to use regular expressions and extensional constraints.

  • Social golfers presents a case study on modeling problems using set variables and constraints.

Advanced models. The following models are slightly more advanced:

  • Knight’s tour demonstrates a problem-specific brancher inspired by a classic heuristic for a classic problem.

  • Bin packing also demonstrates a problem-specific brancher including techniques for breaking symmetries during branching.

  • Kakuro presents a model that employs user-defined constraints implemented as extensional constraints using tuple set specifications. Interestingly, the tuple set specifications are computed by solving a simple constraint problem.

  • Crossword puzzle presents a simple model using nothing but distinct and element constraints. The simple model is shown to work quite well compared to a dedicated problem-specific constraint solver. This underlines that an efficient general-purpose constraint programming system actually can go a long way.

Note that the first two case studies require knowledge on programming branchers, see Programming branchers.

Acknowledgments. We thank Pierre Flener and Håkan Kjellerstrand for numerous detailed and helpful comments on the case studies. Their comments have considerably improved the presentation of the case studies.