We've been working on a new feature for Octeract Engine, namely to automatically extract SOS structure from a model and then exploit it.

While the literature is quite rich on what to do with SOS once we have them, I couldn't find any work on how to algorithmically detect the structure. So far we just home-brewed the detection algorithm and it works pretty well, but I was curious whether there's some theoretical work on the subject out there.

I'm aware that such detection will have bad theoretical complexity, however this is not an issue for us, so if you are aware of a bad complexity algorithm do post an answer - the engine uses Octeract Reformulator technology so we can easily detect abstract mathematical structure even in very large problems with or without set notation.

  • 3
    $\begingroup$ Is it no common for optimizers to convert SOS1 constraints to ordinary binary constraints? I recall a talk from Bob Bixby with that message. So there might be no advantage of detecting SOS1 constraints. I am looking to hear what the other experts writes. $\endgroup$ – ErlingMOSEK Dec 9 '19 at 12:58
  • $\begingroup$ Hi @ErlingMOSEK, yes, the main difference of our approach is on the detection side: we detect SOS1 and SOS2 without the user declaring them as such, and we detect SOS structure in non-linear expressions. $\endgroup$ – Nikos Kazazakis Dec 9 '19 at 13:14

Your Answer

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

Browse other questions tagged or ask your own question.