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$ Commented Feb 23, 2019 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$ Commented Feb 23, 2019 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$ Commented Mar 12, 2019 at 2:42

1 Answer 1

Reset to default
1
$\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$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.