Skip to content

Bound Disjunction Constraints #858

Closed as duplicate
Closed as duplicate

Description

@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!

Activity

  1. Opt-Mucca commented on May 31, 2024

    @Opt-Mucca
    Collaborator

    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.

  2. ctdunc commented on May 31, 2024

    @ctdunc
    ContributorAuthor

    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 :)

  3. Joao-Dionisio commented on Jul 15, 2024

    @Joao-Dionisio
    Member

    Any updates on this @ctdunc?

  4. ctdunc commented on Jul 28, 2024

    @ctdunc
    ContributorAuthor

    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.

  5. Joao-Dionisio commented on Dec 19, 2024

    @Joao-Dionisio
    Member

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

  6. ctdunc commented on Dec 20, 2024

    @ctdunc
    ContributorAuthor

    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.

  7. Joao-Dionisio commented on Oct 15, 2026

    @Joao-Dionisio
    Member

    This is essentially already part of the big issue. We're just missing the recipe mentioned here, but I'll close to clear the issue page and just point the big issue to this one as well.

    Only 10 open issues, yoo-hoo!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions