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

Question

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):
        print(f"-> Selected at deadline {pulp.value(n)}")

Returns

Optimal
list1 is valid: True
list2 is valid: False
-> Selected at deadline 0.0
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.

Answer 1

Your model basically reads as

$$ \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

Answer 2

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)