# Find the list with the fewest elements whose cumulative sum reaches threshold

I have a question with which I am stuck and would be very grateful for help:

• I have multiple lists of non-negative numerical values (all of the same length)
• I want to find the list with the lowest n, where the cumulative sum of the first n elements is larger or equal than a fixed threshold.

So in the example below with threshold = 10, I expect the solver to select "list2" at n = 3, because 1+1+8 == 10. My current implementation in PuLP looks like this:

import pulp

threshold = 10
lists = {
"list1": [2,4,0,0,2],
"list2": [1,1,8,2,3],
"list3": [0,5,0,2,1],
}

n = pulp.LpVariable("list_index", 0, 4, pulp.LpInteger)
lists_selected = pulp.LpVariable.dicts("is_selected", lists, cat=pulp.LpBinary)

prob = pulp.LpProblem("myProblem", pulp.LpMinimize)
prob += (n, "minimize list_index")
prob += (pulp.lpSum(lists_selected) == 1, "there can only be one selected list")
for list_name, list_is_selected in lists_selected.items():
prob += (pulp.lpSum([a for i, a in enumerate(lists[list_name]) if i <= n]) >= list_is_selected * threshold,
f"if {list_name} is selected, its cumulative sum has to reach the threshold {threshold}")

status = prob.solve()

# Manual check to see if the solution is valid
print(pulp.LpStatus[status])
for list_name, list_is_selected in lists_selected.items():
is_valid = (sum([a for i, a in enumerate(lists[list_name]) if i <= pulp.value(n)]) >= pulp.value(list_is_selected) * threshold)
print(f"{list_name} constraint is valid: {is_valid}")
if pulp.value(list_is_selected):


Returns

Optimal
list1 is valid: True
list2 is valid: False
list3 is valid: True


So from my point of view, the solver sets list_index to its minimum 0, which violates the threshold constraint of the selected list2. I'm not sure if I am lacking understanding on integer programming or if this is a PuLP-specific problem.

• Unless you have a specific syntax question about PuLP, I think you would be better off writing your model in mathematical notation. The site lets you enter math using MathJax.
– prubin
Commented Apr 12, 2022 at 20:33
• If the lists of numbers are input data, why do you need an integer program? You can just do partial sums of each list in a loop and grab the list with smallest $n$.
– prubin
Commented Apr 12, 2022 at 20:37
• Thanks for your comments! You are right, but my problem is a little bit more complicated than this and I wanted to add constraints incrementally. I'll give it a try in MathJax! Commented Apr 12, 2022 at 20:42

\begin{align*} \min \quad n \quad \text{s.t.} \quad \sum_{k = 0}^{n} l_{i,k} \geq b_i \cdot \epsilon, \quad \sum_{i \in L} b_i = 1, \end{align*}

where $$l_{i,k}$$ is the k-th element of the i-th list and $$b_i$$ is a binary variable that equals one iff the $$i$$-th list is selected. The problem is that $$n$$ is a variable as well and you can't use PuLP variables inside logical python expressions like if. Therefore, your second constraint is not valid due to the if I <= n inside the sum.

Instead, you can define a binary variable $$b_{i,k}$$ that equals 1 iff list $$i$$ is selected and we sum up until the $$k$$-th element. Then, our model looks like this

$$\min \sum_{i \in L} \sum_{k = 0}^{m_i} k \cdot b_{i,k}$$

subject to

\begin{align} \sum_{k = 0}^{r} l_{i,k} &\geq b_{i,r} \cdot \epsilon \quad \forall i \in L, r \in \{0, \ldots, m_i\}, \\ \sum_{i \in L} \sum_{k = 0}^{m_i} b_{i,k} &= 1. % \end{align}

Here, $$L$$ denotes the set of lists and $$m_i$$ the number of elements in the $$i$$-th list. In code (note that I prefer the .addConstraint() and .setObjective() methods over the overloaded += operator):

import pulp

threshold = 10
lists = {
"list1": [2,4,0,0,2],
"list2": [1,1,8,2,3],
"list3": [0,5,0,2,1],
}

prob = pulp.LpProblem("myProblem", pulp.LpMinimize)

# Lists
L = lists.keys()

# Variables
b = {}
for l in L:
for k in range(len(lists[l])):
b[l, k] = pulp.LpVariable(f"b[{l}, {k}]", cat=pulp.LpBinary)

# Objective
prob.setObjective(sum(k * b[l, k] for l in L for k in range(len(lists[l]))))

# Constraints
for l in L:
for r in range(len(lists[l])):
prob.addConstraint(sum(lists[l][k] for k in range(r)) >= b[l, r]*threshold)

prob.addConstraint(sum(b[l, k] for l in L for k in range(len(lists[l]))) == 1)

# solve the problem
status = prob.solve()

# print the solution
print(pulp.LpStatus[status])
for (l, k) in b:
print(f"b[{l}, {k}] = {b[l, k].varValue}")


This yields:

Optimal
b[list1, 0] = 0.0
b[list1, 1] = 0.0
b[list1, 2] = 0.0
b[list1, 3] = 0.0
b[list1, 4] = 0.0
b[list2, 0] = 0.0
b[list2, 1] = 0.0
b[list2, 2] = 0.0
b[list2, 3] = 1.0
b[list2, 4] = 0.0
b[list3, 0] = 0.0
b[list3, 1] = 0.0
b[list3, 2] = 0.0
b[list3, 3] = 0.0
b[list3, 4] = 0.0

• Amazing, thank you so much! Also thanks for explaining why my solution in PuLP was invalid and for helping me formulate the problem in mathematical notation, I learned a lot! Commented Apr 13, 2022 at 10:10
• I have one additional question: As k is the index we are trying to minimize, in the first constraint, shouldn't we sum from r=0 until k and not the other way round? Commented Apr 13, 2022 at 12:25
• @birnbaum Sorry, there was a tiny typo in the first constraint, i.e. $b_{i,k}$ instead of $b_{i,r}$ on the right hand side. Is it now clear why we sum from $k=0$ to $k=r$?
– joni
Commented Apr 13, 2022 at 15:40
• yes, thanks a lot, now I got it! Commented Apr 13, 2022 at 16:05

I think the appropriate way to do this is what was proposed by Prof. Rubin, but if you want to use a mathematical approach, the following formulation would be helpful.

$$\begin{eqnarray} \text{Max/Min} & \text{Constant}\\ \text{subject to} \\ &\sum_{j\in \mathcal{J}} w_{ij}x_{ij} \leq Threshold \quad \text{for} \quad i \in \mathcal{I}:ok_{i}\notag \\ &\sum_{j\in \mathcal{J}} x_{ij} \geq 1 \quad \text{for} \quad i\in \mathcal{I}:ok_{i}\notag \\ \text{where,} \qquad & x_{ij} = \{0,1\} \quad \text{for} \quad i,j \in \mathcal{I},\mathcal{J} \notag \end{eqnarray}$$

The variable $$x_{ij}$$ indicates that if element $$j \in \mathcal{J}$$ in the list $$i \in \mathcal{I}$$ is allocated, $$1$$, otherwise $$0$$ and $$w_{ij}$$ is the lists you defined. Please be aware that, if you want to select items in each list based on a pre-defined threshold, you should be sure that the cumulative sum of the items can be achieved. According to this, a checker set $$ok_{i}$$ is defined. By the above formulation and using solution pool technology the results are:

For achieving the first $$n$$ items, as Kuifje mentioned, by adding the following constraint:

$$\begin{eqnarray} &\sum_{j\in \mathcal{J}} x_{ij} \leq \sum_{j\in \mathcal{J}} x_{ij-1}\quad \text{for} \quad i \in \mathcal{I}:ok_{i}\notag \\ \end{eqnarray}$$

The solution is: (i2: j1, j2, j3, j4)

• I think that you need an extra constraint to enforce consecutive $1s$ in the solution, as OP states "the cumulative sum of the first $n$ elements" : $x_{i,j}\le x_{i,j-1}$ for all list $i$. Commented Apr 13, 2022 at 11:04
• @Kuifje, thanks. I will check it and update the answer. I didn't see that. Commented Apr 13, 2022 at 12:55