3
$\begingroup$

When linearizing a separable nonlinear function is there an advantage/disadvantage in using SOS2 sets in comparison to using binary variables?

$\endgroup$

1 Answer 1

1
$\begingroup$

Mathematically they are equivalent, but some solvers will exploit SOS2 structure with customized branching rules. Here is IBM's explanation of this for CPLEX.

$\endgroup$
3
  • $\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$
    – Clement
    Aug 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$
    – Clement
    Aug 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.