Modelling

A problem is a Model: variables with finite integer domains, and constraints over them. Everything else in the library starts from a model.

Variables

int_vars creates variables. Given a number it returns a list, given a shape it returns nested lists, so a roster of 3 nurses over 5 days is a 3 by 5 grid.

import pyaicad as ac

DAYS, NURSES = 5, 3
OFF, DAY, NIGHT = 0, 1, 2

model = ac.Model()
roster = model.int_vars((NURSES, DAYS), domain=[OFF, DAY, NIGHT])
model.num_vars
15

roster[n][d] is the shift of nurse n on day d. Variables have no names: you keep the lists that int_vars returned.

Constraints

Constraints are built by functions and added to the model with add, one at a time or as any iterable. The available ones are all_different(), not_equal(), equal(), among(), at_least(), sum_equals(), gcc(), regular(), table() and disjunctive().

# Every day has exactly one nurse on the night shift and one or two on the day shift.
for d in range(DAYS):
    column = [roster[n][d] for n in range(NURSES)]
    model.add(ac.gcc(column, {NIGHT: (1, 1), DAY: (1, 2)}))

# A nurse works at most five days a week.
model.add(ac.among(row, [DAY, NIGHT], 0, 5) for row in roster)

# The first nurse is on leave on the last day.
model.add(ac.equal(roster[0][DAYS - 1], OFF))

regular states a pattern on a sequence of variables with an automaton. Here, a night shift is never directly followed by a day shift. State 0 is “not after a night”, state 1 is “after a night”; the columns of the table are the sorted values of the domain (off, day, night), and None forbids a transition.

after_night = [
    [0, 0, 1],     # state 0: off -> 0, day -> 0, night -> 1
    [0, None, 1],  # state 1: off -> 0, day is forbidden, night -> 1
]
model.add(ac.regular(row, after_night, initial_state=0, accepting_states=[0, 1]) for row in roster)

len(model.constraints)
12

Checking an assignment

An assignment lists one value per variable, in the order of model.variables. model.check tells whether it satisfies every constraint, and is_constraint_satisfied whether it satisfies one.

everyone_off = [OFF] * model.num_vars
print("everyone off is a solution:", model.check(everyone_off))

violated = [c for c in model.constraints if not model.is_constraint_satisfied(c, everyone_off)]
print(len(violated), "of", len(model.constraints), "constraints are violated")
everyone off is a solution: False
5 of 12 constraints are violated

Finding a solution is the job of the next chapters.