Structured Constraint Programming

Author

Ken Pu

Introduction

Let’s look at ways we can build constraint programs (CP) in a structured way. As a case study, we will model the curriculum requirements of the Computer Science program.

Data

Let’s start with data. The environment is modeled as a database. Let’s build a database to model the curriculum.

data = []
for i in range(4):
    for s in ['Fall', 'Winter']:
        data.append(f"Y{i+1} {s}")

semesters = Series(data, name='semesters')
semesters
0      Y1 Fall
1    Y1 Winter
2      Y2 Fall
3    Y2 Winter
4      Y3 Fall
5    Y3 Winter
6      Y4 Fall
7    Y4 Winter
Name: semesters, dtype: object

The semesters of the curriculum.

data = [
    'CSCI 1030U', 'CSCI 1060U', 'CSCI 1061U', 'CSCI 1062U', 'CSCI 1063U', 
    'CSCI 2000U', 'CSCI 2010U', 'CSCI 2020U', 'CSCI 2040U', 'CSCI 2050U',
    'CSCI 2072U', 'CSCI 2110U', 'CSCI 3010U', 'CSCI 3030U', 'CSCI 3055U', 
    'CSCI 3060U', 'CSCI 3070U', 'CSCI 3090U', 'CSCI 3230U', 'CSCI 3240U', 
    'CSCI 3310U', 'CSCI 3540U', 'CSCI 4020U', 'CSCI 4030U', 'CSCI 4040U', 
    'CSCI 4050U', 'CSCI 4052U', 'CSCI 4055U', 'CSCI 4060U', 'CSCI 4080U', 
    'CSCI 4100U', 'CSCI 4110U', 'CSCI 4140U', 'CSCI 4150U', 'CSCI 4160U', 
    'CSCI 4210U', 'CSCI 4220U', 'CSCI 4230U', 'CSCI 4410U', 'CSCI 4420U', 
    'CSCI 4430U', 'CSCI 4610U', 'CSCI 4620U'
]

courses = Series(data, name='courses')
courses.head()
0    CSCI 1030U
1    CSCI 1060U
2    CSCI 1061U
3    CSCI 1062U
4    CSCI 1063U
Name: courses, dtype: object

Data is needed to model prerequisites and areas of senior courses. For now, let’s get back to these relations laters.

Unknowns

We will also call them independent variables. These are the variables that should be solved to derive the desired solution.

def make_unknowns(model:CpModel)->DataFrame:
    data = np.empty((len(courses), len(semesters)), dtype=object)
    for i,c in enumerate(courses):
        for (j, s) in enumerate(semesters):
            data[i,j] = model.new_bool_var(f"{c}∈{s}?")

    unknown = pd.DataFrame(data, index=courses, columns=semesters)
    return unknown
model = CpModel()
unknown = make_unknowns(model)
unknown.head()
semesters Y1 Fall Y1 Winter Y2 Fall Y2 Winter Y3 Fall Y3 Winter Y4 Fall Y4 Winter
courses
CSCI 1030U CSCI 1030U∈Y1 Fall? CSCI 1030U∈Y1 Winter? CSCI 1030U∈Y2 Fall? CSCI 1030U∈Y2 Winter? CSCI 1030U∈Y3 Fall? CSCI 1030U∈Y3 Winter? CSCI 1030U∈Y4 Fall? CSCI 1030U∈Y4 Winter?
CSCI 1060U CSCI 1060U∈Y1 Fall? CSCI 1060U∈Y1 Winter? CSCI 1060U∈Y2 Fall? CSCI 1060U∈Y2 Winter? CSCI 1060U∈Y3 Fall? CSCI 1060U∈Y3 Winter? CSCI 1060U∈Y4 Fall? CSCI 1060U∈Y4 Winter?
CSCI 1061U CSCI 1061U∈Y1 Fall? CSCI 1061U∈Y1 Winter? CSCI 1061U∈Y2 Fall? CSCI 1061U∈Y2 Winter? CSCI 1061U∈Y3 Fall? CSCI 1061U∈Y3 Winter? CSCI 1061U∈Y4 Fall? CSCI 1061U∈Y4 Winter?
CSCI 1062U CSCI 1062U∈Y1 Fall? CSCI 1062U∈Y1 Winter? CSCI 1062U∈Y2 Fall? CSCI 1062U∈Y2 Winter? CSCI 1062U∈Y3 Fall? CSCI 1062U∈Y3 Winter? CSCI 1062U∈Y4 Fall? CSCI 1062U∈Y4 Winter?
CSCI 1063U CSCI 1063U∈Y1 Fall? CSCI 1063U∈Y1 Winter? CSCI 1063U∈Y2 Fall? CSCI 1063U∈Y2 Winter? CSCI 1063U∈Y3 Fall? CSCI 1063U∈Y3 Winter? CSCI 1063U∈Y4 Fall? CSCI 1063U∈Y4 Winter?

Constraints

We can immediate declare some basic constraints.

  1. Each course can only be taken at most once.
  2. Each semester can have at most 5 courses.
  3. Must take lots of courses.
def make_taken_atmost_once(model:CpModel, unknown:DataFrame)->Series:
    def fn(row:pd.Series):
        c = sum(row) <= 1
        model.Add(c)
        return c

    return unknown.apply(fn, axis=1)

Each course can only be taken at most once.

model = CpModel()
unknown = make_unknowns(model)
C1 = make_taken_atmost_once(model, unknown)
C1.head()
courses
CSCI 1030U    (((((((CSCI 1030U∈Y1 Fall? + CSCI 1030U∈Y1 Win...
CSCI 1060U    (((((((CSCI 1060U∈Y1 Fall? + CSCI 1060U∈Y1 Win...
CSCI 1061U    (((((((CSCI 1061U∈Y1 Fall? + CSCI 1061U∈Y1 Win...
CSCI 1062U    (((((((CSCI 1062U∈Y1 Fall? + CSCI 1062U∈Y1 Win...
CSCI 1063U    (((((((CSCI 1063U∈Y1 Fall? + CSCI 1063U∈Y1 Win...
dtype: object
def make_semester_atmost_five(model:CpModel, unknown:DataFrame)->Series:
    def fn(col:pd.Series):
        c = sum(col) <= 5
        model.Add(c)
        return c

    return unknown.apply(fn, axis=0)

Each semester can only have at most five courses.

model = CpModel()
unknown = make_unknowns(model)
C1 = make_semester_atmost_five(model, unknown)
C1.head()
semesters
Y1 Fall      ((((((((((((((((((((((((((((((((((((((((((CSCI...
Y1 Winter    ((((((((((((((((((((((((((((((((((((((((((CSCI...
Y2 Fall      ((((((((((((((((((((((((((((((((((((((((((CSCI...
Y2 Winter    ((((((((((((((((((((((((((((((((((((((((((CSCI...
Y3 Fall      ((((((((((((((((((((((((((((((((((((((((((CSCI...
dtype: object
def make_min_selection(model:CpModel, unknown:DataFrame, min:int):
    vars = unknown.values.reshape(-1)
    c = sum(vars) > min
    model.Add(c)
    return c

Dependent Variables

We will declare a number of dependent variables. These values are derived from data and unkowns (and maybe other dependent variables). Since the values of unknowns are non-deterministic, derived qualities are also variables.

They can be general integer variables.

Let’s create a set of dependent integer variables, taken_in, which indicates the semester that the courses are taken in. The taken_in[c] is from 1 to \(n\) if the course [c] is taken. Otherwise taken_in[c] = 0.

def make_taken_in(model:CpModel, unknown:DataFrame)->Series:
    def fn(row:pd.Series)->cp_model.IntVar:
        var = model.NewIntVar(0, len(row)+1, 'taken_in')
        model.add_map_domain(var, row, offset=1)
        return var

    taken_in = unknown.apply(fn, axis=1)
    return taken_in
model = CpModel()
unknowns = make_unknowns(model)
taken_in = make_taken_in(model, unknown)

taken_in.head()
courses
CSCI 1030U    taken_in
CSCI 1060U    taken_in
CSCI 1061U    taken_in
CSCI 1062U    taken_in
CSCI 1063U    taken_in
dtype: object

Let’s also define the set of dependent variables, taken, which are booleans indicating of the course is taken.

def make_taken(model:CpModel, unknown:DataFrame)->Series:
    def fn(row:pd.Series)->cp_model.IntVar:
        var = model.NewBoolVar('taken')
        model.AddMaxEquality(var, row)
        return var

    taken = unknown.apply(fn, axis=1)
    return taken
model = CpModel()
unknown = make_unknowns(model)
taken = make_taken(model, unknown)

taken.head()
courses
CSCI 1030U    taken
CSCI 1060U    taken
CSCI 1061U    taken
CSCI 1062U    taken
CSCI 1063U    taken
dtype: object

Solution

We can solve the unknowns (hopefully) and the derived variables using a Solver. The solution will be rendered by views.

model = CpModel()
unknown = make_unknowns(model)

#
# constraints
#
taken_atmost_once = make_taken_atmost_once(model, unknown)
semester_atmost_five = make_semester_atmost_five(model, unknown)

#
# dependent variables
#
taken_in = make_taken_in(model, unknown)
taken = make_taken(model, unknown)
make_min_selection(model, unknown, min=35)

#
# solution
#
solver = cp_model.CpSolver()
status = solver.solve(model)

status_name = {
    cp_model.OPTIMAL: 'optimal',
    cp_model.FEASIBLE: 'feasible',
    cp_model.INFEASIBLE: 'infeasible',
    cp_model.MODEL_INVALID: 'invalid',
    cp_model.UNKNOWN: 'unknown',
}[status]

status_name
'optimal'

Viewing the solution

def view(solver:CpSolver, df:DataFrame)->DataFrame:
    def fn(x):
        return solver.value(x)
    return df.map(fn)
view(solver, unknown).head()
semesters Y1 Fall Y1 Winter Y2 Fall Y2 Winter Y3 Fall Y3 Winter Y4 Fall Y4 Winter
courses
CSCI 1030U 1 0 0 0 0 0 0 0
CSCI 1060U 0 0 0 0 0 0 0 0
CSCI 1061U 0 0 0 0 0 0 0 0
CSCI 1062U 0 0 0 0 0 0 0 0
CSCI 1063U 1 0 0 0 0 0 0 0 
view(solver, taken_in)
courses
CSCI 1030U    1
CSCI 1060U    0
CSCI 1061U    0
CSCI 1062U    0
CSCI 1063U    1
CSCI 2000U    1
CSCI 2010U    1
CSCI 2020U    1
CSCI 2040U    2
CSCI 2050U    2
CSCI 2072U    2
CSCI 2110U    2
CSCI 3010U    2
CSCI 3030U    3
CSCI 3055U    3
CSCI 3060U    3
CSCI 3070U    3
CSCI 3090U    3
CSCI 3230U    4
CSCI 3240U    4
CSCI 3310U    4
CSCI 3540U    4
CSCI 4020U    4
CSCI 4030U    5
CSCI 4040U    5
CSCI 4050U    5
CSCI 4052U    5
CSCI 4055U    5
CSCI 4060U    6
CSCI 4080U    6
CSCI 4100U    6
CSCI 4110U    6
CSCI 4140U    6
CSCI 4150U    7
CSCI 4160U    7
CSCI 4210U    7
CSCI 4220U    7
CSCI 4230U    7
CSCI 4410U    8
CSCI 4420U    8
CSCI 4430U    8
CSCI 4610U    8
CSCI 4620U    8
dtype: int64
view(solver, taken_in) \
.to_frame() \
.reset_index() \
.rename(columns={0: 'semester'}) \
.groupby(by='semester') \
.agg({
    'courses': lambda x: (f"{len(x)} :" + ", ".join(x))
})
courses
semester
0 3 :CSCI 1060U, CSCI 1061U, CSCI 1062U
1 5 :CSCI 1030U, CSCI 1063U, CSCI 2000U, CSCI 20...
2 5 :CSCI 2040U, CSCI 2050U, CSCI 2072U, CSCI 21...
3 5 :CSCI 3030U, CSCI 3055U, CSCI 3060U, CSCI 30...
4 5 :CSCI 3230U, CSCI 3240U, CSCI 3310U, CSCI 35...
5 5 :CSCI 4030U, CSCI 4040U, CSCI 4050U, CSCI 40...
6 5 :CSCI 4060U, CSCI 4080U, CSCI 4100U, CSCI 41...
7 5 :CSCI 4150U, CSCI 4160U, CSCI 4210U, CSCI 42...
8 5 :CSCI 4410U, CSCI 4420U, CSCI 4430U, CSCI 46...