Management of�Blood Component Preparation

Speaker: Chun-Cheng Lin

National Taiwan University

​

Co-authors: Chang-Sung Yu, Yin-Yih Chang

Outline

• Introduction to

the blood component preparation problem (BCPP)

​

• A linear time algorithm for the BCPP

​

• Some variants of the BCPP

​

• Conclusion and future work

2

Introduction

• Transfusion therapy
• to transfuse the specific blood components

needed to replace particular deficits

for some medical purposes.

​

• Whole blood
• contain all blood elements
• a source for blood component production.

​

• Blood component preparation
• the indication for the use of unfractionated whole blood

⇒ almost does not exist now

• separating specific cell components from the whole blood
• a lot of different methods (processes) or equipment

⇒ different use, efficiency and quality

3

A Process of Separating Blood Components

• Implied value (a_i): Consider both the revenue contributed by patients or insurance and the costs induced by blood of collection, testing, preparation, preservation, storage, processing time, etc.
• Demand limit (d_i).

4

Packed Red Blood Cells

Platelet-Rich Plasma

Washed Red Blood Cells

Fresh Frozen Plasma

Platelet Concentrate

Fresh Plasma

Frozen Plasma

Cryoprecipitate

soft-spin centrifugation

hard-spin centrifugation

washing

Whole Blood

freezing

thawing; centrifugation; freezing

Blood Component Preparation Problem

• Blood Component tree
• vertex v_i = a blood component

with value a_i and demand limit d_i

• the amount x_i of v_i is derived from

the amount of its parent

according to a given ratio r_i;

​

• Initial assignment of { x_i }
• x₁ = Q; other x_i = 0

​

• The Blood Component Preparation Problem (BCPP)

Given an initial volume Q of the whole blood and

an n-vertex blood component tee T

(where demand limit d_i ; implied value a_i),

determine the assignments of { x_i }

so that (1) the total value is maximized

(2) while the demand limit of each component is satisfied

5

A linear programming approach

• The BCPP problem can be solved by linear programming.

​

​

​

​

​

​

6

Comment:

There exist a lot of software tools for the linear programming problem, users just need to describe the BCPP as a linear program and then use those tools to solve it without implement it.

Example

7

Q = 100

Motivations

• Linear programming (LP) problem

​

​

​

​

​

​

​

​

• 2 drawbacks to solve the BCPP by LP:
• The worst-case algorithm for the LP problem may not be executed efficiently (its time complexity is nonlinear)
• It may not be convenient for users to directly describe the constraints of the LP for a general derivatives tree.

8

Main result

• Main Theorem: There exists a linear time algorithm for the BCPP in the size of vertices.

​

• Characteristic value ϕ (v_i) of v_i
• Compute the following formula in the bottom-up fashion

​

​

​

​

• e.g.,
• ϕ (v₈) = 2; ϕ (v₉) = 6
• ϕ (v₆) = max( 3, 0.7×2 + 0.3×6 ) = 3.2

​

9

Our linear time algorithm (1/4)

• Step 1: ∀ vertex v_i in top-down fashion of T,
• x_i is assigned d_i, and then the remaining amount is forwarded to the next level;
• if not enough to satisfy any demand limit, then return false.
• for convenience, we express that x_i = d_i + y_i.

​

10

0.8

0.2

10+0

3

10

4+0

4

4

5+0

8

5

12+1.6

2

12

7+13.4

1

7

8+0

3

8

9+4

1

9

13+5.2

2

13

6+1.8

6

6

0.7

0.3

0.2

0.5

0.3

1

x₁

x₂

x₃

x₇

x₄

x₅

x₆

x₈

x₉

Our linear time algorithm (2/4)

• Step 2: ∀ vertex v_i in bottom-up fashion of T,
• If v_i is a leaf, then y_i^M = y_i;

o.w., y_i^M = min_{vj∈Child(vi)}{ y_j^M / r_j },

y_i^m = y_j – r_j y_i^M for each v_j ∈ Child(v_i).

• (In fact, y_i^M is the maximal possible amount of v_i flowed from its descendents and y_i^m is the amount of every descendent of v_j of v_i after y_i^M is achieved)

​

11

y₁^m

10

0

8

0

4

2

1.6

0

13.4

11

6

2

4

0

5.2

1

1.8

0

y₁^M

y₂^m

y₂^M

y₃^m

y₃^M

y₇^m

y₇^M

y₆^m

y₆^M

y₄^m

y₄^M

y₈^m

y₈^M

y₉^m

y₉^M

Our linear time algorithm (3/4)

• Step 3:
• Initially, all the leaves of T are marked.
• For each internal vertex v_i in the bottom-up fashion of T, compute ϕ (v_i). If ϕ (v_i) = a_i, then vertex v_i is marked.

​

​

​

12

v₄, v₅, v₇, v₈, v₉ are leaves, and hence, marked.

ϕ (v₆) = max(3, 0.7×2+0.3×6) = 3.2 > 3 = a₆

⇒ v₆ is unmarked.

ϕ (v₃) = max(8, 1×1) = 8 = a₃

⇒ v₃ is marked.

ϕ (v₂) = max(4, 0.2×2+0.3×1+0.5×3.2) = 4 = a₂

⇒ v₂ is marked.

ϕ (v₁) = max(3, 0.8×4+0.2×8) = 4.8 > 3 = a₁

⇒ v₁ is unmarked.

y₁^m

10

0

8

0

4

2

1.6

0

13.4

11

6

2

4

0

5.2

1

1.8

0

y₁^M

y₂^m

y₂^M

y₃^m

y₃^M

y₇^m

y₇^M

y₆^m

y₆^M

y₄^m

y₄^M

y₈^m

y₈^M

y₉^M

y₉^M

Our linear time algorithm (4/4)

• Step 4: Let U = V. ∀ v_i ∈ U in top-down fashion of T, if v_i is unmarked then output x_i = d_i + 0; otherwise, do the following:
• Output x_i = d_i + y_i^M;
• ∀ v_j in the top-down fashion of the subtree T_vi rooted at v_i, if v_j is marked, then output x_j = d_j + y_j^m; otherwise, for evry children v_k of v_j, y_k^m ← y_k^m + r_k y_j^m, and then output x_j = d_j + 0 (i.e., y_j^m = 0);
• U ← U \ V(T_vi)

13

0.3

0.8

0.2

10+0

3

10

4+0

4

4

5+0

8

5

12+1.6

2

12

7+13.4

1

7

8+0

3

8

9+4

1

9

13+5.2

2

13

6+1.8

6

6

0.7

0.3

0.2

0.5

1

y₁^m

10

0

8

0

4

2

1.6

0

13.4

11

6

2

4

0

5.2

1

1.8

0

y₁^M

y₂^m

y₂^M

y₃^m

y₃^M

y₇^m

y₇^M

y₆^m

y₆^m

y₄^m

y₄^M

y₈^m

y₈^M

y₉^m

y₉^M

0

2.4

0.6

Observations of our outputs

• Observation 1.

​

​

​

​

​

​

​

​

• Observation 2. In the output of our algorithm,
• For every vertex v_i in R₁, a_i < ϕ (v_i).
• For every vertex v_i in R₂, a_i = ϕ (v_i).

​

• Observation 3. Any feasible solution of the BCPP is reachable from the output of our algorithm.

14

on the band

above the band

below the band

R₂

R₃

R₁

Output of Step 1 of our algorithm

Output of our algorithm

Comparison of solutions

15

on the band

above the band

below the band

R₂

R₃

R₁

band

…

…

R₁₁

R₁₂

R₁₃

R₂

R₃

R₁

Any feasible solution

Output of Step 1 of our algorithm

Output of our algorithm

Blood Component Preparation Problem

• Theorem. The BCPP can be solved in O(n) time.

Proof. Skipped.

​

• Extension: How to choose multiple standardized processes so that the total value is maximized?
• The preparation and preservation of blood components are considered within a time frame.

In practice, we may execute more than one process simultaneously within a certain time frame.

• Fortunately, for the standardization of executing processes, the number of alternative processes is fixed constant.
• The extended problem can be solved roughly in polynomial time.

16

Modified Blood Component Preparation Problem

• The deriving operation may be nonreversible.

⇒ require: the volume of the components at higher levels is more.

​

• The Modified Blood Component Preparation Problem (BCPP’)

Given the initial volume Q of the whole blood and

an n-vertex blood component tree T

(every vertex has its demand limit),

determine the assignments of { x_i }

so that (1) the volume of the components at higher levels

is remained as more as possible

(2) while the demand limit of every component is satisfied.

​

• Algorithm:

Steps 1 and 2 are the same as those of the previous.

Step 3: Output x₁ = d₁ + y₁^M ; x_i = d_i + y_i^m, ∀ v_i ∈ V \ {v₁}.

​

• Corollary. The BCPP’ can be solved in O(n) time.

17

Conclusion and future work

• We have defined a new problem called the blood component preparation problem (BCPP), and proposed not only a linear programming solution but also a linear time algorithm for the BCPP.

​

• Some variants are also given in this work.

​

• A line of future work includes:
• to investigate the tractability of the `derivatives graph problem’ on some special cases of graphs;
• to take more factors (e.g., time and inventory) into account in the BCPP;
• to evaluate the effectiveness of the BCPP applied in practical environment;
• to investigate the sensitivity analysis and the critical paths of the BCPP.

18

Thank you for your attention!

19