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.