Bound Disjunction Constraints

[ctdunc]

Regular Disjunction constraints are quite slow when there are many bound disjunctions with distinct coefficients, since from my understanding the symmetry graph is built out by permuting variables with the same coefficients. Fortunately, there is also the bounddisjunction constraint handler, which I am working on adding support for. It looks like bound disjunctions only support constraints of the form x_i{>=, <=}c_i (i.e. with one variable). Creating them this way doesn't feel very "pythonic", so I'd like to implement a function which takes expressions, and creates dummy variables so that constraint expr <=a OR expr >= b is converted to (expr == dummy_var) AND (dummy_var <= a OR dummy_var >=b)

A few questions:

1. does this seem like a reasonable approach?
2. any suggestions for telling whether two expressions are the same? it would be helpful to be able to order & compare expressions so that we do not introduce more dummy variables than we need to, & handle all dummy bounds for the same expression in the same contiguous region of a loop.
3. is it the responsibility of the library or the user to handle (a<=expr<=b) OR (z<=expr<=w) where z<w? I haven't looked closely enough (yet) to see if bounddisjunction already handles this, but maybe somebody with more experience already knows.
4. Is there a way to indicate to SCIP that these dummy variables are not part of the original problem? At least in model.addVar it does not seem possible.

Thanks!

[Opt-Mucca]

Am all for adding support for bound disjunction constraints! That would provide some nice functionality to users, and I've at least observed myself that they're important for many of the MIPs I solve. I disagree on the not pythonic view. It looks pretty natural to me. For the below points I'll hit them one-by-one:

1. It is a reasonable approach. I'd be interested in which scenarios it nets a performance improvement, or in which scenarios presolving already performs a similar operation. As for adding it directly to PySCIPOpt, it would have to be added to the recipes portion (will tag @Joao-Dionisio if you have more questions on that). By default, we don't want to do any extra modelling for the user. It is ultimately the users responsibility to model their problem, and it would cause confusion if we "improved" their model at the modelling stage. An example confusion for this specific application would be on why there are now two constraints instead of one, and why the constraint type they thought they were adding isn't there. The base of PySCIPOpt should just be focused on an interface to SCIP. Because this is frustrating for some, e.g. for non-linear objectives not being supported via PySCIPOpt, some other developers are starting a recipes submodule that has modelling helper functions.
2. For linear expressions you can just compare the coefficient, and for polynomial expressions you could just sort through each term and compare the powers. I don't think there's an easy way to do for this general non-linearities though.
3. See my response to point 1 for this. It's the responsibility of the user, and I at least am fundamentally against default handling of this responsibility.
4. There is not. This is one of the many problems with modelling assistance. The recipes extension will probably need to implement some extra functionality for this.

Thanks for all your work on this! Hope the answers were helpful.

[ctdunc]

Am all for adding support for bound disjunction constraints! That would provide some nice functionality to users, and I've at least observed myself that they're important for many of the MIPs I solve. I disagree on the not pythonic view. It looks pretty natural to me. For the below points I'll hit them one-by-one:

1. It is a reasonable approach. I'd be interested in which scenarios it nets a performance improvement, or in which scenarios presolving already performs a similar operation. As for adding it directly to PySCIPOpt, it would have to be added to the recipes portion (will tag @Joao-Dionisio if you have more questions on that). By default, we don't want to do any extra modelling for the user. It is ultimately the users responsibility to model their problem, and it would cause confusion if we "improved" their model at the modelling stage. An example confusion for this specific application would be on why there are now two constraints instead of one, and why the constraint type they thought they were adding isn't there. The base of PySCIPOpt should just be focused on an interface to SCIP. Because this is frustrating for some, e.g. for non-linear objectives not being supported via PySCIPOpt, some other developers are starting a recipes submodule that has modelling helper functions.

2. For linear expressions you can just compare the coefficient, and for polynomial expressions you could just sort through each term and compare the powers. I don't think there's an easy way to do for this general non-linearities though.

3. See my response to point 1 for this. It's the responsibility of the user, and I at least am fundamentally against default handling of this responsibility.

4. There is not. This is one of the many problems with modelling assistance. The recipes extension will probably need to implement some extra functionality for this.

Thanks for all your work on this! Hope the answers were helpful.

Recipes does seem like a good place to handle this. Will check out hopefully next week :)

[Joao-Dionisio]

Any updates on this @ctdunc?

[ctdunc]

Apologies -- we ended up going a slightly different direction on the project this was relevant for, so I ended up not having bandwidth to complete at work. I'd like to come back to it soon, though, to test.

[Joao-Dionisio]

Hey @ctdunc! How close is this to being done? Can we help with the final steps somehow?

[ctdunc]

Still the same situation unfortunately. If you want to clear out your backlog I can close and reopen if i ever get a chance to revisit.