Sheet 4

Task 1

Recall the definition of domain consistency and relaxed domain consistency such as bound($\mathbb{Z}$), range, and bound(${D}$) consistency. What is the consistency level of the following CSPs?

Task 2

Let $X = \{x, y, z\}$ and $D(x)=\{3,4,5\}, D(y)=\{0,1,2,3\},D(z)=\{1,5\}$. Define one or more propagators implementing the constraint $x\leq y$. Compute the propagator on the constraint store defined. Is the propagator strong idempotent? Is it weak idempotent?

Task 3

Define a propagator for $x+y=d$ and then for $ax+by=d$. Finally, generalize it to the linear equality $\sum a_i x_i = d$.

• Is it necessary to perform several iterations of your propagator? Is it idempotent?

• What type of consistency it produces? (domain or bound consistency level?)

• Apply the propagator to the following example: $x=3y+5z$, $D(x)={2..7},D(y)={0..2},D(z)={-1..2}$. Compare the result with your answer to the previous point.

Task 4 - Usefulness of Weak Idempotency

Assume $V = {x, y}$ and $D(x)=[0 .. 3], D(y)= [0 .. 5]$ Consider the constraint $3x = 2y$ and the propagator $p_{32}$ \(\begin{array}{l} p_{32} (D)(x) = D(x) \cap \{\lceil(2 \min D(y))/3\rceil ,\ldots, \lfloor(2 \max D(y))/3\rfloor\}\\ p_{32} (D)(y) = D(y) \cap \{\lceil(3 \min D(x))/2\rceil , \ldots , \lfloor(3 \max D(x))/2\rfloor\} \end{array}\)

Apply the propagator three times and state whether the propagator is strong idempotent. If it is not is there a constraint store for which it is weak idempotent?

Task 5

How would you implement a propagator for $\max(x,y) = z$?

Task 6

The element constraint models the following very common situation: we have to decide which among four goods to buy; for each good we have a different price; how to propagate the price while the variable is not yet assigned a good?

• Define a way to handle this situation without using the element constraint.

• Define a propagator for the element$(a,x,y)$ constraint.

• Is it necessary to perform several iterations of your propagator? Is it idempotent?

• What type of consistency it produces? (domain or bound consistency level?)

• Run your propagator on the following example: $a=[4,5,7,9], D(x)={1,2,3}, D(y)={2..8}$.

• Can you devise a clever data structure that would speed up the propagation? Would it be worth storing the data structure for successive iterations?

• In gecode the element constraint is used also to implement a particular type of channeling, namely, $z=x_y$, where $y$ and $z$ are single variables and $x$ is an array of variables. Write formally the propagators for $x,y,z$ for the constraint $\mathtt{element}(z,x,y)$.

Task 7 - Modelling

Model the following problem and report the model in written form.

Steel is produced by casting molten iron into slabs. A steel mill can produce a finite number, $\sigma$, of slab sizes. Let sizes be expressed in weight. An order has two properties, a colour corresponding to the route required through the steel mill and a weight. Given $d$ input orders, the problem is to pack the orders onto slabs, the number and size of which are also to be determined, such that the total capacity of the slabs in minimized. In other words, we want to minimize the waste of steel (steel produced in addition to the actual sizes of orders). This assignment is subject to two further constraints:

Capacity constraints:

The total weight of orders assigned to a slab cannot exceed the slab capacity.

Colour constraints:

Each slab can contain at most $p$ of $k$ total colours ($p$ is usually 2). The colour constraints arise because it is expensive to cut up slabs in order to send them to different parts of the mill.

The above description is a simplification of a real industrial problem. For example, the problem may also include inventory matching, where surplus stock can be used to fulfil some of the orders.

A numerical example:

$\sigma=3, d=5, k=3, p=2$. Slab sizes = {12, 10, 7} (note, we can use more than one slab of a certain size and we do not need to use all slab sizes).

  ------- --- --- --- --- ---
  Order    1   2   3   4   5
  Size     5   8   3   4   6
  Color    1   3   2   1   2
  ------- --- --- --- --- ---

A solution:

  --------------- ------- ---- --- -- --
  Slab Capacity     12     10   7     
  Orders           1,3,4   2    5     
  Load              12     8    6     
  Loss               0     2    1     
  --------------- ------- ---- --- -- --

Task 8 - Reviewing each others’ work

Pulling your git repository you will find added the directory asg1/problem-0/others. It contains all projects submitted for Assignment 1. Your task is to review the projects with particular care to the following elements:

• performance: have the results been validated? how does the quality of the solutions rank with respect to the others reports? Are the time limit and the computational resources reported and equal among the reports?
• model: the way constraints are written, are they concise and effective or hardcoded and specific? If original, is the model sensible?
• description: is the language precise with use of proper terminology and mathematical symbols to make concepts clear or is it vague and unclear? Is the document well structured?

Submit your ranked list (ties are possible) to this pool. The pool closes Monday, October 16, 2023 at 14:00.