1
$\begingroup$

H.P. Williams states in his book "Model Building in Mathematical Programming:

"An SOS1 is a set of variables (continuous or integer) within which exactly one variable must be non-zero."

So, if I have two binary variables a, b which also form a SOS1 then the SOS1 property together with the constraint a + b = 1 impose integrality on a, b and therefore I don't need to require explicitely the integrality of a,b.

CPLEX defines a SOS1 as:

"SOS Type 1 is a set of variables where at most one variable may be nonzero."

Is there a way to avoid explicitely requiring the integrality of a,b as in the case of Williams?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Using the CPLEX definition, the constraint $a+b=1$ with $a$ and $b$ forming a type 1 SOS still implies integrality of $a$ and $b.$

Note that avoiding an explicit integrality constraint is not necessarily a good thing. Solvers take integrality into consideration when doing presolve reductions and when computing cuts at nodes. If you do not specify integrality, the solver might or might not infer it from the SOS1 constraint, depending on the sophistication of the solver.

$\endgroup$
4
  • $\begingroup$ Yes, but in the case of CPLEX a + b = 1 implies the solutions (1,0) or (0,1) but not (0.0) which CPLEX's definition of SOS1 should allow. Requiring a + b <=1 allows all three binary combinations but also non binary values. $\endgroup$
    – Clement
    Jan 15 at 10:07
  • $\begingroup$ With $a+b\le 1$ I don't think there is a way to avoid declaring $a$ and $b$ to be integer. $\endgroup$
    – prubin
    Jan 15 at 16:01
  • $\begingroup$ Would the addition of a variable c help? The SOS1 is then {a,b,c} and I can add the constraint a + b + c = 1. This allows the solutions (1,0,0), (0,1,0), (0,0,1). The variable c should just not distruct the meaning of the model. $\endgroup$
    – Clement
    Jan 15 at 16:24
  • $\begingroup$ So $c$ would appear in just that one equation and the SOS1 set and nowhere else. That would seem to get the job done. $\endgroup$
    – prubin
    Jan 15 at 19:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.