# Restrict the number of non-zero variables to any constant in MILP

I am designing an MILP in which given a set $$[n]$$ of $$n$$ agents, we create for each $$i \in [n]$$ a real variable $$x_i$$. The variables $$x_i$$ are between 0 and 1 ($$0 \leq x_i < 1$$). I would like to restrict the number of times $$x_i = 0$$ to any integer constant $$m$$.

Is there any way to do this using some linear constraints?

Define binary variable $$y_i$$ for each $$i$$. Let $$\epsilon$$ be a small constant close to $$0$$. You can enforce the desired constraints by adding the following:

\begin{align} \epsilon y_i \le x_i &\le y_i \quad \forall i \tag{1}\\ \sum_i (1-y_i) &\le m \tag{2} \end{align}

Constraints $$(1)$$ enforce $$y_i = 0 \implies x_i = 0$$ and $$y_i=1 \implies x_i\ge \epsilon >0$$. Constraints $$(2)$$ impose that the number of times $$y_i=0$$ (and thus $$x_i$$) is smaller than $$m$$.

• What if there is a solution in which $x_i < \epsilon$? Commented May 21 at 15:54
• If there is an optimal solution to the original problem with $x_i < \epsilon,$ you won't find it, and will end up with a suboptimal solution. This is essentially the price of doing business, because (for a variety of reasons) optimization models do not tolerate strict inequality constraints.
– prubin
Commented May 21 at 16:05
• So the answer to my initial question is "no"? Commented May 21 at 16:10
• I would not say that. What does $x_i$ represent exactly ? If you set for example $\epsilon = 10^{-6}$, what are you missing (in terms of $x_i$)? Commented May 21 at 19:12
• @SamuelBismuth, let me turn it back to you -- can you give an example where it matters, i.e., where the best solution returned by this heuristic differs substantially from the optimal solution to your original system of constraints?
– D.W.
Commented May 21 at 23:17