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's gravatar image

accept rate: 0%

edited 08 Jan '18, 18:04

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

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%20Pratt's gravatar image

Rob Pratt
accept rate: 28%

edited 08 Jan '18, 18:22

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%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

edited 08 Jan '18, 18:17

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

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
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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



Asked: 08 Jan '18, 17:12

Seen: 285 times

Last updated: 09 Jan '18, 10:27

OR-Exchange! Your site for questions, answers, and announcements about operations research.