Adding soft constraints to a scheduling problem in or-tools python

Question

tools and im trying to use it to generate a timeTable for a highschool. Variables are Lesson, rooms, and timeslots and the goal of course to assign all the lessons to a certain room and a timeslot while respecting the given constraints.

The problem is in the documentation i don't see it talking about soft and hard constraint and all the constraint i've added are surely hard ones, is there a way to implement soft constraint for this example just a simple one.

Thanks in advance.

Bucher

You have implement soft constraints manually by adding them in the objective – Diuresis

Can you show me how to do it by code please. – Bucher

Answer 1

Probably a duplicate of Do Google Optimization Tools support Soft Constraints?, but I'll add some examples with CP-SAT.

Here's a simple soft limit example:

from ortools.sat.python import cp_model

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

x = [model.NewBoolVar("") for i in range(10)]

# hard constraint: number of 1's >= 4
model.Add(sum(x) >= 4)

# soft constraint: number of 1's <= 5
delta = model.NewIntVar(-5, 5, "")
excess = model.NewIntVar(0, 5, "")
model.Add(delta == sum(x) - 5)
model.AddMaxEquality(excess, [delta, 0])
model.Minimize(excess)

solver.Solve(model)
print([solver.Value(i) for i in x])
print(solver.Value(excess))

See a more complex example here

And here's one concerning fullfiled requests:

from ortools.sat.python import cp_model

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

x = [model.NewIntVar(0, 10, "") for i in range(10)]

# request: sum() <= 10
req1 = model.NewBoolVar("")
model.Add(sum(x) <= 10).OnlyEnforceIf(req1)

# request: sum() >= 5
req2 = model.NewBoolVar("")
model.Add(sum(x) >= 5).OnlyEnforceIf(req2)

# request: sum() >= 100
req3 = model.NewBoolVar("")
model.Add(sum(x) >= 100).OnlyEnforceIf(req3)

model.Maximize(req1 + req2 + req3)
solver.Solve(model)
print(solver.Value(sum(x)))
print(solver.ObjectiveValue())

Diuresis

Sorry to bother but i didn't quite understand the use of delta and the excess variables. – Bucher

Excess is what you want to penalize, so you want to set it to 0 if you are bellow the limit – Diuresis