On PreSOS1BigM Parameter
Answered
Consider a bunch of constraints of type \sum_{i\in N} x_{i} = 1, x_{i} \in {0,1}. If I model them as SOS1 constraints and set the PreSOS1BigM parameter equal to 0, will GUROBI perform GUB branching on these SOS1 constraints?
-
If parameter PreSOS1BigM is set to 0 then the SOS constraints of type 1 are not reformulated with linear constraints. In this case, these SOS constraints are not part of the LP relaxation. They are included in branching if they are violated.
0 -
Thank you very much for your reply. Couple of follow-up questions:
how are they included in the branching? Is it through GUB branching or through some other method?
0 -
I am not quite sure what you mean by GUB branching.
If an SOS constraint is not satisfied then more than 1 variable is different from 0. The branching is done on these variables, for example, one of them or a subset is fixed to 0.
Does this answer your question?0 -
Yes. This answers my question. Thank you very much.
What I meant by GUB branching can be found in the following IJOC paper (Section 2.2): https://pubsonline.informs.org/doi/abs/10.1287/ijoc.11.2.173
Fixing a subset of variables in the SOS1 constraint to zero in one of the branches (and its complement to 0 to zero in another branch) is what is termed in the literature as Generalized Upper Bound (GUB)/SOS branching.
Is it possible to know how these subset of variables (to set to zero in one branch) are chosen in Gurobi?
0 -
I am afraid we cannot give you more details on this.
May I ask the intention of the question? Do you want to use Gurobi for some kind of benchmark that requires some knowledge of how SOS constraints are handled?
0 -
Thank you very much for your help. I am trying to solve a MIP model using Gurobi for my research that has a bunch of SOS1 constraints. I think SOS1 branching may be more effective for my model than the reformulation and thus, I am curious how SOS1 branching is handled in Gurobi.
0 -
I am sorry but I cannot give you more details. But it is interesting that your model can be solved more efficiently if the SOS constraints are not reformulated. Did you also experiment with the parameter PreSOS1Encoding?
0 -
Yes, I did. It seems to work better without the reformulation.
0
Please sign in to leave a comment.
Comments
8 comments