The shape of constraints in linear programming and MIP solvers
Let's say we have four variables, x1 through x4. And we want to select some combination of them such that
$ 2 <= x1 + x2 + x3 + x4 <= 4 $
Or
$ x1 + x2 + x3 + x4 = 0 $
We can't express this as a single inequality.
But if we introduce a deciding / auxiliary variable, y, we cover both cases by turning the
constraint on (y = 1) or off (y = 0) like so:
$ 2*y <= x1 + x2 + x3 + x4 <= 4*y $
I don't know how other solvers work, but the one I'm using now HiGHS does
not accept variables in the bounds themselves, so we have to move those terms
to the other size of the inequality (and separate to two inequalities). In the
process, we'll make both of them use <= 0 for uniformity.
Lower bound: $ 2*y <= x1 + x2 + x3 + x4 $ becomes $ 2*y - x1 - x2 - x3 - x4 <= 0 $
And upper bound: $ 2*y <= x1 + x2 + x3 + x4 <= 4*y $ becomes $ x1 + x2 + x3 + x4 - 4*y <= 0 $