I am trying to figure out an algorithm to put as many numbers as possible into a list of different capacity of buckets. It's aimed to solve a problem that a group of runners who run different miles cover as many Ragnar relay legs without skipping a leg.
Thirty-six numbers (legs in miles) below can be repeated many times and can start with any legs in the list.
legs = [3.3, 4.2, 5.2, 3, 2.7, 4,
5.3, 4.5, 3, 5.8, 3.3, 4.9,
3.1, 3.2, 4, 3.5, 4.9, 2.3,
3.2, 4.6, 4.5, 4, 5.3, 5.9,
2.8, 1.9, 2.1, 3, 2.5, 5.6,
1.3, 4.6, 1.5, 1.2, 4.1, 8.1]
A list of runs:
runs = [3.2, 12.3, 5.2, 2.9, 2.9, 5.5]
It becomes an optimization problem that try to put as many numbers to different capacity of buckets if we think legs are list of numbers and runs are buckets.
Given a start leg (1 in this case), find out how many legs can be covered. Below is a sample output starting with leg 1:
Total run mileage = 32.0
Total legs covered = 7 (L1, L2, L3, L4, L5, L6, L7) Total mileage used = 27.7
Total mileage wasted = 4.3
{'Total': 3.2, 'Reminder': 0.2, 'Index': 0, 'L4': 3}
{'Total': 12.3, 'Reminder': 0.8, 'Index': 1, 'L1': 3.3, 'L2': 4.2, 'L6': 4}
{'Total': 5.2, 'Reminder': 0.0, 'Index': 2, 'L3': 5.2}
{'Total': 2.9, 'Reminder': 0.2, 'Index': 3, 'L5': 2.7}
{'Total': 2.9, 'Reminder': 2.9, 'Index': 4}
{'Total': 5.5, 'Reminder': 0.2, 'Index': 5, 'L7': 5.3}
I think this can be written and solved as an explicit optimization problem (to be precise an integer programming model):
Input data:
L[i], r[j] (legs and runs)
Binary variables
assign[i,j] (runner j does leg i)
covered[i] (leg i is covered by a runner)
Model:
max sum(i, covered[i]) (objective)
sum(i,L[i]*assign[i,j]) <= r[j] (runner capacity)
covered[i] <= sum(j,assign[i,j]) (leg is covered)
covered[i] <= covered[i-1] (ordering of legs)
This is not code but the mathematical model. The code will depend on the MIP solver (and modeling tool) that is being used. When solve this model I get:
---- 52 PARAMETER report results
run1 run2 run3 run4 run5 run6
leg1 3.300
leg2 4.200
leg3 5.200
leg4 3.000
leg5 2.700
leg6 4.000
leg7 5.300
total 3.000 11.500 5.200 2.700 5.300
runLen 3.200 12.300 5.200 2.900 2.900 5.500
Note: I basically printed here assign[i,j]*covered[j]*L[i]. The reason is that some variables assign[i,j] may be turned on, while the corresponding covered[j]=0. So just printing assign may be a bit misleading.
A sample implementation using cvxpy can look like:
import cvxpy as cp
legs = [3.3, 4.2, 5.2, 3, 2.7, 4,
5.3, 4.5, 3, 5.8, 3.3, 4.9,
3.1, 3.2, 4, 3.5, 4.9, 2.3,
3.2, 4.6, 4.5, 4, 5.3, 5.9,
2.8, 1.9, 2.1, 3, 2.5, 5.6,
1.3, 4.6, 1.5, 1.2, 4.1, 8.1]
runs = [3.2, 12.3, 5.2, 2.9, 2.9, 5.5]
n = len(legs)
m = len(runs)
assign = cp.Variable((n,m),boolean=True)
covered = cp.Variable(n,boolean=True)
prob = cp.Problem(cp.Maximize(cp.sum(covered)),
[
assign.T@legs <= runs,
covered <= cp.sum(assign,axis=1),
covered[1:n]<=covered[0:(n-1)]
])
prob.solve()
# reporting of solution
L = round(prob.value)
result = assign.value[0:L,]
for i in range(L):
for j in range(m):
result[i,j] *= covered.value[i]*legs[i]
print(result)
I just transcribed the mathematical model here.