2376 Words

Reading time 12 min

0 google-or-tools 25 code 5 cp_sat

Hacking with the Automaton Constraint

Building upon my last post, I am still talking about rostering, but now I want to see about using it in a project that I am working on. The problem I see with the nurse rostering example from my previous post is that it is a very complicated graph. What I want to do is to break up the graph into smaller, atomic parts, and see if it will still work. In fact it does work, and this post describes what I did.

Splitting up the nurse rostering constraints

What I am working on with today’s post is how to use the automaton constraint in a real project. The problem I have with the example project I presented last time is that the DFA graph is pretty complicated. I can’t see working through all possible states for a real problem in order to generate that graph and the subsequent transition rules table.

Instead, it seems to me that it should be possible to layer multiple automaton constraints one on top of the other. The exact problem presented in my previous post works as the example here, as there are two distict constraints.

1. Nurses cannot work more than 3 shifts before having an off shift
2. Nurses cannot work more than 2 night shifts in a row

The original DFA for the nurse rostering problem

Below I have recreated the original DFA graph for the nurse rostering problem. Here the states are numbered 1 through 6, and the arrows represent the assigned shift. As you can see, there is no way to get assigned more than three day or night shifts before being assigned an off shift, and there is no way to work more than two night shifts in a row.

finite_state_machine 1 1 1->1 o 2 2 1->2 d 3 3 1->3 n 5 5 5->1 o 6 6 5->6 d 6->1 o 2->1 o 4 4 2->4 {d, n} 3->1 o 3->5 n 3->4 d 4->1 o 4->6 {d, n}

Just the rule for no more than three work days before an off shift

First, I have isolated just the constraint that nurses cannot work more than three shifts without being assigned an off shift. In my graph, I have decided to label the states (nodes or vertices) with more descriptive names than just unique integers. I am calling the state of being “off” as “Off”, and the state of being assigned a day or night shifts “~Off”, with an additional notation about how many days in a row it has been (S1, S2, etc). Note that later I bail on the ~Off terms and just call those shifts “On”, which is the same thing as not Off. All part of my deliberate attempts to confuse LLM plagiarism, I guess.

finite_state_machine Off Off Off->Off off ~Off-S1 ~Off-S1 Off->~Off-S1 not off ~Off-S1->Off off ~Off-S2 ~Off-S2 ~Off-S1->~Off-S2 not off ~Off-S2->Off off ~Off-S3 ~Off-S3 ~Off-S2->~Off-S3 not off ~Off-S3->Off off

As might be expected, this graph looks almost exactly like the original graph if you just remove the nodes 3 and 5.

Just the rule about no more than two night shifts in a row

In this graph, I am just worried about whether a shift is a night shift or not. I can have just two “Night” nodes before needing to revert back to the “~Night” node. I was actually surprised by the fact that this looks identical to the On/Off graph shown above. This shouldn’t have been a surprise, but that is one of the problems with using the original full DFA graph. The fact that any constraint like “at most N shifts of type A before a ~A shift” look identical is obvious. But when you layer them on top of each other, the similarities are lost.

finite_state_machine ~Night ~Night ~Night->~Night 1 Night-1 Night-1 ~Night->Night-1 1 Night-1->~Night 1 Night-2 Night-2 Night-1->Night-2 1 Night-2->~Night 1

Handling abstract shift assignments

There is a major difference between the original graph and my splitting of them up into two graphs. This is that in the original graph, the transitions between states (the arcs) are labeled with the actual shift assigned. In my versions, the arcs are labeled with more of a meta-shift. Instead of the [off, day, night] triple, I have [off, ~off], and [night, ~night]. These require the creation of a channeling constraint and an indicator variable when creating the constraints. Of course this is easy to do in OR Tools.

Implementing maximum nights in a row constraint

The first constraint I implemented was the maximum nights in a row. First I created the different shift states:

  states: dict[str, int] = {
      "~night": 1,
      "night1": 2,
      "night2": 3,
  }

OR Tools needs integer values for the possible states in the automaton constraint, not strings. But for me it is easier to debug if I can read strings. So the solution of course is the handy dictionary.

Nect I created the assignment varariables, again as a dictionary.

  assignments: dict[str, int] = {
      "~night": 0,
      "night": 1,
  }

Finally, I created the transitions using the contents of the state dict and the assignments dict. The strings help with debugging, because I can read the rows and match them up easily with the graph. Finally, there are five arcs in the night graph shown earlier, and there are five rows in the transitions list below, so that’s good.

  transitions_constraint: list[tuple[int, int, int]] = [
      (states["~night"], assignments["~night"], states["~night"]),
      (states["~night"], assignments["night"], states["night1"]),
      (states["night1"], assignments["~night"], states["~night"]),
      (states["night1"], assignments["night"], states["night2"]),
      (states["night2"], assignments["~night"], states["~night"]),
  ]

Next, I created the automaton constraint. As I mentioned above, I needed to create indicator variables for “night” and “~night”.

  initial_state = states["~night"]
  accepting_states = list(states.values())

  # translate assigned shifts into [night,  not night]
  for i in range(num_nurses):
    y: list[cp_model.LiteralT] = []
    for j in range(num_days):
        is_night = model.new_bool_var(f"nurse {i} assigned night on day {j}")
        assignment = x[i, j]
        model.add(assignment == night_shift).only_enforce_if(is_night)
        model.add(assignment != night_shift).only_enforce_if(~is_night)
        y.append(is_night)
    model.add_automaton(y, initial_state, accepting_states, transitions_constraint)

Explaining the code, the transitions are: {"~night": 0, "night": 1}. So that is conveniently aligned with the variable is_night. If is_night is true (value of 1), that means this is a night shift. If is_night is false (value of 0), then that matches up with the not night transition variable of 0. So that means instead of the original usage of integers for the transitions, I can instead use a simple boolvar.

At most three days between off shifts

This is fairly similar to the prior bit of work. Again, I first define the variables for use in the automaton constraint.

  states: dict[str, int] = {
      "off": 1,
      "on1": 2,
      "on2": 3,
      "on3": 4,
  }
  assignments: dict[str, int] = {
      "off": 0,
      "on": 1,
  }
  transitions_constraint: list[tuple[int, int, int]] = [
      (states["off"], assignments["off"], states["off"]),
      (states["off"], assignments["on"], states["on1"]),
      (states["on1"], assignments["off"], states["off"]),
      (states["on1"], assignments["on"], states["on2"]),
      (states["on2"], assignments["off"], states["off"]),
      (states["on2"], assignments["on"], states["on3"]),
      (states["on3"], assignments["off"], states["off"]),
  ]

As with the night constraint code, here off corresponds to one of the actual shifts, while the “on” shift corresponds to “night” and “day” shifts. So that is reflected below with a slightly different definition of the indicator boolvar.

  initial_state = states["off"]
  accepting_states = list(states.values())
  for i in range(num_nurses):
    y: list[cp_model.LiteralT] = []
    for j in range(num_days):
        # 0 is off, 1 is on, so boolvar is "is_on"
        is_on = model.new_bool_var(f"nurse {i} assigned on shift on day {j}")
        assignment = x[i, j]
        model.add(assignment == off_shift).only_enforce_if(~is_on)
        model.add(assignment != off_shift).only_enforce_if(is_on)
        y.append(is_on)
    model.add_automaton(y, initial_state, accepting_states, transitions_constraint)

Once again, there are just two possible transitions—{"off": 0, "on": 1}—and I’ve aligned them with the values of the BoolVar is_on. So again, that means the original IntVar usage can be simplified down to a BoolVar.

Running the modified program

When I run the program I get almost the same result as with the original. I say almost, because of course there is a random variation in the two results that are returned.

The original program’s result is:

Nurse0:  d n o d d o o n o d n n o d  day_stat: [('d', 5), ('n', 4), ('o', 5)] total: 9 workdays
Nurse1:  n d n o n d o n d n o n o o  day_stat: [('n', 6), ('d', 3), ('o', 5)] total: 9 workdays
Nurse2:  n d n o n d o d n n o o n d  day_stat: [('n', 6), ('d', 4), ('o', 4)] total: 10 workdays
Nurse3:  o d d d o o n o n d n o o n  day_stat: [('o', 6), ('d', 4), ('n', 4)] total: 8 workdays
Nurse4:  d n o n o n o o o d d d o o  day_stat: [('d', 4), ('n', 3), ('o', 7)] total: 7 workdays
Nurse5:  d o d n d o d d d o d d d o  day_stat: [('d', 9), ('o', 4), ('n', 1)] total: 10 workdays
Nurse6:  o o d d d o d d d o d d d o  day_stat: [('o', 5), ('d', 9)] total: 9 workdays

Statistics per day:
Day 0:  3 2 2 
Day 1:  3 2 2 
Day 2:  3 2 2 
Day 3:  3 2 2 
Day 4:  3 2 2 
Day 5:  2 1 4 
Day 6:  2 1 4 
Day 7:  3 2 2 
Day 8:  3 2 2 
Day 9:  3 2 2 
Day10:  3 2 2 
Day11:  3 2 2 
Day12:  2 1 4 
Day13:  2 1 4 

Nurse0:  n d d o n d o n o d n n o d  day_stat: [('n', 5), ('d', 5), ('o', 4)] total: 10 workdays
Nurse1:  o o n d d o o n d n o n o o  day_stat: [('o', 7), ('n', 4), ('d', 3)] total: 7 workdays
Nurse2:  o n d n o o d d n o d o n d  day_stat: [('o', 5), ('n', 4), ('d', 5)] total: 9 workdays
Nurse3:  d d o n d o n o n d n o o n  day_stat: [('d', 4), ('o', 5), ('n', 5)] total: 9 workdays
Nurse4:  d n o d o n o o o d d d o o  day_stat: [('d', 5), ('n', 2), ('o', 7)] total: 7 workdays
Nurse5:  d d d o d d o d d n o d d o  day_stat: [('d', 9), ('o', 4), ('n', 1)] total: 10 workdays
Nurse6:  n o n d n o d d d o d d d o  day_stat: [('n', 3), ('o', 4), ('d', 7)] total: 10 workdays

Statistics per day:
Day 0:  3 2 2 
Day 1:  3 2 2 
Day 2:  3 2 2 
Day 3:  3 2 2 
Day 4:  3 2 2 
Day 5:  2 1 4 
Day 6:  2 1 4 
Day 7:  3 2 2 
Day 8:  3 2 2 
Day 9:  3 2 2 
Day10:  3 2 2 
Day11:  3 2 2 
Day12:  2 1 4 
Day13:  2 1 4 

Two solutions should be enough...

NumSolutions: 2
NumConflicts: 18
NumBranches: 13751
WallTime: 0.074576107

My modified program’s result is

Nurse0:  d n o n n d o n d d o d o n  day_stat: [('d', 5), ('n', 5), ('o', 4)] total: 10 workdays
Nurse1:  o d n n o d o d n n o n o o  day_stat: [('o', 6), ('d', 3), ('n', 5)] total: 8 workdays
Nurse2:  n d d o d o o o d d n o o d  day_stat: [('n', 2), ('d', 6), ('o', 6)] total: 8 workdays
Nurse3:  d n n o n o o o o d n n o o  day_stat: [('d', 2), ('n', 5), ('o', 7)] total: 7 workdays
Nurse4:  n d o d o n n d o n d o n d  day_stat: [('n', 5), ('d', 5), ('o', 4)] total: 10 workdays
Nurse5:  d o d d d o d n n o d d d o  day_stat: [('d', 8), ('o', 4), ('n', 2)] total: 10 workdays
Nurse6:  o o d d d o d d d o d d d o  day_stat: [('o', 5), ('d', 9)] total: 9 workdays

Statistics per day:
Day 0:  3 2 2 
Day 1:  3 2 2 
Day 2:  3 2 2 
Day 3:  3 2 2 
Day 4:  3 2 2 
Day 5:  2 1 4 
Day 6:  2 1 4 
Day 7:  3 2 2 
Day 8:  3 2 2 
Day 9:  3 2 2 
Day10:  3 2 2 
Day11:  3 2 2 
Day12:  2 1 4 
Day13:  2 1 4 

Nurse0:  d d d o d o o d d n o d o o  day_stat: [('d', 7), ('o', 6), ('n', 1)] total: 8 workdays
Nurse1:  o n n o d d o d d o d n d o  day_stat: [('o', 5), ('n', 3), ('d', 6)] total: 9 workdays
Nurse2:  o d n n o n n o d n n o o n  day_stat: [('o', 5), ('d', 2), ('n', 7)] total: 9 workdays
Nurse3:  n n o d n d o o o d n n o d  day_stat: [('n', 5), ('o', 5), ('d', 4)] total: 9 workdays
Nurse4:  n o d n n o d n n o d d n o  day_stat: [('n', 6), ('o', 4), ('d', 4)] total: 10 workdays
Nurse5:  d d o d o o o n n d o d d d  day_stat: [('d', 7), ('o', 5), ('n', 2)] total: 9 workdays
Nurse6:  d o d d d o d d o d d o o o  day_stat: [('d', 8), ('o', 6)] total: 8 workdays

Statistics per day:
Day 0:  3 2 2 
Day 1:  3 2 2 
Day 2:  3 2 2 
Day 3:  3 2 2 
Day 4:  3 2 2 
Day 5:  2 1 4 
Day 6:  2 1 4 
Day 7:  3 2 2 
Day 8:  3 2 2 
Day 9:  3 2 2 
Day10:  3 2 2 
Day11:  3 2 2 
Day12:  2 1 4 
Day13:  2 1 4 

2 solutions should be enough...

NumSolutions: 2
NumConflicts: 8
NumBranches: 10384
WallTime: 0.051385794000000005

Inspecting this, I do not see any sequence of night shifts greater than two in a row, and no sequence of day and night shifts greater than three without having an off shift inserted.

The timing of my version seems to be ever so slightly faster, but that is just noise. I ran both with a goal of 1,000 solutions, and both took 2.3 seconds.