3
$\begingroup$

I investigating various aspects of MIP and I can see that my current modelling langaunge support Special Ordered Sets(https://python-mip.readthedocs.io/en/latest/sos.html) but looking at the papers they are from 1978 and 1984, and there seems very little online material about them and which leaves me the question should I use these and does any body having good experiences of using them in recent time?

$\endgroup$
3
  • 1
    $\begingroup$ What prevents you of using them? If you experience a positive effect on your problem then you can be happy; if not just think about something else. $\endgroup$
    – Clement
    Dec 22 '20 at 15:30
  • 1
    $\begingroup$ In many (but not all) cases, formulations with binary variables are faster. Solvers like binary variables. Of course, SOS formulations can help if you don't have good bounds and they help with formulating interpolations. $\endgroup$ Dec 22 '20 at 21:13
  • 2
    $\begingroup$ Bob Bixby in a talk I saw said that SOS mostly was converted to standard binary variable form in most cases. This supports the statement of Erwin. Note MIP codes of today are very different from those in 1984. $\endgroup$ Dec 23 '20 at 6:33
4
$\begingroup$

As long as the solver you pass that information to also supports SOS, and as long as the modelling environment has an SOS interface for that solver, you can notice massive differences in performance for some problems. As usual, this is not always the case, but it works great a lot of the time.

You can see why (from a more intuitive point of view than the papers) in Jeff Linderoth's lecture notes on SOS.

$\endgroup$
2
  • $\begingroup$ Do you have empirical experiences with it your self? $\endgroup$ Dec 22 '20 at 14:39
  • 2
    $\begingroup$ Yes I do, the main benefit is that it reduces the combinatorial search space. If it's applicable, then trees that might have otherwise generated a massive number of nodes before convergence can instead converge in a relatively small number of iterations. $\endgroup$ Dec 22 '20 at 15:17
3
$\begingroup$

There are two aspects to Special Ordered Sets. The first is that they can make the model definition simpler and thereby make the intent clearer.

The second is that a particular solver may use dedicated algorithms to assist solution times.

As originally developed, there are two types of Special Ordered Sets. The first, SOS1, is used when it is required to select exactly one option from a choice of several. The second type, SOS2 are used to select one or two (adjacent) variables and are typically used to approximate a non-linear function (objective or constraint) by a set of piece-wise linear elements.

The only real potential downside is that if it is required to port the model to some other environment the Special Ordered Sets may not be available or defined in a different way. However, this can be overcome if it arises and I wouldn't consider it as a major drawback.

$\endgroup$
2
  • $\begingroup$ Might be me misunderstanding SOS1, but it seems as if it is not exactly one option. But at most one option. At least when I use it in Python MIP. I would much have preferred the exactly one option. But that is not what the constraint does. $\endgroup$ Dec 26 '20 at 20:08
  • 1
    $\begingroup$ Exactly one from several is how SOS1 sets were originally defined (In another life I did some work on the codes initiated by Martin Beale). This is reflected in H. P. Williams's book on model building. If this is not how they are implemented in some solvers then it's easily modified with a supplementary constraint requiring the variables to sum to one if this is required. $\endgroup$
    – normanj
    Dec 27 '20 at 22:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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