Add support for special case operators like min, max, etc in Expressions

[niesmo]

Hi all 👋,

We're encountering a scenario where having support for some special case operators like min or max would make things a lot simpler for us. This is compared to having to figure out the linear way of expressing those operations. I see that OPTANO currently has support for them in their expressions (OPTANO docs).

I think adding support for them would be a great addition to FLIPs 😄.
Willing to help 🙋‍♂️.

[matthewcrews]

@niesmo Could you provide an example of what you are trying to express? I am looking through the docs at the link you provided. Is it just the Min and Max operators you are needing? I could see adding that as a function/method under LinearExpr.

The challenge will be that not all backends go through OPTANO. CPLEX and Gurobi do but Google OR Tools does not. This has been a pain point.

[niesmo]

Is it just the Min and Max operators you are needing?

Yes. For now that's what we need.

The challenge will be that not all backends go through OPTANO. CPLEX and Gurobi do but Google OR Tools does not. This has been a pain point.

You're right. that is a pain point. It could be a NotImplementedException at first for OR Tools. If OR Tools adds the features we could implement it here and if not, maybe we can implement a manual one for OR Tools (I have no idea how complex/difficult it might be).

Could you provide an example of what you are trying to express?

Simple example:

Decision variables: x1, x2, x3 | continuous | [0, 2]
Constraint: 3 * x3 >= MAX (4 * x1, 3.5 * x2)
Objective: Maximize ( 4 * x1 + 5 * x2 - x3 )

Complex example (I have not figured out how to do this in OPTANO yet):
I'm going to describe this since I dont know how to formulate it.

Decision variables: let's say we have n binary decision variables.
Constraint:
M = Maximum of decision variables multiplied by some constant (different constant for each decision variable).
LHS = Sum of all decision variables multiplied by some constant (different constant for each decision variable) for only the decision variables that their constant is greater than M - 30.
RHS = Sum of all decision variables multiplied by some constant (different constant for each decision variable).
✨ LHS >= 80% RHS ✨
Objective:
Maximize sum of all decision variables multiplied by some constant (different constant for each decision variable).

[matthewcrews]

Interesting. This is going to add a lot of variables and constraints to your model and cause it to take longer to solve. I'm actually less concerned about the Max/Min functions and more curious about formulating the LHS in your example there. You're essentially adding a WHERE clause to the decision variables which means even more indicator variables. This could cause a rather large increase in the number of variables and constraints.

[matthewcrews]

I spent some time looking through the code and it would be a pretty significant overhaul to support this. I need to think about whether it would be possible to do it in such a way that didn't break backward compatibility. I need to evolve the domain in a way that doesn't break existing models.

[matthewcrews]

I'd be happy to discuss your specific situation over a call if that would be helpful. You LHS requirement is not something I've seen before so I'd be curious as to the motivation.

[niesmo]

Interesting. This is going to add a lot of variables and constraints to your model and cause it to take longer to solve.

I think you're absolutely right.

I'm actually less concerned about the Max/Min functions and more curious about formulating the LHS in your example there. You're essentially adding a WHERE clause to the decision variables which means even more indicator variables. This could cause a rather large increase in the number of variables and constraints.

Yeah, this is first approach and certainly the most naïve approach that came to mind. There likely exist simpler and more clever ways of approaching it which I would love to learn 😄 .

I'd be happy to discuss your specific situation over a call if that would be helpful

Okay, we'll schedule something up. Thanks