DM877 - Constraint Programming

Sheet 1

Task 1

Consider the SEND + MORE = MONEY cryptarythm problem see in the classes.

  • Implement the model saw in class and experiments with different heuristics for the search changing:
    • the criterion for selecting which variable to assign first and
    • the criterion for selecting which value to assign first.

  • Formulate another model for the problem (hint: model the arithmetic constraint by means of rest variables)

  • Implement in MiniZinc the alternative models that you have conceived. Compare their solutions. Which is fastest? (print search statistics and compare them).

  • Visualize the search tree

  • Find all solutions for the problem. How many solutions are there? Do all models yield the same number?

  • Model, implement and solve the optimization version in which you have to maximize the value that MONEY gets.

  • Repeat the analysis for the cryptarythm: ten + ten + forty = sixty or the one proposed in the assignments of the course in coursera

  • Compare using lexicographic and first-fail search. Which of the two search strategies is the best in the two problems? Is the conclusion the same?

Task 2

Model and solve in MiniZinc the following problem. A kid goes to a store and buys four items. The cashier: “that makes $7.11”. The kid pays and when he is about to leave the store, the Cashier says: “Hold on, I multiplied! let me add! wow, the sum is also $7.11”. Which are the prices of the four items?