DM826 - Modeling and Solving Constrained Optimization Problems
Sheet 1, Spring 2011 [pdf format]

Prepare the following exercises for discussion in class on Friday 11th February 2011.



Exercise 1 Show how to model via MIP a feasibility region that is given by the union of two disjoint polytopes that is: {x | Ax ≤ b ∨ Cx ≤ d}.



Exercise 2 In class we discussed the n-queens problem. In gecode you find the model implemented as one of the examples. Look at the example and compare on the basis of time, number of nodes and number of failures the following alternatives:

  1. [a)] the use of global constraints (full, partial, no use);
  2. the consistency level (look at the documentation of the global constraints to understand how to declare this);
  3. a few different choices for branching



Exercise 3 Grocery puzzle: a kid goes into a grocery store and buys four items. The cashier charges 7.11 $, the kid pays and is about to leave when the cashier calls the kid back, and says ”Hold on, I multiplied the four items instead of adding them; I’ll try again; Hah, with adding them the price still comes to 7.11 $”. What were the prices of the four items?

  1. [a)] model the problem in CP;
  2. look at the example in gecode;
  3. compare on the basis of time, number of nodes and number of failures different choices for branching ;
  4. symmetry breaking avoids searching for solutions that are obtained by simple permutation of previously visited states. In this specific problem the symmetry is broken by imposing an ordering in the prices of the four items. Check if the contribution of this breaking symmetry is relevant;
  5. observe that 711 is has a prime factor 79. How could you use this fact in the CP model?
  6. Let a, b, c, d be the cost of the four items. Compare two models that decomposes the multiplication constraint abcd=711 into 1) ab=t1, cd=t2, t1t2=711; 2) ab=t1, t1c=t2, t2d=711.



Exercise 4 A Latin square of order n is an n × n array filled with n different Latin letters (or numbers or colors), each occurring exactly once in each row and exactly once in each column. In statistics, Latin Squares are used to design experiments where each letter represents a sample position. A Latin hypercube is the generalization of this concept to an arbitrary number of dimensions, whereby each sample is the only one in each axis-aligned hyperplane containing it. When sampling a function of N variables, the range of each variable is divided into M equally probable intervals. M sample points are then placed to satisfy the Latin hypercube requirements; note that this forces the number of divisions, M, to be equal for each variable. Formulate the problem of finding a Latin Square of order n and a Latin hypercube with M points in N dimensions as a Constraint Satisfaction Problem and write the model in the notation used in [A2].



Exercise 5 Formulate the problem of finding the chromatic number of a graph as a Constrained Optimization Problem.



Exercise 6 Consider the IMADA elective course timetabling problem:

  1. [a)]Read the problem definition and understand the MIP model given in ZIMPL (see links from Lecture 1).
  2. Formulate the problem as a CP model
  3. Devise new (soft) constraints that take into account the welfare of each individual student
  4. Implement your model in Comet and experiment with the data made available for the current and the next quarter.