The ${\rm\scriptsize REGULAR}$ Constraint

Let's see a new (strange) global constraint

$${\rm\scriptsize REGULAR}(X, T, s_0, F)$$

• The constraint ensures that the sequence of the $X$ variables...
• ...Is compliant with a given Deterministic Finite Automaton (DFA)
  • $T$ specifies the valid state transitions: $(s_{cur}, v, s_{next})$
  • $s_0$ is the initial state
  • $F$ is the set of accepting states

In detail, the constrain is satisfied iff:

• All transitions are valid
• When the sequence ends, the DFA is in an accepting state

The ${\rm\scriptsize REGULAR}$ Constraint

Consider this example:

• The starred state is $s_0$ (initial state)
• The double-circled states are those in $F$ (accepting states)

This is an example of a valid sequence (6 variables)

The ${\rm\scriptsize REGULAR}$ Constraint

Consider this example:

• The starred state is $s_0$ (initial state)
• The double-circled states are those in $F$ (accepting states)

This an invalid sequence (forbidden transition)

The ${\rm\scriptsize REGULAR}$ Constraint

Consider this example:

• The starred state is $s_0$ (initial state)
• The double-circled states are those in $F$ (accepting states)

This an invalid sequence (the last state is not in $F$)

The ${\rm\scriptsize REGULAR}$ Constraint

Consider this example:

• The starred state is $s_0$ (initial state)
• The double-circled states are those in $F$ (accepting states)

As usual, the ${\rm\scriptsize REGULAR}$ constraint is capable of filtering

• In particular, it can enforce GAC on the $X$ variables

The ${\rm\scriptsize REGULAR}$ Constraint

The constraint can sometimes be very useful:

• Main example: complex regulations (laws) in work shift scheduling

Hover, the constraint is not always provided by solvers

The reason is that ${\rm\scriptsize REGULAR}$ can be decomposed

• We introduce a state variable $Y_i$ for each $X_i$...
• ...Plus an additional $Y_{n}$ variable for the finale state
• We enforce valid transitions by posting multiple ${\rm\scriptsize TABLE}$ constraints
• Each ${\rm\scriptsize TABLE}$ constraint regulates a single transition

The ${\rm\scriptsize REGULAR}$ Constraint

The ${\rm\scriptsize REGULAR}$ Constraint

Or-tools provides ${\rm\scriptsize REGULAR}$ via the API:

slv.TransitionConstraint(X, T, s0, F)

Where:

• X is a list with the $X_i$ variables
• T is a "matrix" (list of lists) with the allowed transitions
• s0 is the index of the initial state
• F is a list with the accepting states

The solver builds the decomposition automatically

Constraint Systems

A Shift-Scheduling Problem

A Shift-Scheduling Problem

Consider the following problem (by Tim Curtois):

We need to plan the working shifts for the employees of a company

• The planning horizon $eoh$ is known (in days)

Each type of working shift $k$:

• Has a given duration $l_k$ (in minutes)
• Cannot be followed by shifts in a given list $I_k$

Each worker $i$:

• Works a single shift type per day $j$ (or takes a day off)
• Should work at most $M_{i,k}$ shifts of type $k$
• Should work at most $D_i$ and at least $d_i$ minutes overall

A Shift-Scheduling Problem

Again, each worker:

• Should work at most $w_i$ week ends
  • For week-end days we have $j \mod 7 = 5 \text{ or } 6$
  • A week end is worked if there is a shift on Saturday or Sunday
• Should work at least $c_i$ and at most $C_i$ consecutive shifts
• Should take at least $g_i$ consecutive days off
• Has a set of mandatory days off $V_i$ (vacation)

There are positive preferences $h$ over shifts:

• If worker $i_h$ does not take shift $k_h$ on day $j_h$, we pay a penalty $w^p_h$

There are negative preferences $h$ over shifts:

• If worker $i_h$ does take shift $k_h$ on day $j_h$, we pay a penalty $w^n_h$

A Shift-Scheduling Problem

There are cover requirements $h$ for shifts and days:

• Let $y_{h}$ be the number of shifts $k_h$ on day $j_h$
• If $y_h$ is less than a given requirement $r_h$, we pay $w^u_h (r_h - y_h)$
• If $y_h$ is greater than a given requirement $r_h$, we pay $w^o_h (y_h - r_h)$
• The penalty $u_h$ is much greater than the penalty $o_h$

About the number of entities:

• Let $n_e$ be the number of workers
• Let $n_s$ be the number of shift types
• Let $n_p$ be the number of positive preferences
• Let $n_n$ be the number of negative preferences
• Let $n_c$ be the number of cover requirements

A Shift-Scheduling Problem

This is a rather complex problem

• Writing a model takes time (more than we have in this session)...
• So we will see one possible approach together

The main variables are:

$$\begin{align} & x_{i,j} \in \{0..n_s\} & \forall i = 0..n_e-1, j = 0..eoh-1 \\ & w_{i,j} \in \{0, 1\} & \forall i = 0..n_e-1, j = 0..eoh-1 \end{align}$$

• $x_{i,j}$ is the shift type for worker $i$ on day $j$
• $x_{i,j} = n_s$ for a day off
• $w_{i,j} = 1$ if worker $i$ does not take a day off on $j$

Chaining constraints:

$$\begin{align} & w_{i,j} = (x_{i,j} \neq n_s) & \forall i = 0..n_e-1, j = 0..eoh-1 \end{align}$$

A Shift-Scheduling Problem

Compatibility constraints between subsequent shifts:

$$\begin{align} & {\rm\scriptsize TABLE([x_{i,j}, x_{i,j+1}], T)} & \forall i = 0..n_e-1, j = 0..eoh-2 \end{align}$$

• Where $T$ contains all the valid transitions, i.e.

$$(k', k") \in T \text{ iff } k' = n_s \vee k" = n_s \vee k" \notin I_{k'}$$

Maximum number of shift types per worker:

$$\begin{align} & {\rm\scriptsize GCC}(X_{i,:}, [0..n_s], [0..0], [M_{i,0}, M_{i,1}, ... \infty]) & \forall i = 0..n_e-1 \end{align}$$

Limits on the number of minutes per worker ($l_{n_s} = 0$):

$$\begin{align} & \sum_{j=0..eoh-1} l_{x_{i,j}} \leq D_i & \forall i = 0..n_e-1 \\ & \sum_{j=0..eoh-1} l_{x_{i,j}} \geq d_i & \forall i = 0..n_e-1 \\ \end{align}$$

A Shift-Scheduling Problem

Maximum number of weekends:

• First we introduce a set of additional variables

$$\begin{align} & W^{we}_{i,h} \in \{0,1\} & \forall i = 0..n_e-1, h = 0..^{eoh}/_7 \end{align}$$

• $W^{we}_{i,h} = 1$ if worker $i$ works on the $h$-th weekend
• Then we define the variable via the constraints:

$$\begin{align} & W^{we}_{i,h} = \max(W_{i,7(h+1)-2}, W_{i,7(h+1)-1}) & \forall i = 0..n_e-1, h = 0..^{eoh}/_7 \end{align}$$

• Then we constraint the sum:

$$\begin{align} \sum_{h = 0..^{eoh}/_7} W^{we}_{i,h} \leq w_i \end{align}$$

Mandatory days off:

$$\begin{align} & x_{i,j} = n_s & \forall i = 0..n_e-1, j \in V_i \end{align}$$

A Shift-Scheduling Problem

Constraint on consecutive days:

${\rm\scriptsize REGULAR}$ on the $W_{i,j}$ variables for each worker $i$

• doX = X days off
• doe = enough days off ("doe" stands for a number)
• wdX = X working days
• wdm = min working days ("wdm" stands for a number)
• wdM = max working days ("wdM" stands for a number)

A Shift-Scheduling Problem

Constraint on consecutive days:

${\rm\scriptsize REGULAR}$ on the $W_{i,j}$ variables for each worker $I$

• Once we reach doe, we stop counting the days off
• No working day allowed in doX before doe is reached
• No day off allowed in wdX before wdm is reached
• No working day allowed one wdM is reached

A Shift-Scheduling Problem

Constraint on consecutive days:

${\rm\scriptsize REGULAR}$ on the $W_{i,j}$ variables for each worker $I$

• HP: infinite days off before and after the planning period
• Hence, doe is the initial state...
• ...And all doX and doe state are accepting...
• ...But only states between wdm and wdM are accepting

A Shift-Scheduling Problem

The penalty for not satisfying positive preferences:

$$\begin{align} & z_p = \sum_{h = 0..n_p-1} w^p_h (x_{i_h, j_h} \neq k_h) \end{align}$$

The penalty for not satisfying negative preferences:

$$\begin{align} & z_n = \sum_{h = 0..n_n-1} w^n_h (x_{i_h, j_h} = k_h) \end{align}$$

The penalty for not satisfying cover preferences:

$$\begin{align} & {\rm\scriptsize COUNT}(X_{:,j}, k_h, y_h) & \forall h = 0..n_c-1 \\ & z_o = \sum_{h = 0..n_c-1} w^o_h \max(y_h - r_h, 0) \\ & z_u = \sum_{h = 0..n_c-1} w^u_h \max(r_h - y_h, 0) \\ \end{align}$$

A Shift-Scheduling Problem

The overall cost function is:

$$\begin{align} \min z = z_p + z_n + z_o + z_u \end{align}$$

The model and two instances are available on the start-kit

• Change the search strategy and solve Instance1 to optimality
  • Pick the branching variables, select the var/value strategy...
  • ...Order the variables based on your ideas
• Then try to find the best possible solution for Instance2
  • The optimal solution is 828...
  • ...See how close you can get!

NOTE: both tasks are difficult!