How can I formulate this specific if-then constraint?

Question

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?

Answer 1

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

Answer 2

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