When linearizing a separable nonlinear function is there an advantage/disadvantage in using SOS2 sets in comparison to using binary variables?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
Mathematically they are equivalent, but some solvers will exploit SOS2 structure with customized branching rules. Here is IBM's explanation of this for CPLEX.
-
$\begingroup$ I read somewhere, I don't know where anymore, that using binary variables might lead faster to the optimal solution because of the advances made in the MILP field. I tried this out on a model I have developed but the results are disappointing. In my case, introducing binaries is far worse than using SOS2. Unfortunately, this observation, doesn't prove anything; in another case the results might be the opposite. $\endgroup$– ClementAug 4, 2020 at 7:19
-
$\begingroup$ IBM writes: "If there is no ordered relationship among the variables (such that weights cannot be specified or would not be meaningful), other formulations should be used instead of a special ordered set." Can you imagine, what order relationship might exist, between the members of an SOS2 that models the piecewise linearization of a separable function? $\endgroup$– ClementAug 4, 2020 at 7:25
-
$\begingroup$ For SOS2 (in CPLEX), I believe that the weights are used to sort the variables, which in turn defines which pairs of variables are "adjacent". So you could, for instance, assign weights 1, 2, ... according to the indexing of the breakpoints. $\endgroup$– prubin ♦Aug 5, 2020 at 17:46