CpModel BoolVar not evaluating as a boolean

Question

I'm a bit stuck here, and couldn't find any similar examples or obvious methods to use...

For a volunteer scheduling script (in Python), there's cases where some volunteers may have to do 2+ roles on the same day. Certain combinations (pairs) of roles are more difficult than others to do simultaneously, so I've assigned integer (0-10) penalty weights for each pair in the input data. Rather than Minimize (optimization), I've decided to Add (constraint) to forbid any sum of sum of weights greater than const conflict_level.

Below is the constraint code that currently am trying. The args for days, roles and volunteers are range lists (i.e., [0-n]).

For any person on any day, I would like to take the list of their roles (x, an array of CpModel BoolVars) use the bit pairs to address and sum the pair weights.

To help visualize the approach I'm trying, here is code tested in the Python CLI:

>>> x = [True,False,True,True,False,False,False]
>>> [i for i,n in enumerate(x) if n]         
[0, 2, 3]
>>> [role_objs[a]['conflicts'][role_names[b]] for a,b in list(combinations([i for i, n in enumerate(x) if n], 2))]
[6, 8, 2]

Which would sum to 16 in this example.

But if the boolean list is replaced by a BoolVar list, I get an error.

def constraint_role_conflicts(model, jobs, data, days, roles, volunteers):
role_objs = data['roles']
role_names = [n['name'] for n in data['roles']]
for d in days:
    for v in volunteers:
        x = [jobs[(d,r,v)] for r in roles]
        model.Add(sum([role_objs[a]['conflicts'][role_names[b]] for a,b in list(combinations([i for i, n in enumerate(x) if n], 2))]) > conflict_level)

At the 2nd instance of 'n' in the Add method call, I am getting:

NotImplementedError: Evaluating a LinearExpr instance as a Boolean is not implemented.

What am I doing wrong?

UPDATE - Adding as requested a complete minimal reproducible example.

from ortools.sat.python import cp_model
from itertools import combinations

# role conflict pain threshold setting
pain_threshold = 8

# role pair pain factors
conflicts = [
    [0, 10,6, 8, 8, 7, 8 ],
    [10,0, 9, 3, 2, 3, 3 ],
    [6, 9, 0, 2, 1, 2, 6 ],
    [8, 3, 2, 0, 1, 5, 10],
    [8, 2, 1, 1, 0, 7, 7 ],
    [7, 3, 2, 5, 7, 0, 4 ],
    [8, 3, 6, 10,7, 4, 0 ]
]

ndays = 25
nroles = 7
nvols = 10

days = list(range(ndays))
roles = list(range(nroles))
vols = list(range(nvols))


model = cp_model.CpModel()

jobs = {}
for d in days:
    for r in roles:
        for v in vols:
            jobs[(d,r,v)] = model.NewBoolVar(f"d{d}r{r}v{v}")

# one volunteer per each day, each role
for d in days:
    for r in roles:
        # The boolvar array True values are summed and must equal 1,
        # meaning exactly 1 volunteer for each day-role job assignment.
        model.AddExactlyOne(jobs[(d,r,v)] for v in vols)

# don't allow role conflicts over a certain pain threshold
for d in days:
    for v in vols:
        x = [jobs[(d,r,v)] for r in roles]          # e.g. [True, False, True, False, ...]
        # xids = [i for i in range(len(x)) if x[i]]   # e.g. [0, 2, 4]
        # role_pairs = list(combinations(xids, 2))    # e.g. [(0,2), (0,4), (2,4)]
        # pain = sum([conflicts[a][b] for a,b in role_pairs])
        # model.Add(pain > pain_threshold)
        model.Add(sum([conflicts[a][b] for a,b in list(combinations([i for i in range(len(x)) if x[i]], 2))]) > pain_threshold)

solver = cp_model.CpSolver()
solver.parameters.enumerate_all_solutions = False
solver.parameters.num_search_workers = 16
solver.parameters.max_time_in_seconds = 300 # 5 minutes
print("Running Solver...")
status = solver.Solve(model)

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    for d in days:
        print(f"Day {d}")
        for r in roles:
            for v in vols:
                # solver tests the True value of the boolvar.
                if solver.Value(jobs[(d,r,v)]):
                    print(f" d{d}_v{v}_r{r} Role: {r} = Volunteer {v}")
else:
    print("No solution found.")

Answer 1

Please post a complete minimal reproducible example.

And be aware that a boolvar does not have a value per se. You cannot use it an if, a comparison, a python test.

Doing so will create a CP-SAT expression or bounded linear expression.

As this object is not None, it will silently be evaluated to True. For instance, using sort or max and an array of variables used to silently create garbage.

For this reason, we protect the cast to bool as this should never happen.

A useful read is: https://github.com/google/or-tools/blob/stable/ortools/sat/docs/channeling.md

Answer 2

You need to end up with an array of model integer variables for "pain" levels in your conflicts array that the model can sum together. These pain ints have to be toggled on/off (set to 0 or their respective pain value) by an equally long array of model boolean variables. Each bool and respective int correspond to a job pair, a pair of roles that each volunteer could potentially be assigned each day.

Given your Update with complete minimal reproducible example, this should replace your code with comment "don't allow role conflicts over a certain pain threshold":

# Constraint to disallow role conflict sums over a certain pain threshold
# Want to end up with a list of pain value ints to sum together for a decision threshold value
# these ints will be the pain values, in this case, for each role pair possible.
pain_keys = list(combinations(roles, 2))  # [(0, 1), (0, 2), ... (5, 6)]
pain_vals = [conflicts[a][b] for (a,b) in pain_keys]
num_pairs = len(pain_keys)

# Put in the special conditions (assigned role pairs)
job_pairs = []
pair_pains = []
m_pair_active = []
m_pain_val = []
for d in days:
    for v in vols:
        for i in range(num_pairs): # for 7 roles, there are 21 role pairs generated
            # for every pair of roles, group a pair of job assignments that could both be active
            job_pairs.append( [jobs[(d,r,v)] for r in roles if r in pain_keys[i]] )
            pair_pains.append( pain_vals[i] ) # append pain value for this pair
            # create intermediate model bools (pain on/off switch logic bits)
            m_pair_active.append( model.NewBoolVar(f"active_{pain_keys[i]}") )
            m_pain_val.append( model.NewIntVar(0, pain_vals[i], f"pain_{pain_keys[1]}") )

for i in range(len(job_pairs)):
    # setting of m_pair_active bools based on job_pair members both set
    model.Add(sum(job_pairs[i]) == 2).OnlyEnforceIf(m_pair_active[i])
    model.Add(sum(job_pairs[i]) != 2).OnlyEnforceIf(m_pair_active[i].Not())
    # setting of m_pain_val ints based on m_pair_active
    model.Add(m_pain_val[i] == pair_pains[i]).OnlyEnforceIf(m_pair_active[i])
    model.Add(m_pain_val[i] == 0).OnlyEnforceIf(m_pair_active[i].Not())

# Add constraint: sum of pain < threshold
# or optimization: Minimize sum of pain
model.Add(sum(m_pain_val) < pain_threshold)

Instead of all jobs being assigned to the same volunteer, you should now see more like this for example:

Running Solver...
Day 0
 d0_v6_r0 Role: 0 = Volunteer 6
 d0_v0_r1 Role: 1 = Volunteer 0
 d0_v2_r2 Role: 2 = Volunteer 2
 d0_v1_r3 Role: 3 = Volunteer 1
 d0_v5_r4 Role: 4 = Volunteer 5
 d0_v4_r5 Role: 5 = Volunteer 4
 d0_v7_r6 Role: 6 = Volunteer 7
Day 1
 d1_v3_r0 Role: 0 = Volunteer 3
 d1_v7_r1 Role: 1 = Volunteer 7
 d1_v8_r2 Role: 2 = Volunteer 8
 d1_v0_r3 Role: 3 = Volunteer 0
 d1_v1_r4 Role: 4 = Volunteer 1
 d1_v9_r5 Role: 5 = Volunteer 9
 d1_v2_r6 Role: 6 = Volunteer 2
Day 2
 d2_v1_r0 Role: 0 = Volunteer 1
 d2_v3_r1 Role: 1 = Volunteer 3
 d2_v9_r2 Role: 2 = Volunteer 9
 d2_v0_r3 Role: 3 = Volunteer 0
 d2_v8_r4 Role: 4 = Volunteer 8
 d2_v4_r5 Role: 5 = Volunteer 4
 d2_v2_r6 Role: 6 = Volunteer 2

&c.

Answer 3

This replaces the minimal example code, even more minimal, with bugs worked out and Minimize method added in case it is useful to someone someday.

from ortools.sat.python import cp_model
from itertools import combinations

# SETTINGS
pain_threshold = 6  # role conflict pain threshold
ndays = 3
nroles = 3
nvols = 2

# role pair pain factors
conflicts = [
    [0, 5, 8],
    [5, 0, 3],
    [8, 3, 0]
]

days = list(range(ndays))
roles = list(range(nroles))
vols = list(range(nvols))

model = cp_model.CpModel()

jobs = {}
for d in days:
    for r in roles:
        for v in vols:
            jobs[(d,r,v)] = model.NewBoolVar(f"d{d}r{r}v{v}")

# Constraint: one volunteer per each day, each role
for d in days:
    for r in roles:
        # 1 volunteer for each day-role job assignment
        model.AddExactlyOne(jobs[(d,r,v)] for v in vols)

# Constraint to disallow role conflict sums over a certain pain threshold
pain_keys = list(combinations(roles, 2))  # [(0, 1), (0, 2), ... (5, 6)]
pain_vals = [conflicts[a][b] for (a,b) in pain_keys]
npairs = len(pain_keys)
print(f"Number of Pairs = {npairs}")

# Put in the special conditions (assigned role pairs)
job_pairs = []
pair_pains = []
m_pair_active = []
m_pain_val = []
pain_val = 0
for d in days:
    for v in vols:
        for i in range(npairs): # for 7 roles, there are 21 role pairs generated
            pain_val += pain_vals[i]
            # for every pair of roles, group a pair of job assignments that could both be active
            job_pairs.append( [jobs[(d,r,v)] for r in roles if r in pain_keys[i]] )
            pair_pains.append( pain_vals[i] ) # append pain value for this pair
            # create intermediate model bools (pain on/off switch logic bits)
            m_pair_active.append( model.NewBoolVar(f"active_d{d}v{v}rp{i}") )
            m_pain_val.append( model.NewIntVar(0, pain_vals[i], f"pain_d{d}v{v}rp{i}") )
print(f"Pain Max Limit: {pain_val}")

for i in range(len(job_pairs)):
    # setting of m_pair_active bools based on job_pair members both set
    model.Add(sum(job_pairs[i]) == 2).OnlyEnforceIf(m_pair_active[i])
    model.Add(sum(job_pairs[i]) != 2).OnlyEnforceIf(m_pair_active[i].Not())
    # setting of m_pain_val ints based on m_pair_active
    model.Add(m_pain_val[i] == pair_pains[i]).OnlyEnforceIf(m_pair_active[i])
    model.Add(m_pain_val[i] == 0).OnlyEnforceIf(m_pair_active[i].Not())

for d in days:
    for v in vols:
        os = d*nvols*npairs + v*npairs
        model.Add(sum(m_pain_val[os:os+npairs]) <= pain_threshold)

# Optimization: Minimize sum of pain
model.Minimize(sum(m_pain_val))

solver = cp_model.CpSolver()
solver.parameters.enumerate_all_solutions = False
solver.parameters.num_search_workers = 16
solver.parameters.max_time_in_seconds = 300 # 5 minutes
print("\nRunning Solver...")
status = solver.Solve(model)

def printout():
    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        for d in days:
            print(f"Day {d}")
            for r in roles:
                for v in vols:
                    # solver tests the True value of the boolvar.
                    if solver.Value(jobs[(d,r,v)]):
                        print(f" d{d}_v{v}_r{r} Role: {r} = Volunteer {v}")
        worst_pain = 0
        worst_pain_dv = ""
        for d in range(ndays):
            for v in range(nvols):
                os = d*nvols*npairs + v*npairs
                pain = sum([solver.Value(x) for x in m_pain_val[os:os+npairs]])
                if pain >= worst_pain:
                    worst_pain = pain
                    worst_pain_dv = f"Day {d}, Vol {v}"
        print()
        print(f"Worse Pain = {worst_pain} (for {worst_pain_dv})")
        print(f"Pain Total: {sum(solver.Value(x) for x in m_pain_val)}")
        print()

    else:
        print("No solution found.")

printout()