The blood management problem

There are eight types of blood (A, B, AB and O, each coming in + or -), which may be stored until it is six weeks old, at which point it has to be discarded. Some blood types may be substituted for others (as shown in the diagrom). For example, O- blood may be used for anyone, while B+ blood may be used only with patients with B+ blood or AB+ blood.

Each week, new donations are made, and new demands for blood arise. The problem is to determine which blood type to use for each demand type in a given week. Do you use the O- blood now, or hold it for later when it might be used for a patient with A- blood, which can only use A- blood or O- blood?

If we model time in weeks, blood may be 0, 1, 2, ..., 5 weeks old, creating six "ages." Combined with the eight blood types, this means we have 48 "blood types" for supply, and eight blood types for demand. The "state" of our system is the vector of supplies and demands, which means a 56-dimensional vector. There are 27 possible assignments of blood types to demand types (the number of links in the figure). When we include age, we have 8 x 27 = 216 links, which means a decision variable with 216 dimensions. Finally, there are eight types of random supplies (new blood) and eight types of random demand, giving us an information variable with 16 dimensions.

This problem is a nice illustration of the "three curses of dimensionality." This project was the topic of two undergraduate research projects at Princeton University. Lindsey Cant '06 wrote her undergraduate senior thesis on the topic. Her thesis provides a very nice summary of the problem area along with a mathematical model, which is available here. Another student, Vincent Yu '07, built on Lindsey's work, producing a Matlab version of the code that was designed so others can use it. Vincent's writeup, code and datasets can be downloaded from here. Vincent's code illustrates the model and algorithm described in chapter 12, section 12.2 (Blood management). I cannot guarantee that this is the best solution, but it illustrates the use of ADP in the context of a multistage linear program.