I have positive integer variables \(x_k\) and a constraint of the form \(\sum_{t=1}^{x_k}A_t\geq B_k\) for all \(k\) where \(A_t\) and \(B_k\) are nonnegative and given as inputs. Is it possible to linearize such a constraint? asked 08 Jan '18, 17:12 zbir 
If \(x_k \le u_k\), you could introduce binary variables \(y_{kt}\) and constraints \(t\ y_{kt} \le x_k \le (t1)(1y_{kt}) + u_k y_{kt}\) and \(\sum_{t=1}^T A_t y_{kt} \ge B_k\). Check the two cases \(y_{kt} = \{0,1\}\) to see how this works. But that is overkill when all your data are nonnegative. Instead, you can just preprocess to set the lower bound on \(x_k\) so that \(x_k \ge \min\{T: \sum_{t=1}^T A_t \ge B_k\} \). answered 08 Jan '18, 18:15 Rob Pratt 
Assume that the index set of \(A_{t}\) is \(t\in\left\{ 1,\dots,T\right\} \). Create binary variables \(y_{k,t}\) for all \(k\) and \(t\), with the intent that \(y_{k,t}=1\) if and only if \(x_{k}\ge t\). We enforce that with the constraints \[ y_{k,t}\le y_{k,t1}\quad\forall k,\forall t>1 \] and \[ x_{k}=\sum_{t=1}^{T}y_{k,t}\quad\forall k. \] (The first constraint is necessary to ensure that all the 1 values of \(y_{k,\cdot}\) occur at the start of the sequence and are consecutive.) The original constraint can now be written \[ \sum_{t=1}^{T}A_{t}y_{k,t}\ge B_{k}\quad\forall k. \] answered 08 Jan '18, 18:15 Paul Rubin ♦♦ BUT Rob is right about the case where all the \(A_t\) are nonnegative.
(08 Jan '18, 18:19)
Paul Rubin ♦♦
Thank you. What if the summation starts at \(k+1\) and ends at \(k+x_k\) and the RHS involves \(x_k\). Like this \(\sum_{t=k+1}^{k+x_k}A_t\geq B_kx_k\)? I mean do I choose the index set \(\left\{ k+1,\dots,T\right\}\)? Can I apply the same reasoning as you did?
(08 Jan '18, 19:14)
zbir
1
Even in this case, you can just preprocess. Update the lower bound on \(x_k\) to be at least \(\min \{S: \sum_{t=k+1}^{k+S} A_t \ge B_k  S\}\).
(08 Jan '18, 21:27)
Rob Pratt
Thank you Rob. Can you please explain what do you mean by preprocess? Do you mean I have to include the lower bound in the constraints that you provided?
(08 Jan '18, 22:57)
zbir
By preprocess, I mean modify the lower bounds on the \(x_k\) variables instead of introducing new variables or constraints.
(08 Jan '18, 23:02)
Rob Pratt
Very good. Can I still apply preprocessing in the case where \(B_k\) is nonnegative integer variable? The min operation is no longer linear, that's the problem.
(09 Jan '18, 09:32)
zbir
If \(B_k\) is a nonnegative variable (integer or not), the preprocessing does not apply and you should use the additional binary variables and constraints. (You can still update the lower bound on \(x_k\) by using the lower bound on \(B_k\) instead of \(B_k\) in the \(\min\) operation, but that is no longer sufficient to capture your original constraint.)
(09 Jan '18, 10:21)
Rob Pratt
showing 5 of 7
show 2 more comments

Are the \(A_t\) values nonnegative?
I have made a mistake in the original post. See the updates please.