1
$\begingroup$

I would like to model the following:

$B \le \alpha \implies \sum_i W(i) \ge \beta$, where $B$ a continuous variable, $W(i)$ binary variables, $\alpha$ a real constant number, $\beta$ an integer constant number

I could do this by introducing a new binary variable $Z$ and requiring

$B \le \alpha \implies Z = 1$ and $Z =1 \implies \sum_i W(i) \ge \beta$

My question is, is there a possibility of avoiding the introduction of $Z$?

$\endgroup$
8
  • $\begingroup$ Related: or.stackexchange.com/questions/10172/… $\endgroup$
    – RobPratt
    Jan 31 at 0:33
  • $\begingroup$ Here the constraint $\sum_i W(i) \ge \beta $ is an all integer constraint. Could this somehow avoid the introduction of $Z$? $\endgroup$
    – Clement
    Jan 31 at 8:44
  • $\begingroup$ Dear @RobPratt, in a case, where one of $w_i$ is equal to one, then $B \leq \alpha \implies w = 1$. That can be linearized without any more binary variables. Would you say, does not any general procedure exist to do that? $\endgroup$
    – A.Omidi
    Jan 31 at 9:39
  • $\begingroup$ I should state that $1 \le \beta \le \lvert I \rvert, i \in I$ $\endgroup$
    – Clement
    Jan 31 at 15:24
  • $\begingroup$ Do you also have bounds on $B$ and $\alpha$? $\endgroup$
    – RobPratt
    Jan 31 at 17:15

1 Answer 1

3
$\begingroup$

As in How to enforce logical implication $\sum_j a_j x_j \le b \implies \sum_j c_j x_j \le d$, (temporarily) introduce constant $\epsilon>0$ and binary variable $Z$, and impose linear big-M constraints \begin{align} \alpha + \epsilon - B &\le (\alpha + \epsilon - 0) Z \tag1\label1 \\ \beta - \sum_i W_i &\le (\beta - 0) (1-Z) \tag2\label2 \end{align} Now eliminate $Z$ by multiplying \eqref{1} by $\beta$ and \eqref{2} by $\alpha + \epsilon$ and adding them up to obtain the valid inequality $$\beta(\alpha + \epsilon - B) + (\alpha + \epsilon)\left(\beta - \sum_i W_i\right) \le \beta(\alpha + \epsilon) Z + (\alpha + \epsilon) \beta (1-Z),$$ which simplifies to $$B + \frac{\alpha + \epsilon}{\beta}\sum_i W_i \ge \alpha + \epsilon. \tag3\label3$$

But this is too weak unless $B=0$ or $\sum_i W_i = 0$. The original disjunction $$B \ge \alpha + \epsilon \lor \sum_i W_i \ge \beta$$ is nonconvex, and \eqref{3} is a convex relaxation.

$\endgroup$
1
  • $\begingroup$ Thank you very much Rob . I will implement it and see. $\endgroup$
    – Clement
    Jan 31 at 20:08

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.