4
$\begingroup$

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?

$\endgroup$
0
6
$\begingroup$

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.

$\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.