Do solvers use GUB/SOS1 branching?

Question

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.

score 9 · Answer 1 · answered Nov 25 '19 at 16:20

9

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.

answered Nov 25 '19 at 16:20

EhsanK

5,864
3
17
54

1

To complete @EhsanK said, SCIP has a facility to deal with it. Please, see this link. – A.Omidi Nov 26 '19 at 10:32

Oguz Toragay · Accepted Answer · 2019-12-02T20:07:06.053

6

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.

edited Dec 02 '19 at 20:07

answered Nov 25 '19 at 16:55

Oguz Toragay

8,652
2
13
41

Nikos Kazazakis · Answer 3 · 2019-11-25T23:23:49.873

2

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.

edited Nov 25 '19 at 23:23

answered Nov 25 '19 at 23:18

Nikos Kazazakis

12,121
17
59

Do solvers use GUB/SOS1 branching?

3 Answers3

Linked