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

Prepare the following exercises for discussion in class on Monday 6th February 2011.

The topic of the exercises is modeling, which in this course consists in identifying variables, domains, constraints and objective functions that formulate the problem and expressing this in a way that allows the solution by available software.

Exercise 1

Model as MIP the following cases:

• a feasibility region that is given by the union of two disjoint polytopes that is: {x | Ax ≤ b ∨ Cx ≤ d}.
• the logical conditions on binary variables x_i, i=1,…,4:
  • ¬ x₁ ∨ x₂ ∨ x₃
  • x₁ ∧ x₂
  • (x₁∧ x₂) ⇒ (x₃∧ x₄)
• a piecewisely linearized general nonlinear function g(x) of a single variable x. Let g(x) be continuous and x be within the interval [a₀,a_m]. Let f(x) be the piecewise linear function of g(x), where the interval [a₀,a_m] is partitioned into m small intervals via the break points [a₀,a₁,…,_m], where a₀ < a₁ < … < a_m as shown in Figure 1.

  ---

  

  Figure 1: A general nonlinear function g(x) and its piecewise linearization f(x)

  ---

Exercise 2

Model as MIP and as CP the following progressive party problem. It consists in timetabling a party at a yacht club. Certain boats are to be designated hosts, and the crews of the remaining boats in turn visit the host boats for several successive half-hour periods. The crew of a host boat remains on board to act as hosts while the crew of a guest boat together visits several hosts. Every boat can only host a limited number of guests at a time (its capacity) and crew sizes are different. There are six time periods. A guest boat cannot not revisit a host and guest crews cannot meet more than once. The problem facing the rally organizer is that of minimizing the number of host boats.

Exercise 3

Formulate the problem of finding the chromatic number of a graph as a MIP and as a CP problem.

Exercise 4

The n-queens problem asks to place n queens on a chess board such that the queens do not attack each other.

• Give a CP model for the problem
• Give at least one redundant constraints
• Describe a possible branching rule
• Identify all possible symmetries

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 5

Model the following problem as a CP problem. The rack configuration problem consists of plugging a set of electronic cards into racks with electronic connectors. Each card plugged into a rack uses a connector. In order to plug a card into a rack, the rack must be of a rack model.

Each card is characterized by the power it requires. Each rack model is characterized by the maximal power it can supply, its number of connectors, and its price. The problem is to decide how many of the available racks are actually needed, and which rack is of which rack model model such that

• every card is plugged into one rack
• the total power demand and the number of connectors required by the cards does not exceed that available for a rack
• the total price is minimized.

Exercise 6

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. implement the model in gecode-python;
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=t₁, cd=t₂, t₁t₂=711; 2) ab=t₁, t₁c=t₂, t₂d=711.