How to handle SOS type 1 and SOS type 2 constraints?
AnsweredHello,
Some constraints of my model involve general constraints:
A = min[B, x] & B = piecewise linear function of x
So, Gurobi converts these constraints into SOS type 1 and type 2 constraints during the presolve stage, then moves to MIPNode stage. The problem is that Gurobi takes a long time for the MIPNode stage. (For the size of the instance, please refers to the statistics below)
Optimize a model with 16904 rows, 25632 columns and 57162 nonzeros
Model has 12996 general constraints
Variable types: 25632 continuous, 0 integer (0 binary)
Coefficient statistics:
Matrix range [1e03, 1e+04]
Objective range [7e+01, 7e+04]
Bounds range [1e+05, 7e+06]
RHS range [6e+00, 7e+03]
PWLCon x range [3e+00, 1e+06]
PWLCon y range [4e+00, 4e+05]
Presolve removed 25423 rows and 46696 columns (presolve time = 5s) ...
Presolve added 13191 rows and 46212 columns
Presolve time: 5.76s
Presolved: 30095 rows, 71844 columns, 213165 nonzeros
Presolved model has 9443 SOS constraint(s)
Variable types: 71262 continuous, 582 integer (582 binary)
Root relaxation presolve removed 3601 rows and 11915 columns
Root relaxation presolved: 26494 rows, 59929 columns, 174117 nonzeros
My question is as follows:
1) Any better formulation for my general constraints for A & B? (e.g., using BigM)
2) Any SOSdedicated cuts supported in Gurobi? I'm reading some papers for SOS cuts but I am wondering if such cuts already have been applied to Gurobi as these papers were published more than 10 years ago.
Appreciated,
Eunseok Kim

Hi,
1) Any better formulation for my general constraints for A & B? (e.g., using BigM)
Since it is generally more efficient to capture SOS constraints as linear constraints, the Gurobi presolve would automatically reformulate the SOS constraints into their binary forms using bigM values if a very large M is not required. The user has control over this behavior using the parameters PreSOS1BigM and PreSOS2BigM.
2) Any SOSdedicated cuts supported in Gurobi? I'm reading some papers for SOS cuts but I am wondering if such cuts already have been applied to Gurobi as these papers were published more than 10 years ago.
Each general constraint in Gurobi has an equivalent MIP formulation including auxiliary variables and linear and SOS constraints. Adding such constraints to a continuous model would transform it to a MIP where the SOS constraints are not included in the root LP relaxation and are addressed with branching rules. If an SOS constraint is not reformulated into a binary form during presolve, it is not included in the root LP relaxation and does not participate in cutting plane generation. Which paper are you referring to?
Best regards,
Maliheh
0 
Hi Maliheh,
Thanks for your prompt response.
According to the log, it seems like Gurobi converted general constraints into SOS constraints.
1) Does it mean that Gurobi converted the general constraints into binary form with bigM during presolve stage? or left it as SOS constraints? I'm confused about whether these general constraints were included in the root LP relaxation or not.
2) I have read the description of parameters PreSOS1BigM and PreSOS2BigM. It tells that large BigM may cause numerical issues. But I'm unsure of the appropriate values for these constraints as I can't figure out the form of SOS constraints converted by Gurobi presolve. Could you provide further explanation on this topic? I guess that if I choose too small values, then the model will become infeasible.
3) List of papers I'm referring to:
 M. Zhao and I. R. de Farias Jr. The Piecewise Linear Optimization Polytope: New Inequalities and Intersection with SemiContinuous Constraints. Mathematical Programming, pages 139, 2012.
 I. de Farias, E. L. Johnson, and G. L. Nemhauser. Facets of the Complementarity Knapsack Polytope. Mathematics of Operations Research, 27(1):210226, 2002Best regards,
Eunseok Kim
0 
Hi,
1) The log shows:Presolved model has 9443 SOS constraint(s)
This implies that all SOS constraints are not reformulated into their binary forms. The 9443 SOS constraints will not be part of the LP root relaxation and will be addressed using branching rules.
2) You need to do some experimentation to find out what the appropriate M value for your problem is. As the values of these parameters increase, the likelihood of reformulating all the SOS constraints into their binary forms increase. It is also important to make sure you define the tightest possible finite bounds for all the variables participating in the general constraints.
In case you are using the Gurobi Python API, you can write the presolved model into a file using the method Model.presolve() to find out the type of the SOS constraints in your model. The simple general constraints are usually translated into a MIP using SOS1 constraints and the function constraints are translated into a MIP using SOS2 constraints.
3) Cutting planes are an integral part of the Gurobi optimizer and there are various globally valid cuts implemented in Gurobi. If you search for the word “Cuts” in the Gurobi Parameter Descriptions page, you will see the various cuts implemented in Gurobi. However, as mentioned, the SOS constraints that remain in the presolved model are addressed using branching rules and are not part of the LP relaxation and cutting plane generation.
Best regards,
Maliheh
0
Please sign in to leave a comment.
Comments
3 comments