optimizationor-toolsnonlinear-optimizationcp-sat

Rounding Non-LinearExpr with google or-tools SAT solver


Using CP-SAT of google or-tools I'm trying to write this constraint:

q >= (50x + 100y + 150z + 200k + 250p + 300v) / (x + y + z + k + p + v)

Where q is a simple integer.

The thing is I need to round the right side of the equation (let's call it expression) as follows:

if(expression < 75) {
    expression = 50;
} else if(expression < 125) {
    expression = 100;
} else if(expression < 175) {
    expression = 150;
} else if(expression < 225) {
    expression = 200;
} else if(expression < 275) {
    expression = 250;
} else {
    expression = 300;
}

So I need to round the expression

(50x + 100y + 150z + 200k + 250p + 300v) / (x + y + z + k + p + v)

So that it gets one of the following values:

{50, 100, 150, 200, 250, 300}

Let's review 2 cases:

Case 1

q = 180 and expression = 176.

Although the condition 180 >= 176 is true, after rounding up 176 to 200 the tested condition should be 180 >= 200 which is false.

So for q = 180 and expression = 176 I would like the condition to return false.


Case 2

q = 210 and expression = 218.

Although the condition 210 >= 218 is false, after rounding down 218 to 200 the tested condition should be 210 >= 200 which is true.

So for q = 210 and expression = 218 I would like the condition to return true.


I got a great answer here for resolving this challenge over a linear expression but now I need to resolve it for a non-linear expression.

Any suggestions?


Solution

  • Let's rephrase

    you have an integer variable e with a value between 0 and 300. You want to round it to the nearest multiple of 50

    if you do:

    (e div 50) * 50
    

    you will get the max multiple of 50 less or equal to e

    (70 / 50) * 50 -> 50
    (99 / 50) * 50 -> 50
    (102 / 50) * 50 -> 100
    

    To get a round to nearest, you need to add 25 to e before the division

    ((e + 25) div 50) * 50
    

    Which will do the correct rounding

    ((70 + 25) / 50) * 50 -> 50
    ((99 + 25) / 50) * 50 -> 100
    ((102 + 25) / 50) * 50 -> 100
    

    with the correct or-tools CP-SAT python code:

    numerator = model.NewIntVar(...)
    model.Add(numerator == 50x + 100y + 150z + 200k + 250p + 300v)
    denom = model.NewIntVar(...)
    model.Add(denom == 50x + 100y + 150z + 200k + 250p + 300v)
    e = model.NewIntVar(0, 300, 'e')
    model.AddDivisionEquality(e, numerator, denom)
    
    shifted_e = model.NewIntVar(25, 325, 'shifted_e')
    model.Add(shifted_e == e + 25)
    multiple_of_fifty = model.NewIntVar(0, 6, 'multiple_of_fifty')
    model.AddDivisionEquality(multiple_of_fifty, shifted_e, 50)
    result = model.NewIntVar(0, 300, 'result')
    model.Add(result = multiple_of_fifty * 50)