3
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ What if there is a solution in which $x_i < \epsilon$? $\endgroup$ Commented May 21 at 15:54
  • $\begingroup$ 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. $\endgroup$
    – prubin
    Commented May 21 at 16:05
  • $\begingroup$ So the answer to my initial question is "no"? $\endgroup$ Commented May 21 at 16:10
  • $\begingroup$ 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$)? $\endgroup$
    – Kuifje
    Commented May 21 at 19:12
  • $\begingroup$ @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? $\endgroup$
    – D.W.
    Commented May 21 at 23:17

Your Answer

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

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