Stack Overflow Asked by forhas on November 27, 2021
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?
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)
Answered by Laurent Perron on November 27, 2021
if a and b are positive then
a div b >= q
is equivalent to
a >= q * b
now, your example does not specify how to round (nearest or down)
if you want to round down
q * (x + y + z + k + p + v) <= (50x + 100y + 150z + 200k + 250p + 300v)
If you want to round to nearest, you need to add q / 2 in the right place
q * (x + y + z + k + p + v) <= (50x + 100y + 150z + 200k + 250p + 300v + q / 2)
Now, if you want the other direction
a div b <= q
is equivalent to
a <= q * b + q - 1
The rest of the transformation is the same.
Answered by Laurent Perron on November 27, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP