(607d) Heuristic Approximations to Multistage Stochastic Problems With Endogenous Uncertainty

        The clinical trials are one of main sources of costs for drug
development process. Proper clinical trial planning is needed to maximize
R&D productivity. The clinical trial planning problem can be viewed as a
specific illustration of the R&D pipeline management problem.  The characteristics
of the R&D pipeline management problem are several new-product-development
projects, different levels of resources necessary to complete each project,
limited amounts of available resources, and returns once the products reach the
market. Generally, the development of new products involves a stage-gate
process: if a product fails to successfully complete a stage, the product does
not continue through the subsequent stages, and the resources that were
originally assigned to that product become available. When the product fails to
complete a stage the return of that product is not realized. The decisions are
to select which projects to pursue, and the best way to assign the resources to
the chosen projects to maximize the returns¹.

         In general, the necessary resources, the returns, and which
products will make it to the market successfully are not known with certainty
at the time the decisions are made. The uncertainties are resolved slowly as
the decisions are executed requiring recourse action ². These
optimization problems belong to a special class of mathematical programs called
stochastic programs (SPs) under endogenous uncertainty. The literature on
problems with endogenous uncertainty is limited and can be grouped based on the
whether the resolution of uncertainty or the distribution parameters of
uncertainty are impacted by the decisions. The scope of this abstract is limited
to the SPs in which the resolution of uncertainty is decision dependent.

                Jonsbraten
et al. ³ is one of
the first to study this problem for MILPs. The authors developed a
branch-and-bound algorithm coupled with an implicit enumeration method to
generate the scenario trees. Investment and operational planning of gas field
developments, in which the revelation of uncertainty in gas reserves depends on
the investment decisions, was studied by Goel and Grossman ⁴. The
authors formulate the problem as a multi-stage stochastic MILP, and proposed an
approximation algorithm based on decomposition and search space restriction to
solve it. A Lagrangean duality based branch-and-bound algorithm, which is
guaranteed to give the optimal solution, was proposed to solve a similar
formulation^5,6. Mercier and van Hentenryck developed
?Anytime Multi-Step Anticipatory Algorithm? (Amsaa) to solve stochastic
optimization problems with both exogenous and endogenous uncertainty. The
algorithm uses the sampling average approximation method to approximate the
problem as a Markov Decision Process (MDP), heuristic search algorithm to solve
the MDP, and stochastic combinatorial optimization solvers to compute good
upper bounds for the heuristic search algorithm. Colvin and Maravelias ^2,7,8 incorporated the decision dependent revelation of
uncertainty in clinical trial outcomes explicitly in their SP formulations. Rigorous
SP approaches become computationally intractable with the size of the portfolio
and source of uncertainties, because the scenario and decision trees grow
exponentially. To date, the largest R&D pipeline management problem solved
included seven products ² only
considering the uncertainty in the outcome of the clinical trials. The
computational costs associated with the R&D pipeline management problem
where the only uncertainty in the outcome of clinical trials is considered
stems from the exponential growth of non-anticipativity constraints.

This talk
presents two heuristic approximations to solve the pharmaceutical R&D
pipeline planning problem under endogenous uncertainty. The uncertainty
addressed in the pharmaceutical R&D pipeline is associated with the outcome
of the clinical trials. The developed heuristic approximations decompose the
rigorous SP formulation using two different approaches. In the first approach, the
multi-stage stochastic problem is decomposed into a series of two stage
stochastic problems (Figure 1). The second approach decomposes the problem into
a series of knapsack problems. In this formulation, at each stage items are
created for possible product-stage combinations. The value of each item is
estimated as the expected revenue of a product with successful completion of
the pipeline using the likelihood that the product will reach the market given
the product's current status in the pipeline. The knapsack is solved each time
a realization occurs eliminating items that become infeasible. Given the
computational resources required to solve the rigorous SP formulation, both
approaches are highly parallelizable.

The performances
of the two decomposition approaches are compared to the rigorous stochastic
program solution for two case studies.  The first comparison looks at a two
product case where two stages of development are analyzed. In this case, both
the two-stage decomposition approach and the knapsack approach yield objective
values within one percent of the rigorous formulation. The second case examined
a three product, three stage case. The objective values obtained from the
decomposition approaches yielded values within three percent of the rigorous
formulation.

Figure 1- The two-stage
decomposition approach

1.            Subramanian D, Pekny JF, Reklaitis GV. A
Simulation-Optimization Framework for Research and Development Pipeline
Management. AIChE Journal. October 2001 2001;47(10):2226-2242.

2.            Colvin M, Maravelias CT. Modeling
methods and a branch and cut algorithm for pharmaceutical clinical trial
planning using stochastic programming. European Journal of Operational
Research. 2010;203(1):205-215.

3.            Jonsbråten T, Wets R, Woodruff D. A
class of stochastic programs withdecision dependent random elements. Annals
of Operations Research. 1998;82(0):83-106.

4.            Goel V, Grossmann IE. A stochastic
programming approach to planning of offshore gas field developments under
uncertainty in reserves. Computers & Chemical Engineering. 2004;28(8):1409-1429.

5.            Goel V, Grossmann IE. A Lagrangean
duality based branch and bound for solving linear stochastic programs with
decision dependent uncertainty. In: Puigjaner L, Espuna A, eds. European
Symposium on Computer-Aided Process Engineering-15, 20A and 20B. Vol
20a-20b. Amsterdam: Elsevier Science Bv; 2005:55-60.

6.            Goel V, Grossmann IE, El-Bakry AS,
Mulkay EL. A novel branch and bound algorithm for optimal development of gas
fields under uncertainty in reserves. Computers & Chemical Engineering. 2006;30(6-7):1076-1092.

7.            Colvin M, Maravelias CT. A stochastic
programming approach for clinical trial planning in new drug development. Computers
& Chemical Engineering. 2008;32(11):2626-2642.

8.            Colvin M, Maravelias CT. Scheduling
of testing tasks and resource planning in new product development using
stochastic programming. Computers & Chemical Engineering. 2009;33(5):964-976.