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\}$
$\begingroup$
$\endgroup$
2
-
$\begingroup$ How are $M_i$ and $m_i$ defined if $x_{ij}=0$ for all $j$? $\endgroup$– RobPrattCommented 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$– zdmCommented Apr 27 at 23:28
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$.