How do I make sure that no more than n variables have the same value?

[MarcelloTheArcane]

To help this not be an XY problem, here's what I'm trying to do.

I am trying to write a scheduling optimiser, with the following requirements:

• A list of jobs where each job has an ordered list of workstations it must visit
• A list of workstations where each workstation has:
  • a maximum number of tasks it can complete in a given day, and
  • a minimum number of days until the next workstation can start

import collections

workstation = collections.namedtuple("workstation", ["jobs_per_day", "days_till_next"])
workstations = [
    workstation(3, 2),
    workstation(2, 1),
    workstation(1, 1),
    workstation(1, 1),
    workstation(4, 1),
    workstation(3, 1),
]

jobs = [
    (0, 5), # each number is the workstation index in order
    (0, 2, 3, 5),
    (0, 1, 2, 4, 5),
    (0, 4, 5),
    (0, 1, 3, 5),
]

I want to produce a calendar of working days, with each day containing the list of steps that should be completed by each workstation:

Workstation	Day 0	Day 1	Day 2	Day 3	Day 4	Day 5
0	0, 1, 2	3, 4
1			2	4
2			1	2
3				1	4
4				3	2
5			0		1, 3	2, 5

I have worked out how to make sure that the steps are in order, but I'm stuck on making sure no more than jobs_per_day steps are added each day.

I tried doing this with intervals, but wasn't sure how to do that either. I'm not sure this is an interval problem, as I think it's more discrete:

Do not directly jump to intervals when you have a scheduling problem. Intervals are great if you actually have a somewhat continuous time or space that you need to schedule. If you have a more discrete problem, such as a scheduling problem with a fixed number of slots, you can often model this problem much more efficiently using simple Boolean variables and constraints...
The CP-SAT Primer, 5. Advanced Modeling

The only thing that springs to mind is to make a load of boolean intermediate variables, where each one is true if and only if a given step is allocated to a given day, and then making sure that the sum of each day's workstation's booleans is less than jobs_per_day. Something like this - which looks horrible:

from ortools.sat.python import cp_model

model = cp_model.CpModel()

horizon = 5

# Make a load of variables, which analogues the day each step is allocated
int_vars = []
for i in range(horizon):
    int_vars.append(model.new_int_var(0, horizon + 1, f"int_var_{i}"))

# Make some boolean variables where one is true if a step is on a day
bool_vars = {}
for var in range(horizon):
    for i in range(horizon):
        bool_vars[(var, i)] = model.new_bool_var(f"{var}_is_{i}")
        model.add(int_vars[var] == i).only_enforce_if(bool_vars[(var, i)])
        model.add(int_vars[var] != i).only_enforce_if(~bool_vars[(var, i)])

# Make sure they are in ascending order
for index in range(horizon - 1):
    model.add(int_vars[index] <= int_vars[index + 1])

jobs_per_day = 2

# Make sure that the number of steps in each day is under the limit
for value in range(horizon):
    model.add(sum(bool_vars[(var, value)] for var in range(horizon)) <= jobs_per_day)

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

if solution == cp_model.FEASIBLE or solution == cp_model.OPTIMAL:
    for var in int_vars:
        print(f"{var}: {solver.value(var)}")
else:
    print("No solution found")

Is there a correct way to achieve my goal?

[lperron]

As indicated in the CP_SAT primer, just don't create integer variables. Just use Boolean variables.

[MarcelloTheArcane]

Thanks, that's interesting, I hadn't thought of that.

How would I add constraints so that step n + 1 is always after step n, using only boolean constraints?

Also, when it comes to adding objectives, how would I do that without an integer variable to minimise?

[lperron]

you have multiple options.

The basic problem is a scheduling problem with a cumulative constraint of size 2 (which is at odd with your solution top left cell which contains 3 numbers).

So the best option is to see that as a scheduling problem. Look at all jobshop_ft06_sat.py, create all task intervals with precedences.
Instead of using n no_overlap constraints, use one cumulative constraint with a capacity of 2.

Your code is fine. But it would be better not to use Boolean vars if the crux of the problem is a temporal one.

My initial reaction is that persons coming from the CP community tends to create integer variables for assignment, which is not optimal.

[MarcelloTheArcane]

@lperron Thanks for your help.

I've gone with using integer variables for each day, and am using the cumulative constraint to limit how many steps can be processed each day.

From your advice, I'm also using boolean variables where I can!