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$ – LocalSolver Nov 16 '20 at 9:14
  • $\begingroup$ Well, sure thing. $\endgroup$ – ktnr Nov 17 '20 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$ – 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\}$} $$

  • $\begingroup$ Thanks a lot! you are amazing! you made it sound too easy. $\endgroup$ – MAHER Nov 16 '20 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 '20 at 22:48
  • 1
    $\begingroup$ @prubin I added the converse just now. $\endgroup$ – RobPratt Nov 17 '20 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 '20 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 '20 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, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.