I am writing a program to solve a combinatorial optimization problem. I have been working on an algorithm that gets the desired results, but I am having difficulties getting the algorithm to perform well.
The problem domain is the medical equipment supply industry, and the basic requirement is to assign items to packages so that the rental charge is minimized. Equipment can be rented individually, but there are also packages defined containing a combination of equipments, and the rental charge of the packages is less than the total rental charge of the individual equipments. While generating the bill, I need to assign the items to packages wherever possible in such a way that the total rental charge is minimized.
In my model, packages are defined as follows
- Each package can contains 1..N Groups G1, G2, G3,.. GN.
- Each Group must have at least X items (where X >= 0), and at most Y items ( Y > 0, Y >= X)
- Each Group can contain 1..n Item Types IT1, IT2, ... ITn
- Each Item Type must be included at least A times (A >= 0) in the group, and at most B times (B > 0, B >= A)
An example of a packages could be as follows;
Bed and Wheelchair package Group: Bed (total item min 1, max 1) Bed 6 feet (min 0, max 1) Bed 6.5 feet (min 0, max 1) Group: Wheelchair (total item min 1, max 1) Manual wheelchair (min 0, max 1) Motorized wheelchair (min 0, max 1) Group: Accessories (min 0, max 3) Air Mattress (min 0, max 1) Air blower (min 0, max 1) Pillows (min 0, max 2)
There would be multiple packages available similar to the above. One particular Item Type can appear only once in a package. However, different packages can have the same Item Type.
Assumptions / Requirements:
- Each package has a rental charge associated with it, as does each Item Type.
- When renting a package, only the package price is charged, not the items inside the package. A rental can consist of both packages and individual items.
- When renting out X number of items of different types, the items should be assigned to packages where possible, so that the total rental is minimized.
- There can be multiple ways of forming the packages, and the ones with the lowest rental should be selected.
- There can be multiple combinations that produce the lowest rental. All of them are required in the result. (I may be able to work around this requirement if absolutely needed).
- I need to support rental of up to 25 items. The number of available packages can vary from 10 to 20.
- An additional complexity that I will need to add later is to support the concept of packages contained inside packages.
- I need to run this for multiple rental bills in a batch mode, which makes the performance of the algorithm so critical.
My approach so far:
- For each item, find a list of the packages that it can belong to based on the item type.
- Create a graph where each node is a item-package assignment. Arrange the graph so that the nodes at each leaf level represent the possible package assignments for a single item.
- Do a depth first traversal of the graph, pruning the subtree and backtracking when it is obvious that the subtree cannot result in an optimal solution. I am pruning the subtree when either of the following is false:
- When the remaining items are included, can it satisfy the minimum quantities required for each package in the branch so far ?
- Is the total price of the packages included so far less than the total of the individual price of all the line items ?
The approach is ending up with an expensive calculation. In one test with 24 items and a small number of packages, it traversed 2.5 million nodes and took more than a minute for the results to come back. Ideally, I would like the results to be returned in seconds.
I will very much appreciate any pointers to an efficient algorithm that can be used for this problem.
EDIT: I am adding an example of a bill and package.
Bed and Accessories package Group: Bed (total item min 1, max 1) Bed (B) (min 1, max 1) Group: Accessories (total item min 0, max 2) Mattress (M) (min 0, max 1) Pillows (P) (min 1, max 2)
Total quantities in bill: B: 2, M: 3, P: 5
The packages can be formed in different ways:
2 packages, remaining items billed individually (1B, 1M, 1P), (1B, 2P) (1B, 2P), (1B, 2P) (1B), (1B) etc 1 package, remaining items billed individually (1B, 1P), (1B, 2P), (1B, 1M, 1P), (1B), etc
With IP, the function to be minimized can be defined as
aD + bB + cM + dP where D is the quantity of discount package B, M and P are the quantities of the items not billed as packages, and a, b, c, d are the rental costs for each.
Some of the constraints:
B <= 2 M <= 3 P <= 5 D + B = 2
However, for the Accessories group, it is getting complex. I cannot have
D + M = 3,
as D can be formed without any mattress, like the [(1B, 2P), (1B, 2P)] combination. In this combination, D = 2, and M = 3, since all the Ms are being billed individually, and there are 2 discount packages. I was thinking of introducing some additional variables to represent what quantities are picked for each group, but I think that will result in a quadratic constraint.