5

Most MIP solver's API have special methods to add SOS1-constraints of the form $$ \sum_{i \in I} c_i x_i \leq 1, \tag{1}$$ i.e. at most one of the binary variables $x_i, i \in I$ is allowed to take a non-zero value. As far as I know, writing $(1)$ as SOS1-constraint enables most solvers to use SOS1-branching, i.e. in Gurobi's Python API this means to

# Use this
model.addSOS(GRB.SOS_TYPE1, x, c)
# instead of
model.addConstr(sum(c[i]*x[i] for i in I) <= 1) 

Is there also a special method for a SOS1-constraint

$$ \sum_{i \in I} c_i x_i = 1, \tag{2}$$

i.e. exactly one of the binary variables takes a non-zero value?

Ronaldinho
  • 385
  • 2
  • 5

1 Answers1

7

I don't think

 model.addSOS(GRB.SOS_TYPE1, x, c)

is precisely the same as

 model.addConstr(sum(c[i]*x[i] for i in I) <= 1)

unless you add bounds like $x_i \in [0,1/c_i]$ to the SOS variables (and add another constraint to select one $x_i$).

For an "exactly one non-zero" you need the equality constraint.

Also, note that in many cases binary variables are better than SOS1 constructs (unless you need big-M constraints). This has to do with better bounding and cuts. Even for SOS2, binary variables can work better. In practice, I use SOS1 variables very rarely: binary variables and indicator constraints can handle most cases. Some solvers will even try to replace SOS1 variables by binary variables in the presolve phase.

Erwin Kalvelagen
  • 2,676
  • 1
  • 6
  • 11