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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ In the upcoming Mosek version 10 you can specify such constraints directly. $\endgroup$– ErlingMOSEKMar 1, 2022 at 10:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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.
-
$\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$– ORLoverFeb 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$– ORLoverFeb 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$– RobPrattFeb 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$– ORLoverFeb 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$– RobPrattFeb 28, 2022 at 21:12