0
$\begingroup$

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?

$\endgroup$
3
  • $\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

5
$\begingroup$

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

$\endgroup$
7
  • $\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
2
$\begingroup$

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

$\endgroup$

Your Answer

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