Add a division inequality constraint

Question

I need to resolve this simple optimization problem with Google OR-Tools CP-SAT solver in Python:

Goal = MAXIMIZE (X+Y+Z)
Constraint: Z/(X+Y+Z) <= 0.25

I don't know how to write the constraint properly since it is not linear. Could you help me?

Answer 1

You have to create an intermediate variable and set its value using model.AddDivisionEquality. You also have to scale some variables up as CP-SAT works with integers.

scaling = 1000
x = model.NewIntVar(0, 10, 'x')
y = model.NewIntVar(0, 10, 'y')
z = model.NewIntVar(0, 10, 'z')

scaled_z = model.NewIntVar(0, 10 * scaling, 'z_scaled')
denom = model.NewIntVar(1, 3 * 10, 'x+y+z')
division = model.NewIntVar(0, 10 * scaling, 'z/(x+y+z)')

model.Add(scaled_z == z * scaling)
model.Add(denom == x + y + z)
model.AddDivisionEquality(division, scaled_z, denom)
model.Add(division <= int(0.25 * scaling))
model.Maximize(x + y + z)

solver.Solve(model)

print('x =', solver.Value(x))
print('y =', solver.Value(y))
print('z =', solver.Value(z))
print('z/(x+y+z) =', solver.Value(division) / scaling)