Algorithm for optimal packing with known inventory

Question

Hospitals are changing the way they sterilize their equipment. Previously the local surgeons kept all their own equipment and made their own surgery trays. Now they have to confine to a country wide standard. They want to know how many of the new trays they can make from their existing stock, and how much new equipment they need to buy.

The inventory of medical equipment looks like this:

http://pastebin.com/rstWSurU

each hospitals has codes for various medical equipment and then a number for how many they have of the corresponding item

3 surgery trays with their corresponding items are show in this dictionary.

http://pastebin.com/bUAZhanK

There are a total of 144 different operation trays

the hospitals will be told they need 25 of tray x, 30 of tray y, etc...

They would like to maximize the amounts of trays they can finish with their current stock. They would also like to know what equipment they need to purchase in order to finish the remaining trays.

I have thought about two possible solutions one being representing the problem as a linear programming problem. The other solving the problem by doing a round-robin brute force solve of the first 90% of the problem and solving the remaining 10% by doing a randomized algorithm several times and then pick the best solve of those tries.

I would love to hear if anyone knows a smart way of how to tackle this problem!

Answer 1

If I understand this correctly we can optimize for each hospital separately. My guess is that the following would be a good start for an MIP (Mixed Integer Programming) model:

I use the following indices: i is items and t is trays. x(t,i) indicates how many items we assign to each tray type. y(t) counts the number of trays of each type that we can compose using the available items. From the solution we can calculate the shortages that we need to order.

Of course we are just maximizing the number of trays we can make. There is no consideration of balancing (many trays of one type and few or zero of another). I mitigate a little bit by not allowing to create more trays than required (if we have more items they need to go to other types of trays). This requirement is formulated as an upper bound on y(t).

For large problems we can restrict the (t,i) combinations to the ones that are possible. This will make the model smaller. When using precise math notation:

A further optimization would be to substitute out the variables x(t,i).

Adding shipping surplus items to other hospitals would make the model more difficult. In that case we could end up with a model that needs to look at all hospitals simultaneously. May be an interesting case for some decomposition approach.