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


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?

  • $\begingroup$ Would be so nice to just write $Y_i \gets (\sum_i X_i \geq 6)$ when using a MILP solver. $\endgroup$
    – Hexaly
    Nov 16, 2020 at 9:14
  • $\begingroup$ Well, sure thing. $\endgroup$
    – ktnr
    Nov 17, 2020 at 15:55
  • $\begingroup$ 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. $\endgroup$
    – Hexaly
    Nov 18, 2020 at 14:25

2 Answers 2


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\}$} $$

  • $\begingroup$ Thanks a lot! you are amazing! you made it sound too easy. $\endgroup$
    – MAHER
    Nov 16, 2020 at 12:57
  • $\begingroup$ 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. $\endgroup$
    – prubin
    Nov 16, 2020 at 22:48
  • 1
    $\begingroup$ @prubin I added the converse just now. $\endgroup$
    – RobPratt
    Nov 17, 2020 at 0:32
  • $\begingroup$ @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. $\endgroup$
    – MAHER
    Nov 17, 2020 at 1:47
  • $\begingroup$ 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. $\endgroup$
    – RobPratt
    Nov 17, 2020 at 1:55

I thought about the following:

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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.