10
$\begingroup$

GUB/SOS1 branching is an old and well-known idea (see for example page 9 of Jeff Linderoth's notes).

Is this implemented in commercial solvers these days?

The Gurobi documentation mentions SOS1 constraints, but never mentions SOS1 branching.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
6
$\begingroup$

I found in the IBM website that: CPLEX automatically converts SOS1 constraints on binary variables into a regular set packing constraint(source).

On page 80 of this presentation by Jeff Linderoth, it is mentioned that some noncommercial solvers like CBC and Ip_solve SOS(2) branching while CBC and MINTO equipped with GUB branching.

Improve this answer
$\endgroup$
9
$\begingroup$

If you accept non-commercial solvers too, then SCIP seems to have it. From the link:

constraints/sos1/branchingrule to decide whether to use neighborhood, bipartite, or SOS1 branching...

AIMMS also seems to have a mention of SOS1 branching according to page 9 of this manual.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ To complete @EhsanK said, SCIP has a facility to deal with it. Please, see this link. $\endgroup$
    – A.Omidi
    Nov 26, 2019 at 10:32
2
$\begingroup$

It's actually quite common, on top of what other people mentioned, I believe MINOTAUR and Couenne support that too, and as of the December release, so will Octeract Engine.

Improve this answer
$\endgroup$

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.