11
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 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, 2019 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, 2019 at 13:14

1 Answer 1

Reset to default
3
$\begingroup$

There has been some research on algorithmically detecting SOS structure in optimization models. One approach is to use a graph-based algorithm to identify the structure of the model and detect the presence of SOS constraints.

The basic idea is to construct a graph representation of the optimization model, where the nodes represent the variables and the edges represent the constraints. Then, the graph is partitioned into strongly connected components, which represent groups of variables that are related to each other through the constraints. If a strongly connected component has a specific structure, such as a quadratic form, then it can be identified as an SOS constraint.

Improve this answer
$\endgroup$

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.