1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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 $\endgroup$ – Johan Löfberg Feb 23 '19 at 9:42
  • $\begingroup$ 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. $\endgroup$ – prubin Feb 23 '19 at 21:14
  • $\begingroup$ 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. $\endgroup$ – henriquefalc Mar 12 '19 at 2:42
0
$\begingroup$

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.

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