(411a) A Two-Stage Stochastic Programming Model for Optimization Under Exogenous and Type I Endogenous Uncertainties

Stochastic programming (SP) is one of the common ways of solving optimization problems under uncertainty. This framework is a scenario-based approach, where each scenario is a different realization of the uncertainty present¹. The uncertainty within these problems come in two different types: decision-independent, exogenous, and decision-dependent, endogenous, uncertainty². A great deal of work has been performed analyzing problems with exogenous uncertainty. Recently, a focus on problems with endogenous uncertainty has emerged^2–6. There are two types of endogenous uncertainty. Type-1 endogenous uncertainty, where decisions made affect the probability distribution of the resulting scenarios. For type-2 endogenous uncertainty, decisions impact the timing of uncertainty resolution. In this work, we focus on stochastic programs with type-1 endogenous uncertainty.

Stochastic programming models containing type-1 endogenous uncertainty tend to arise from problems in which the decision-maker takes imperfect actions, or the results of these actions are stochastic themselves. The reliability optimization of a process through the planning of maintenance⁷ or the optimization of the lifetime of an oil well by planning recompletions for the well⁸ can be example problems. These problems are generally nonlinear and non-convex due to the probability measure of each scenario being dependent on the decisions made. Two recent studies^6,9 aims to solve SPs with decision-dependent probabilities. Medal et al.⁶ present a two-stage stochastic program of a resource allocation problem for facility protection from natural disasters. Two solution approaches were proposed to solve this problem. The first is a greedy algorithm in which protection is iteratively added to the facilities with the largest benefit seen by the additional resources until all resources are allocated. The second approach is a reformulation of the original SP model that exploits the problem characteristics and structure. The authors enumerated all potential recourse actions, estimated their probabilities, and treated them as parameters in the model, which yielded an equivalent mixed integer linear programming (MILP) model. The results showed that the greedy algorithm obtained as good or better solutions than the solution of the MILP model given a computational budget. Hellemo et al.⁹ introduce a general procedure to incorporate continuous distributions within a two-stage stochastic program (TSSP) where the first stage decisions are the parameters of the endogenous uncertainty’s probability distributions. The authors use these probability distributions directly and the approximations of the distributions to show that the incorporation of probability distributions with continuous parameters may be modeled without the need for approximations while maintaining computational tractability for MINLP solvers.

In this study, we introduce a two-stage stochastic programming model under both exogenous and type-1 endogenous uncertainty. The first stage binary decision variables, , directly impact the probabilities associated with the outcome of possible results due to these decisions. is a vector to define a total of actions to take on the system. In the second stage, fixed recourse actions, , are taken given the resulting outcome of and the exogenous uncertainty pertaining to the state of the system, . The objective of the model is to maximize the expected benefit of the first stage decisions through fixed recourse actions, . The probabilities of each outcome, , depends on both first stage decisions and the exogenous uncertainty in the problem. With actions defined by the vector , there is a nonlinearity in the model for N greater than one. The probability measure of the overall outcome then becomes a product of the probabilities associated with each of the N actions taken, . Further nonlinearity of the model occurs through the calculation of the expected benefit where the product of the outcome probability and the benefit from the fixed recourse action are computed, , resulting in a mixed integer nonlinear programming (MINLP) model. The nonlinear terms in the model can be treated as the multiplication of binary variables, which we linearize by the introduction of new variables^10,11 to obtain an equivalent MILP.

We apply the developed TSSP models to a case study that determines the optimal ages for colorectal cancer (CRC) screening by maximizing the expected total quality-adjusted life-years gained (QALYG) due to screening. Colorectal cancer is the third most common and the second most deadly form of cancer worldwide¹². Based on the late-stage 5-year and the early-stage 5-year survival rates, the early detection of CRC and its precursors via screening is an effective mitigation technique to reduce the overall impact of CRC on society. The first stage decisions of the TSSP model are the ages at which a population should be screened with a colonoscopy. Type I endogenous uncertainty arises from the imperfect nature of the screening test. The probability of detecting CRC, or its precursors, depends both on the test used for screening as well as the current, unknown health state of the individual being screened. The source of exogenous uncertainty is the uncertain nature of the progression of CRC within the human body. The distribution of the exogenous uncertainty is constructed in a data-driven approach, where the data comes from multiple sources including various clinical trials^13–19 and the U.S. National Institute of Health’s Surveillance Epidemiology and End-Results (SEER) database²⁰. In the model, each scenario represents a single individual with a differing life history. The fixed recourse actions represent the medical intervention to modify an individual’s life history dependent on the outcome of the first stage decisions.

We formulate the CRC screening problem using our TSSP models (MINLP and MILP), where we utilize the direct calculations of the probability measure for each scenario. The first formulation, MINLP1, is the original TSSP model. The second model, MINLP2, is a modified MINLP in which a variable is introduced to remove the nonlinear terms associated with calculating the probability measure of the outcome. The final model is the equivalent MILP model of the TSSP model. The models are implemented in PYOMO using Python 3.6 and solved to optimality using BARON 20.4.14 for the MINLP models and CPLEX 12.6.3.0 for the MILP model. Despite being the largest of the three models, the MILP model is solved quicker (several orders of magnitude shorter) than the MINLP models.

References

1. Birge, J. R. & Louveaux, F. Introduction to stochastic programming. (Springer Science & Business Media, 2011).
2. Tarhan, B., Grossmann, I. E. & Goel, V. Stochastic Programming Approach for the Planning of Offshore Oil or Gas Field Infrastructure under Decision-Dependent Uncertainty. Ind. Eng. Chem. Res. 48, 3078–3097 (2009).
3. Zeng, Z. & Cremaschi, S. Artificial lift infrastructure planning for shale gas producing horizontal wells. Proc. FOCAPO/CPC, Tuscan, AZ, USA 8–12 (2017).
4. Goel, V. & Grossmann, I. E. A stochastic programming approach to planning of offshore gas field developments under uncertainty in reserves. Comput. Chem. Eng. 28, 1409–1429 (2004).
5. Colvin, M. & Maravelias, C. T. A stochastic programming approach for clinical trial planning in new drug development. Comput. Chem. Eng. 32, 2626–2642 (2008).
6. Medal, H. R., Pohl, E. A. & Rossetti, M. D. Allocating Protection Resources to Facilities When the Effect of Protection is Uncertain. IIE Trans. 48, 220–234 (2016).
7. Zied, H., Sofiene, D. & Nidhal, R. An optimal production/maintenance planning under stochastic random demand, service level and failure rate. in 2009 IEEE International Conference on Automation Science and Engineering 292–297 (2009).
8. Drouven, M. G., Grossmann, I. E. & Cafaro, D. C. Stochastic programming models for optimal shale well development and refracturing planning under uncertainty. AIChE J. 63, 4799–4813 (2017).
9. Hellemo, L., Barton, P. I. & Tomasgard, A. Decision-dependent probabilities in stochastic programs with recourse. Comput. Manag. Sci. 15, 369–395 (2018).
10. Hammer, P. L. & Rudeanu, S. Boolean methods in operations research and related areas. 7, (Springer Science & Business Media, 2012).
11. Oral, M. & Kettani, O. A linearization procedure for quadratic and cubic mixed-integer problems. Oper. Res. 40, S109--S116 (1992).
12. World Heath Organization. Cancer. (2020). Available at: https://www.who.int/news-room/fact-sheets/detail/cancer. (Accessed: 27th February 2019)
13. Hardcastle, J. D. et al. Randomised, controlled trial of faecal occult blood screening for colorectal cancer: results for first 107 349 subjects. Lancet 333, 1160–1164 (1989).
14. Atkin, W. S. et al. Once-only flexible sigmoidoscopy screening in prevention of colorectal cancer: a multicentre randomised controlled trial. Lancet 375, 1624–1633 (2010).
15. Kronborg, O., Fenger, C., Olsen, J., Bech, K. & Søndergaard, O. Repeated screening for colorectal cancer with fecal occult blood test: a prospective randomized study at Funen, Denmark. Scand. J. Gastroenterol. 24, 599–606 (1989).
16. Lieberman, D. A. & Smith, F. W. Screening for colon malignancy with colonoscopy. Am. J. Gastroenterol. 86, (1991).
17. Koretz, R. L. Malignant polyps: are they sheep in wolves’ clothing? Ann. Intern. Med. 118, 63–68 (1993).
18. Rickert, R. R., Auerbach, O., Garfinkel, L., Hammond, E. C. & Frasca, J. M. Adenomatous lesions of the large bowel: an autopsy survey. Cancer 43, 1847–1857 (1979).
19. Thomas, W. M., Pye, G., Hardcastle, J. D. & Walker, A. R. Screening for colorectal carcinoma: an analysis of the sensitivity of haemoccult. Br. J. Surg. 79, 833–835 (1992).

20. Surveillance, Epidemiology, and End Results Program. SEER