2
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – prubin
    Apr 12, 2022 at 20:33
  • 2
    $\begingroup$ 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$. $\endgroup$
    – prubin
    Apr 12, 2022 at 20:37
  • $\begingroup$ 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! $\endgroup$
    – birnbaum
    Apr 12, 2022 at 20:42

2 Answers 2

7
$\begingroup$

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
$\endgroup$
4
  • 1
    $\begingroup$ 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! $\endgroup$
    – birnbaum
    Apr 13, 2022 at 10:10
  • $\begingroup$ 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? $\endgroup$
    – birnbaum
    Apr 13, 2022 at 12:25
  • $\begingroup$ @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$? $\endgroup$
    – joni
    Apr 13, 2022 at 15:40
  • $\begingroup$ yes, thanks a lot, now I got it! $\endgroup$
    – birnbaum
    Apr 13, 2022 at 16:05
3
$\begingroup$

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:

enter image description here

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)

$\endgroup$
2
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Kuifje
    Apr 13, 2022 at 11:04
  • $\begingroup$ @Kuifje, thanks. I will check it and update the answer. I didn't see that. $\endgroup$
    – A.Omidi
    Apr 13, 2022 at 12:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.