DM841 - Heuristics and Constraint Programming for Discrete Optimization
Obligatory Assignment 2, Fall 2016 [pdf format]

• This is the second of two preparatory assignments on constraint programming. The assignment is compulsory with pass/fail evaluation.
• The aim of this assignment is to work with pen and paper on the concepts and definitions of local consistency and propagation discussed in class.
• You are allowed to discuss with your peers but the final submission must be individual.
• This document is best read in the PDF format.
• The submission is electronic at http://valkyrien.imada.sdu.dk/DOApp/.
• You have to hand in one file in PDF format containing your responses to the tasks below. You can handwrite your answers and scan them. Alternatively, source code for the figures and tables is linked below.
• The assignment requires that you have read the slides from the class 18. Questions on that material and on the assignment will be taken up in the class of Monday 24/10.

Consistency, Propagation, and Search

The following assignment was posed in a written exam by Prof. Pierre Flener for the course on Constraint Programming at Uppsala University.

Consider the following CSP and its labelled constraints:

We will look at the execution of the constraint propagation for this problem. The algorithm uses propagator conditions (events), status messages and keeps track of variables whose domains have been modified.

The following propagation choices are imposed:

• Use idempotent propagators achieving bounds(Z) consistency for the arithmetic constraints and domain consistency for the other constraints.
• Post the constraints in the textual order in which they appear above.
• Handle the decision variables in the textual order in which they appear in the CSP above.
• Use a first-in first-out queue (FIFO) for implementing the set Q of propagators that are not known to be at fixpoint. (Note that Q is not a multi-set.)

Upon denoting the propagator of constraint C by p_C(·), address the following tasks:

1. Formalize the propagators in a similar way as seen in class:

   pElement(x,DE)=pElement(D)(x)={                            } ...

2. In the Constraint-Propag fixpoint algorithm seen in the course (slide 15, lecture “Rules Iteration”) one needs to know when propagators are to be executed. For each constraint C, give (without proof) the set PropConds(·) of conditions that should trigger the scheduling of the propagators of C ∈ C , as a strictly tighter CSP might then be obtained. Each propagator condition is of the form ‘Any(α)’, ‘Fixed(α)’, or ‘Min/Max(α)’, where α is a decision variable of C. Write ‘(none)’ rather than nothing, where appropriate. Write the most general condition (eg, Any() is more general than Min/Max()).
   PropConds(c) = {                            }
   PropConds(d) = {                            }
   PropConds(e) = {                            }
   PropConds(f) = {                            }
3. Using a procedure like the Constraint-Propag fixpoint algorithm, perform the pre-search propagation to compute the fixpoint of the root of the search tree. Fill in the data in a table like Table 1 for the initialisation (in the first row) and every pre-search step of your Constraint-Propag. (The array argument of the Element constraint is indexed from 1, not from 0.) Write the status message of the propagators after their execution as precisely as possible, the options being ‘AtFixpt’, ‘Unknwon’ (short for “not known to be at fixpoint”), ‘Subsumed’ and ‘Failed’. In addition, write the modification event that occurs. The modification event is of the form ‘None(α)’, ‘Failed(α)’, ‘Fixed(α)’, ‘Min/Max(α)’, or ‘Any(α)’, where α is a decision variable of the propagated constraint. Write ‘(none)’ rather than nothing, where appropriate. Finally, write the dependant propagators that are triggered by the events occurred and how the new queue of propagators will look like.
4. Indicate what changes in your answers to the previous sub-tasks when instead achieving domain consistency for all the constraints. Why? (Note that you are not asked to fill in another table.)

---

Element( 1 2 3 4 5 6 2 1 8 2 1 0 ,v,x)   (c),      v + x ≤ 7   (d),      w · w ≤ 5   (e),      Distinct({v,w,x})   (f)
Chosen		Status	Modification	Dependent	Non-subsumed	FIFO queue Q
prop.	Resulting DE	message	events	prop.s DepProps	propagators R	of propagators
(none)	v ↦ {},  w ↦ {},  x ↦ {}	(none)	(none)	(none)	{}	[]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]
	v ↦ {   },  w ↦ {   },  x ↦ {   }			{      }	{       }	[       ]

Table 1: Latex source code for this table.

---

1. If the pre-search propagation of sub-task 3. has not solved the problem, then draw (below) the search tree with all the solutions, with pairs of non-subsumed propagator sets and domain extensions as nodes, and decisions (which are constraints) as labelled arcs. The previous choices in this task and the following branching heuristics are imposed:
   • Use largest-minimum variable selection (called INT_VAR_MIN_MAX in Gecode).
   • Use bottom-up value selection (called INT_VAL_MIN in Gecode).
   Continue to use the table on the previous page when propagating a branching decision or a constraint, and mark there the starting row of each call to Constraint-Propag.

---

Figure 1: Latex source code for this figure.

---