2
$\begingroup$

I have a continuous variable $x_{ij}\in[0,1]$ and I need to write the following constraint: $$M_i-m_i+1\leq C_i$$ where $M_i=\max\{j: x_{ij}>0\}$ and $m_i=\min\{j: x_{ij}>0\}$

$\endgroup$
2
  • $\begingroup$ How are $M_i$ and $m_i$ defined if $x_{ij}=0$ for all $j$? $\endgroup$
    – RobPratt
    Commented Apr 27 at 16:11
  • $\begingroup$ That should not happen. For each $i$, we must have at least one $j$ such that $x_{ij}>0$. $\endgroup$
    – zdm
    Commented Apr 27 at 23:28

1 Answer 1

4
$\begingroup$

Let constants $j_\min$ and $j_\max$ be the smallest and largest possible $j$ indices, respectively. Introduce binary decision variable $y_{ij}$ to indicate whether $x_{ij}>0$. Assuming $x_{ij}>0$ for at least one $j$, you can linearize as follows: \begin{align} x_{ij} &\le y_{ij} \tag1\label1\\ M_i &\ge j y_{ij} + j_\min(1-y_{ij}) \tag2\label2\\ m_i &\le j y_{ij} + j_\max(1-y_{ij}) \tag3\label3 \end{align} Constraint \eqref{1} enforces $x_{ij}>0 \implies y_{ij}=1$. Constraint \eqref{2} enforces $y_{ij}=1 \implies M_i \ge j$. Constraint \eqref{3} enforces $y_{ij}=1 \implies m_i \le j$.

$\endgroup$
2
  • $\begingroup$ Thank you. But how this guarantees that $M_i-m_i+1\leq C_i$, for some given constant $C_i$? $\endgroup$
    – zdm
    Commented Apr 27 at 23:28
  • $\begingroup$ You would also impose that constraint directly. $\endgroup$
    – RobPratt
    Commented Apr 28 at 0:32

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.