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 firstn
elements is larger or equal than a fixedthreshold
.
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.