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}

CodePudding user response：

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.