PySCIPOpt icon indicating copy to clipboard operation
PySCIPOpt copied to clipboard

Bound Disjunction Constraints

Open ctdunc opened this issue 8 months ago • 4 comments

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!

ctdunc avatar May 29 '24 14:05 ctdunc