# How to linearize a constraint with variable summation?

 0 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 17●1●4 accept rate: 0% Are the $$A_t$$ values nonnegative? (08 Jan '18, 17:59) Rob Pratt I have made a mistake in the original post. See the updates please. (08 Jan '18, 18:05) zbir

 1 If $$x_k \le u_k$$, you could introduce binary variables $$y_{kt}$$ and constraints $$t\ y_{kt} \le x_k \le (t-1)(1-y_{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 1.2k●2●6 accept rate: 28%
 1 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,t-1}\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 ♦♦ 14.6k●4●12 accept rate: 19% 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_k-x_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 non-negative 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
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: