# Conditional constraint activated by binary variables

I have the following situation in a Mixed Integer Program: $$x_1, \dots, x_n$$ are binary variables, and $$y, z$$ are continuous. If $$k$$ or less variables $$x_i$$ are set to $$1$$, then I need to have $$y \leq z$$. That is,

$$\sum_{i=1}^nx_i \leq k \implies y \leq z$$

I need to include this conditional constraint in my MIP formulation.

One approach would be to create an auxiliary binary variable $$w$$ and include these big-M constraints:

$$\sum_{i=1}^nx_i \geq k + 1 - Mw$$ $$y \leq z + M(1 - w)$$

But, because of the structure of this condition, I have the feeling that this could be done with only one big-M constraint, without the auxiliary variable $$w$$. Is there another way to model that conditional constraint? If possible, it would greatly reduce the size of my formulation, because I already have lots of these constraints.

• Just a minor comment: Creating a more compact model with fewer constraints is not necessary something that leads to a problem which solves faster. On the contrary, it could easily be that it hides the combinatorial structure of the problem, leading to worse performance – Johan Löfberg Feb 23 '19 at 9:42
• Seconding Johan's comment, when I'm using a commercial solver such as CPLEX, and generally assume that whoever designed the presolver was smarter than I am (fairly safe bet), so I let it do any model shrinking. – prubin Feb 23 '19 at 21:14
• Thanks, I'm going to try this approach then. I did some research and this seems to be the way this kind of constraint is modeled indeed. – henriquefalc Mar 12 '19 at 2:42

I don't see any way to avoid the extra binary variable $$w$$ or the two extra constraints. I do want to point out that your first constraint, while correct in spirit, is slightly off in indexing. As stated, it allows $$w$$ to be 0 when $$\sum x_i =k$$, whereas you want to force $$w=1$$ in that case. Changing it to $$\sum x_i \ge k+1 -(k+1)w$$ both fixes the issue and gives you are moderately tight choice of $$M$$ for that constraint.