optimizationconstraintsor-toolsconstraint-programmingcp-sat

OR constraints in CP-SAT

Is there any way we can program the following example formulation using CP-SAT class methods:

(x + y >=10) V (x - y <= 5) V (y >= 2 )

I am aware of the big M-method trick but I was not able to use CP-SAT functions. Is a Boolean variable going to help me here?

Can anyone give me a short program for this so that I can get the idea?

Solution

  • Depends on the solver. I assume you are talking about CP-SAT from Google's OR-tools. You can use binary variables and OnlyEnforceIf to implement the following mathematical model:

    b1=1 => x+y>=10
b2=1 => x-y<=5
b3=1 => y>=2
b1+b2+b3 >= 1
b1,b2,b3 ∈ {0,1}

    The first implication can look like:

      model.Add(x+y>=10).OnlyEnforceIf(b1)

    and similarly for the others. The summation can be stated as is, or as:

      model.AddBoolOr(b1, b2, b3)

    (I prefer the summation, but that is because I am used to MIP models). I would hope they are presolved to the same thing.

    Note that many MIP solvers also can do implications (there they are called indicator constraints). If not, you may need to use big-M constraints (nerdy: or SOS1 sets).

    It is often useful to think in terms of implications (instead of "if"). They are easily understood by human readers and by (most) solvers.