General VRP constraints design discussion

[willbryant]

#93 was closed in favor of 44eb655 with the comment:

If quadratic constraints are needed, it should be possible to use index_expression(..., check_linear: false) to extend this.

I'm not sure I understand whether this will cover everything. Just to explain the motivation, I don't personally know of a significant use case for quadratic expressions is the sense of multiplying one scalar by another scalar, though maybe someone has one. The use case I am most familiar with is about disjunctions; if you have a constraint of the form some_dimension.CumulVar(A) - somedimension.CumulVar(B) <= const, there is a gotcha in or-tools where when a node becomes inactive, the cumul values associated with the node are not zeroed out, and the constraint can end up applying eliminating the solution.

Therefore the standard expression when disjunctions may apply is actually ActiveVar(A)*some_dimension.CumulVar(A) - ActiveVar(B)*some_dimension.CumulVar(B) <= const. ActiveVar being the or-tools "booleans" that indicate whether a node is active.

Or (eg. in pickup-delivery cases where the pickup and delivery are not a specific pair and may be independently deactivated) even ActiveVar(A)*ActiveVar(B)*some_dimension.CumulVar(A) - ActiveVar(A)*ActiveVar(B)*some_dimension.CumulVar(B) <= const.

I think this can be done because it's still a sum-of-products type expression, which I believe is what index_expression supports.

But I don't think it can implement arbitrary forms like ActiveVar(A)*ActiveVar(B)*(some_dimension.CumulVar(A) - some_dimension.CumulVar(B)) <= const, or ActiveVar(A)(some_dimension.CumulVar(A) - constA) - ActiveVar(B)(some_dimension.CumulVar(B) - constB) <= constC`? You'd need to rewrite into a form that has one sum-of-products on each side of the op, and if you need more than two, it won't be possible. The forms won't necessarily have equivalent performance, though I have no idea how to test that out.

So I think this would still cover a lot of people's use cases, but I guess I'm struggling to understand design intent of doing the work in index_expression instead of making the Expression support just pass everything through and letting or-tools figure it out? My understanding is that the Python bindings pass through any expression, though I haven't tested them so I could be wrong.