3
$\begingroup$

I have the following constraint in my model:

$$x = 0 \lor \sum_{i=1}^n y_i = 3$$ where $x$ and $y_i$ are all binary variables.

How this can be linearized by means of big-M notation?

Should I include additional slack variables, or?

$\endgroup$
1
  • $\begingroup$ In the upcoming Mosek version 10 you can specify such constraints directly. $\endgroup$ Commented Mar 1, 2022 at 10:17

1 Answer 1

7
$\begingroup$

You do not need another variable. Your disjunction is equivalent to $$x=1 \implies \sum_{i=1}^n y_i = 3,$$ which you can enforce via big-M constraints $$M_1(1-x) \le \sum_{i=1}^n y_i - 3 \le M_2(1-x).$$ I leave to you the determination of good (small) choices of $M_1$ and $M_2$.

Some solvers also support such indicator constraints directly, without requiring you to explicitly impose big-M constraints.

$\endgroup$
5
  • $\begingroup$ Thanks @RobPratt for your amazing and quick answer. I have a model implemented in CPLEX by means of logical constraints. Now, I want to do it by linearizing the constraints. Some of them are not that simple. Yes, I have read that CPLEX is doing the transformation via indicator constraints. Do you think that my linearization (and carefully chosen M constants) implemented by CPLEX would yield better performances, than the direct logic-based model (with logic-based constraints)? $\endgroup$
    – ORLover
    Commented Feb 28, 2022 at 20:12
  • $\begingroup$ Also, concerning the previous case, what if I would make more complex constraint, such as $x= 0 \vee \sum_{i}y_i = 3 \vee \sum_{j} p_j = 1$. Could this be linearized by following: $M_1(1-x) - M_1(1-y_1) \leq \sum_i y_i -3 \leq M_2 (1-x)$, $M_1(1-x) - M_1(1- y_2) \leq \sum_j p_j - 1 \leq M_2 (1-x),$ $y_1 + y_2 \geq 1, y_1, y_2 \in \{0,1\}$? Or, I misunderstood it somehow ... $\endgroup$
    – ORLover
    Commented Feb 28, 2022 at 20:12
  • 1
    $\begingroup$ Glad to help. Please mark my answer as accepted. I don't know what CPLEX will do in those two cases; I recommend trying both ways. For your more complex constraint, it appears that you are using $y$ to refer to both original variables and variables introduced for linearizing the disjunction. $\endgroup$
    – RobPratt
    Commented Feb 28, 2022 at 20:42
  • $\begingroup$ Sorry, I was quick by writing the solution. Here is what I wanted to write: $M_1(1-x) - M_1(1-t_1) \leq \sum_i y_i -3 \leq M_2 (1-x)$, $M_1(1-x) - M_1(1- t_2) \leq \sum_j p_j - 1 \leq M_2 (1-x),$ and $t_1 + t_2 \geq 1, t_1, t_2 \in \{0,1\}$. I think this works?! $\endgroup$
    – ORLover
    Commented Feb 28, 2022 at 20:47
  • 1
    $\begingroup$ $M_1 (1-t_1) \le \sum_i y_i - 3 \le M_2(1-t_1)$, $M_3 (1-t_2) \le \sum_j p_j - 1 \le M_4(1-t_2)$, $t_1+t_2 \ge x$ $\endgroup$
    – RobPratt
    Commented Feb 28, 2022 at 21:12

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.