# MILP constrained by the minimum number of satisfied constraints

I have an MILP where we have $$t_k = \sum_i P_i\cdot C_{ik} : P_i\ \in \{0,1\}, C_{ik} \in I^+$$

and our model is constrained by the number of times $$t_k$$ is bigger than a certain value $$T_k$$.

$$\left[\sum_k\left(t_k \ge T_k\right)\right] \ge N$$

where $$N$$ is the minimum number of constraints to be satisfied.

Can this problem be solved in MILP and how? I am new to this domain and any leads would be very helpful.

• Are $P_i$ and $C_{ik}$ both variables?
– prubin
Mar 22, 2021 at 20:37
• $P_i$ is a binary variable. $C_{ik}$ is a positive constant. Mar 23, 2021 at 5:59

You can introduce a binary variable $$x_k$$ and linear constraints \begin{align} \sum_k x_k &\ge N\tag1\\ -t_k+T_k&\le M_k(1-x_k) &&\text{for k\in K}\tag2 \end{align} Here, the “big-M” constant $$M_k$$ is a small upper bound on $$-t_k+T_k$$. Because $$t_k\ge 0$$, you can take $$M_k=T_k$$, and the constraint simplifies to $$t_k\ge T_k x_k$$.
Constraint $$(1)$$ forces at least $$N$$ of the $$x_k$$ variables to be $$1$$. Constraint $$(2)$$ enforces the logical implication $$x_k=1\implies t_k\ge T_k$$.