How to make a "Value Decrease Occurrences" constraint on Google Or-Tools SCIP? - Python

Question

Im trying to optimize 12 ordered integer variables with Google Or-Tools. Basically, 1 variable for each month.

One of the constraint I want to implement is that a decrease in value can only ocurr 1 time at max.

This is what I did...

solver.Add(solver.Sum([x[i] <= x[i+1] for i in range(11)]) >= 11)

...and this is the error.

AttributeError: 'LinearConstraint' object has no attribute 'AddSelfToCoeffMapOrStack'

Is there another way to do this constraint?

Answer 1

With the linear solver, you will need big-M formulation to link Boolean variables with xi <= x(i+1).

I recommend using CP-SAT as it makes the writing easier. Please have a look at this doc page

Answer 2

What I did to make it work was to divide the problem into 2 steps.

First I set a flag to indicate when the decreases occur using Big M;

flag = {}
bigM = 100000000

for j in range(12):
 flag[j] = solver.BoolVar('flag[%i]' % j)

for k in range(12-1):
    solver.Add(x[k] <= (x[k+1] + (bigM * flag[k])))

Then, I constrain the sum of the "flag array";

solver.Add(sum(flag[i] for i in range(12)) <= 1)

For some reason, the flag doens't seems to work when the sum constraint is missing. But with the 2 parts it is working properly.