# How can I formulate this specific if-then constraint?

IF $$\sum\limits_d X_{i,d}\ge6$$ THEN $$Y_i = 1$$ (strictly)

AND

IF $$\sum\limits_d X_{i,d}<6$$ THEN $$Y_i = 0$$ (strictly)

$$X$$ and $$Y$$ are binary variables.

What I'm actually trying to do is to charge the objective function some value whenever $$Y_i = 1$$. That is, for each $$i$$, if $$Y_i=1$$, the term $$C\cdot Y_i$$ is charged in the objective function only and only if $$\sum\limits_d X_{i,d}\ge6$$.

Here are some more details about the problem if needed.

• $$I =$$ set of workers (a total of 5 workers);

• $$D =$$ set of days (a total of 6 days);

• $$C=$$ cost for each worked day is fixed.

If a worker worked for 6 days, then the cost of the sixth day is double the normal cost i.e. $$= 2C$$.

Define $$X_{i,d} = 1$$ if worker $$i$$ works on day $$d$$ and 0 otherwise, so I want to charge the objective function a cost if the sum of $$X_{i,d}$$ over $$d$$ equals $$6$$ for each $$i\in I$$.

How can introduce such a variable that would charge the objective function?

• Would be so nice to just write $Y_i \gets (\sum_i X_i \geq 6)$ when using a MILP solver. – LocalSolver Nov 16 '20 at 9:14
• – ktnr Nov 17 '20 at 15:55
• Thank you very much for the links above, ktnr. @MAHER will surely be interested in using that to avoid the tedious linearization works described below. – LocalSolver Nov 18 '20 at 14:25

For simplicity, I will drop the $$i$$ subscripts everywhere and instead write $$x_d$$ for $$x_{i,d}$$ and $$y$$ for $$y_i$$.

The linear constraint $$\sum_{d=1}^6 x_d \le 5 + y$$ enforces $$\sum_{d=1}^6 x_d > 5 \implies y=1.$$ You can derive this constraint via conjunctive normal form as follows: $$\left(\land_{d=1}^6 x_d\right) \implies y \\ \lnot\left(\land_{d=1}^6 x_d\right) \lor y \\ \left(\lor_{d=1}^6 \lnot x_d\right) \lor y \\ \sum_{d=1}^6 (1-x_d) + y \ge 1 \\ \sum_{d=1}^6 x_d - y \le 5 \\$$

The objective will drive $$y=0$$ otherwise, but if you want to explicitly enforce it, you can again use conjunctive normal form: $$\neg\left(\land_{d=1}^6 x_d\right) \implies \lnot y \\ \left(\land_{d=1}^6 x_d\right) \lor \lnot y \\ \land_{d=1}^6 (x_d \lor \lnot y) \\ x_d + (1 - y) \ge 1 \quad \text{for d\in\{1,\dots,6\}} \\ x_d \ge y \quad \text{for d\in\{1,\dots,6\}}$$

• Thanks a lot! you are amazing! you made it sound too easy. – MAHER Nov 16 '20 at 12:57
• Just for future readers of this question, note that this enforces the "if" part but not the "only if" (sum less than 6 implies $y = 0$). From the context of the original question, $y=1$ increases a cost that is presumably being minimized, so the solver will set $y=0$ whenever it is allowed to. – prubin Nov 16 '20 at 22:48
• @prubin I added the converse just now. – RobPratt Nov 17 '20 at 0:32
• @RobPratt So when formulating the problem all constraints should be put together !? The way i see it is that if the following is added xi+(1−yi)≥1for i∈{1,…,6}xi≤yifor i∈{1,…,6} It goes against the first formulation ∑i=16xi−yi≤5 . Please correct if I'm wrong. I'm still learning. – MAHER Nov 17 '20 at 1:47
• The point raised by @prubin is that you could have $y_i=1$ even if all $x_i=0$. The objective discourages that, but it is still feasible unless you explicitly prevent it, as I did in my updated answer. – RobPratt Nov 17 '20 at 1:55

then all you need is: $$Y \ge (\sum X_d) - 5 \ \ \& \ \ Y \le (\sum X_d)/5.$$ This can be written in a solver:
$$\forall$$ worker $$i$$, you can just add $$Cy_i$$ to the cost function and add the constraint $$\sum_{d=1}^6 x_{id} \leq 5 + y_i$$.
(Note that $$y_i$$ can be declared as either continuous or binary.)