Max()/.max() method not yielding expected results

[MxMartin]

Hi!

I tried to model a constraint that sets a machine_active variable to 1 whenever at least one job is assigned.
I however don't manage to get the machine_active variable to be calculated correctly, i.e. multiple machine_activevariables are False though they should be True as jobs are assigned to the respective machine. I attached my code below as well as an alternative implementation using or-tools directly that returns the expected result.

import cpmpy as cp
from cpmpy import SolverLookup

model = cp.Model()
model = SolverLookup.get("ortools")

num_machines = 7
num_jobs = 5

job_to_machine_assignments = cp.boolvar(shape=(num_jobs, num_machines))
machine_active = cp.boolvar(shape=(num_machines,))

# machine active if job assigned
model += machine_active == job_to_machine_assignments.max(axis=0)

# max one machine per job
model += [job_to_machine_assignments[j].sum()<=1 for j in range(num_jobs)]

# max 2 jobs per machine
model += [job_to_machine_assignments[:,m].sum()<=2 for m in range(num_machines)]

# Objective
unassigned =  num_jobs - job_to_machine_assignments.sum()
model.minimize(unassigned)

model.solve()

I also tried the following implementation of the max constraint, which didn't work out for me either:

for m in range(num_machines):
    model += machine_active[m] == max(job_to_machine_assignments[:,m])

Output:

print(job_to_machine_assignments.value())

# [[False False False False False False  True]
#  [False False False False  True False False]
#  [False False False False False  True False]
#  [False False False False False False  True]
#  [False False False  True False False False]]

print(machine_active.value())

# Note that only the fourth value is true though in the output above True values can be found in columns 4 to 7
# [False False False  True False False False]

The following model in or-tools returned expected results:

import numpy as np
from ortools.sat.python import cp_model

model = cp_model.CpModel()
solver = cp_model.CpSolver()

num_machines = 7
num_jobs = 5

j_to_m_assignment = np.empty((num_jobs, num_machines), dtype=object)
for j in range(num_jobs):
    for m in range(num_machines):
        j_to_m_assignment[j, m] = model.NewBoolVar(f"j={j}->m={m}")

m_active = np.empty((num_machines,), dtype=object)
for m in range(num_machines):
    for t in range(num_jobs):
        m_active[m] = model.NewBoolVar(f"m={m}:active")

# machine active if job assigned
for m in range(num_machines):
    model.AddMaxEquality(m_active[m], j_to_m_assignment[:, m])

# max one machine per job
for i in range(num_jobs):
    model.Add(sum(j_to_m_assignment[i].tolist())<=1)

# max 2 jobs per machine
for j in range(num_machines):
    model.Add(sum(j_to_m_assignment[:,j])<=2)

# Objective
unassigned =  num_jobs - sum(j_to_m_assignment.flatten().tolist())
model.Minimize(unassigned)

status = solver.Solve(model)

Output:

j_to_m_assignment_solution = np.array([[solver.Value(j_to_m_assignment[j, m]) for m in range(num_machines)] for j in range(num_jobs)], dtype=bool)
m_active_solution = np.array([solver.Value(m_active[m]) for m in range(num_machines)], dtype=bool)
print(j_to_m_assignment_solution)

# [[False False False  True False False False]
#  [False False False False False False  True]
#  [False False False False  True False False]
#  [False False False False False  True False]
#  [False False False False False False  True]]

print(m_active_solution)
# Note that as expected values 4 to 7 are True
#  [False False False False  True  True  True  True]

[Dimosts]

Hello Martin,

this happens because the max() function used is the python built in function and not the cpmpy one. This means that it directly takes the one with the "maximum value", creating a constraint directly between 2 variables, instead of the desired constraint.

You can use the cp.max() function in order to use it with cpmpy variables, which leads to the wanted result.

best regards,
Dimos

[MxMartin]

Ah, I see, thanks a lot for the clarification, I was getting confused on when to use max, cp.max and .max().

Thanks a lot for the swift response!

[tias]

That is a good point, if we recommend using numpy's numpy-array.sum() (e.g. @IgnaceBleukx in a previous question from Max), then it is surprising that numpy-array.max() does not work.

So we should look into what we recommend...

I think at this point, the most generic is to recommend max(arr[i,j,:]) and sum(arr[i,:,:]) etc...
(or if you dont do from cpmpy import * but import cpmpy as cp then cp.max() etc)