Wednesday, November 4, 2009

SOS variables vs binary variables

Reading the response in http://code.msdn.microsoft.com/solverfoundation/Thread/View.aspx?ThreadId=2485 I was thinking that I probably would model the constraint

(x-1)*(x-2) == 0

differently than the proposed SOS1 formulation. In general an OR can be modeled with a single binary variable (of course in this special case we can model x=1 OR x=2 as x = 1 + xb, where xb is a binary variable). The SOS1 formulation given in the thread is of course perfectly valid.

In practice I almost never use SOS1 sets. The reason for using SOS sets can be two-fold:

  • It makes the formulation easier
  • It improves performance

For SOS1 I often find a formulation with binary variables just as convenient. I don’t have hard data but I suspect that the performance gains resulting from using SOS1 variables are probably not that significant: I would suspect that solvers can use effective cuts on models with binary variable formulations. In addition, the SOS performance really benefits from good reference row weights, which I often don’t have (or in the case of GAMS cannot even specify).

For SOS2 variables (almost always in the context of a piecewise linear formulation) I find the SOS2 formulation helps in simplifying the formulation. E.g. GAMS does not have specific syntax to specify piecewise linear like AMPL, but with a SOS2 formulation, things are not that complicated. See: http://yetanothermathprogrammingconsultant.blogspot.com/2009/06/gams-piecewise-linear-functions-with.html. Also in this case it would be interesting to see if there is any computational advantage in using a specific approach: SOS2 or binary variables.