Posted on April 9, 2019
A new uniform is coming to the Air Force: the OCP (Operational Camouflage Pattern) is replacing the ABU (Airmen Battle Uniform). Despite the long-term simplicity and cost savings that stem from the Air Force and Army sharing a common uniform, a number of short-term challenges arise.
As part of the ABU's retirement, the 145 Air Force ROTC detachments across the country are being asked to trade uniform items among themselves in lieu of making new purchases, an admirable cost-saving, waste-reducing goal. So, for example, if Det 002 has three extra 'Mens 38L ABU Blouse', and Det 075 needs three of them, Det 002 could ship those three blouses to Det 075. If there were just a few items or few detachments, this exercise would be trivial. However, many detachments need hundreds of uniform items 400+ distinct uniform item types spread among the 145 detachments. The complexity grows quickly.
Given a set number of total swaps (shipments), maximize the number of transferred items (uniforms) between nodes (detachments)
A (notional) detachment may need as many 100 items from (say) 30 item types, maybe only 90 of which can be provided by other dets, and it may required shipments from (say) 7 of those detachments. If this were the case, then hundreds of shipments need to be coordinated on dynamically changing information (every shipment changes a detachment's needs and current inventory). Once you factor in the time associated with contacting other detachments, and possible second order effects like detachments underreporting overages to save effort in a brutally time-consuming process, and you are left with a exorbitantly inefficient plan doomed for failure. Greedy matching algorithms to the rescue!
Incomplete/inaccurate information: to tackle this, matches must either update a central database OR (much more simply), all matches must be made simultaneously using the same information. We will proceed with the latter route. To keep it simple for the user (individual detachments), they just need to fill out a highly specific spreadsheet and submit to a central planner.
Time and resource constraints: the central planner will then consolidate the data and algorithmically determine matches, then tell detachments what to send and where. This reduces the need for decentralized contact, a murky expansion of the quadratically scaling handshake problem.
Lack of detachment involvement: nothing is guaranteed to fix this without a mandate much higher than what this lowly ROTC instructor carries. The best one can do is feverishly sell the idea whilst staying out of trouble with superiors for "going rogue" with crazy outside-the-box ideas far above his pay grade.
We want to optimize the situation, but optimize what exactly? There are many paths here, but the best problem statement is: "given a set number of total swaps (shipments), maximize the number of transferred items (uniforms) between nodes (detachments)". This lends itself to a solution to the big picture problem, minimizing additional purchases and saving money. From there, the user can refine goals by changing the number of shipments with various inputs to analyze when diminishing returns set in.
The data structures are pretty simple:
| Det 002 | Det 055 | Det 075 | Det 890 | |
|---|---|---|---|---|
| Det 002 | 0 | 17 | 0 | 4 |
| Det 055 | 10 | 0 | 5 | 2 |
| Det 075 | 2 | 3 | 0 | 28 |
| Det 890 | 3 | 45 | 1 | 0 |
In this example table, the 45 represents the number of uniform items the giving detachment (Det 890) can send to the receiving detachment (Det 055).
The user will set extra criteria such as a limit to the number of total shipments, then follow the following algorithm:
In the above table, the first transfer selected would be Det 890 sending Det 055 the 45 items that Det 890 has as excess that Det 055 needs.
Note, updating the "Give and Take" array only requires modifying the row and column associated with the selected giver and taker. Implementing this would reduce runtime by a linear factor.
First, some book-keeping. We will use a simple class for detachments. No there's no methods attached to it yet, but this project is in its infancy so let's leave our options open.
class Detachment:
def __init__(self, i):
self.number=i
self.inventory = None
Next, some basic variables, reading in the 'titles' (product descriptions), and reading in detachment inventory information.
det_nums=[1,2,3,4]
dets = []
num_dets = len(det_nums)
number_of_shipments = num_dets * 1
# Generate titles
file_name = 'det%03d.csv' % det_nums[0]
titles = read_titles(file_name)
# Read det info
for i in det_nums:
file_name = 'det%03d.csv' % i
inventory = read_csv(file_name)
det = Detachment(i)
det.inventory = inventory
dets.append(det)
The functions for 'read_titles' and 'read_csv' are pretty vanilla, so I'll leave those out (but they will be available in the full code).
We also need an array to hold the giver and taker. We generate this table with the following code:
def gen_give_take(dets):
num_items = len(dets[0].inventory)
num_dets = len(dets)
give_take = [0 for _ in range(num_dets ** 2)]
for g in range(len(dets)):
for t in range(len(dets)):
c=[]
for i in range(num_items):
if dets[g].inventory[i] <= 0 or dets[t].inventory[i] >= 0:
c.append(0)
else:
c.append(min(dets[g].inventory[i], -dets[t].inventory[i]))
give_take[g*num_dets+t] = sum(c)
return give_take
The algorithm listed above is implemented below.
for _ in range(number_of_shipments):
# Step 2: Initialize give_take array
give_take = gen_give_take(dets) #TODO replace with an update function to save time
# Step 3: Find max value in give_take array
index = give_take.index(max(give_take))
taker = index % num_dets
giver = index // num_dets
# Steps 4-6: Make the order and update inventory
num_transferred_list=[] #order
current_order=[]
for i in range(num_items):
if dets[giver].inventory[i] <= 0 or dets[taker].inventory[i] >= 0:
num_transferred_list.append(0)
else:
num_transferred = min(dets[giver].inventory[i], -dets[taker].inventory[i])
num_transferred_list.append(num_transferred)
dets[giver].inventory[i] -= num_transferred
dets[taker].inventory[i] += num_transferred
current_order.append([titles[i], num_transferred])
This is an exercise left to the reader. I wrote up a proof, but it's too lengthy to fit in the margins of this text.