Real-time radiation treatment planning with optimality guarantees via cluster and bound methods. (English) Zbl 07283441

Summary: Radiation therapy is widely used in cancer treatment; however, plans necessarily involve tradeoffs between tumor coverage and mitigating damage to healthy tissue. Although current hardware can deliver custom-shaped beams from any angle around the patient, choosing (from all possible beams) an optimal set of beams that maximizes tumor coverage while minimizing collateral damage and treatment time is intractable. Furthermore, even though planning algorithms used in practice consider highly restricted sets of candidate beams, the time per run combined with the number of runs required to explore clinical tradeoffs results in planning times of hours to days. We propose a suite of cluster and bound methods that we hypothesize will (1) yield higher-quality plans by optimizing over much (i.e., 100-fold) larger sets of candidate beams, and/or (2) reduce planning time by allowing clinicians to search through candidate plans in real time. Our methods hinge on phrasing the treatment-planning problem as a convex problem. To handle large-scale optimizations, we form and solve compressed approximations to the full problem by clustering beams (i.e., columns of the dose deposition matrix used in the optimization) or voxels (rows of the matrix). Duality theory allows us to bound the error incurred when applying an approximate problem’s solution to the full problem. We observe that beam clustering and voxel clustering both yield excellent solutions while enabling a 10- to 200-fold speedup.


90Cxx Mathematical programming
92C50 Medical applications (general)
Full Text: DOI Link


[1] Ahmed S, Gozbasi O, Savelsbergh M, Crocker I, Fox T, Schreibmann E (2010) An automated intensity-modulated radiation therapy planning system. INFORMS J. Comput. 22(4):568-583.Link, Google Scholar · Zbl 1243.90270
[2] Aleman DM, Romeijn HE, Dempsey JF (2008) A response surface approach to beam orientation optimization in intensity-modulated radiation therapy treatment planning. INFORMS J. Comput. 21(1):62-76.Link, Google Scholar
[3] Aleman DM, Glaser D, Romeijn HE, Dempsey JF (2010) Interior point algorithms: Guaranteed optimality for fluence map optimization in IMRT. Phys. Medicine Biol. 55(18):5467-5482.Crossref, Google Scholar
[4] Appenzoller LM, Michalski JM, Thorstad WL, Mutic S, Moore KL (2012) Predicting dose-volume histograms for organs-at-risk in IMRT planning. Medical Phys. 39(12):7446-7461.Crossref, Google Scholar
[5] Baatar D, Boland N, Johnston R, Hamacher HW (2009) A new sequential extraction heuristic for optimizing the delivery of cancer radiation treatment using multileaf collimators. INFORMS J. Comput. 21(2):224-241.Link, Google Scholar · Zbl 1243.90253
[6] Banger M, Oelfke U (2010) Spherical cluster analysis for beam angle optimization in intensity-modulated radiation therapy treatment planning. Phys. Medicine Biol. 55(19):6023-6037.Crossref, Google Scholar
[7] Bentzen SM, Constine LS, Deasy JO, Eisbruch A, Jackson A, Marks LB, Haken T, Randall K, Yorke ED (2010) Quantitative analyses of normal tissue effects in the clinic (QUANTEC): An introduction to the scientific issues. Internat. J. Radiation Oncology Biol. Phys. 76(3):S3-S9.Crossref, Google Scholar
[8] Bertsimas D, Nohadani O, Teo KM (2010) Nonconvex robust optimization for problems with constraints. INFORMS J. Comput. 22(1):44-58.Link, Google Scholar · Zbl 1243.90176
[9] Bezanson J, Edelman A, Karpinski S, Shah VB (2014) Julia: A fresh approach to numerical computing. SIAM Rev. 59(1):65-98.Crossref, Google Scholar · Zbl 1356.68030
[10] Bokrantz R, Forsgren A (2013) An algorithm for approximating convex pareto surfaces based on dual techniques. INFORMS J. Comput. 25(2):377-292.Link, Google Scholar
[11] Boutilier JJ, Craig T, Sharpe MB, Chan TCY (2016) Sample size requirements for knowledge-based treatment planning. Medical Phys. 43(3):1212-1221.Crossref, Google Scholar
[12] Boutsidis C, Zouzias A, Mahoney MW, Drineas P (2015) Randomized dimensionality reduction fork-means clustering. IEEE Trans. Inform. Theory 61(2):1045-1062.Crossref, Google Scholar · Zbl 1359.62232
[13] Boyd S, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
[14] Chan TCY, Craig T, Lee T, Sharpe MB (2014) Generalized inverse multiobjective optimization with application to cancer therapy. Oper. Res. 62(3):680-695.Link, Google Scholar · Zbl 1302.90194
[15] Chen W, Craft D, Madden TM, Zhang K, Kooy HM, Herman GT (2010) A fast optimization algorithm for multicriteria intensity modulated proton therapy planning. Medical Phys. 37(9):4938-4945.Crossref, Google Scholar
[16] Craft D (2007) Local beam angle optimization with linear programming and gradient search. Phys. Medicine Biol. 52(7):N127-N135.Crossref, Google Scholar
[17] Craft D, Bortfeld TR (2008) How many plans are needed in an IMRT multi-objective plan database? Phys. Medicine Biol. 53(11):2785-2796.Crossref, Google Scholar
[18] Craft D, Halabi TF, Shih HA, Bortfeld TR (2006) Approximating convex Pareto surfaces in multiobjective radiotherapy planning. Medical Phys. 33(9):3399-3407.Crossref, Google Scholar
[19] Craft D, Hong TS, Shih HA, Bortfeld TR (2012a) Improved planning time and plan quality through multicriteria optimization for intensity-modulated radiotherapy. Internat. J. Radiation Oncology Biol. Phys. 82(1):e83-e90.Crossref, Google Scholar
[20] Craft D, McQuaid D, Wala J, Chen W, Salari E, Bortfeld T (2012b) Multicriteria VMAT optimization. Medical Phys. 39(2):686-696.Crossref, Google Scholar
[21] Dong P, Ungun B, Boyd S, Xing L (2016) Optimization of rotational arc station parameter optimized radiation therapy. Medical Phys. 43(9):4973-4982.Crossref, Google Scholar
[22] Dong P, Lee P, Ruan D, Long T, Romeijn HE, Yang Y, Low D, Kupelian P, Sheng K (2013a) 4πnon-coplanar liver SBRT: A novel delivery technique. Internat. J. Radiation Oncology Biol. Phys. 85(5):1360-1366.Crossref, Google Scholar
[23] Dong P, Lee P, Ruan D, Long T, Romeijn E, Low DA, Kupelian P, Abraham J, Yang Y, Sheng K (2013b) 4πnoncoplanar stereotactic body radiation therapy for centrally located or larger lung tumors. Internat. J. Radiation Oncology Biol. Phys. 86(3):407-413.Crossref, Google Scholar
[24] Dongarra JJ, Du Croz J, Hammarling S, Duff IS (1990) A set of level 3 basic linear algebra subprograms. ACM Trans. Math. Software 16(1):1-17.Crossref, Google Scholar · Zbl 0900.65115
[25] Dongarra JJ, Du Croz J, Hammarling S, Hanson RJ (1988) An extended set of fortran basic linear algebra subprograms. ACM Trans. Math. Software 14(1):1-17.Crossref, Google Scholar · Zbl 0639.65016
[26] Ernst AT, Mak VH, Mason LR (2009) An exact method for the minimum cardinality problem in the treatment planning of intensity-modulated radiotherapy. INFORMS J. Comput. 21(4):562-574.Link, Google Scholar · Zbl 1243.90272
[27] Fougner C, Boyd S (2018) Parameter selection and pre-conditioning for a graph form solver. Tempo R, Yurkovich S, Misra P, eds. Emerging Applications of Control and System Theory, Lecture Notes in Control and Information Sciences (Springer, Cham, Switzerland), 41-62.Crossref, Google Scholar · Zbl 1407.93126
[28] Ganage SA, Thool RC, Basit HA (2013) Heterogeneous computing based k-means clustering using Hadoop-MapReduce framework. Internat. J. Adv. Res. Comput. Sci. Software Engrg. 3(6):585-592.Google Scholar
[29] Jain AK, Murty MN, Flynn PJ (1999) Data clustering: A review. ACM Comput. Surveys 31(3):264-323.Crossref, Google Scholar
[30] Kessler ML, Mcshan DL, Epelman MA, Vineberg KA, Eisbruch A, Lawrence TS, Fraass BA (2005) Costlets: A generalized approach to cost functions for automated optimization of IMRT treatment plans. Optim. Engrg. 6(4):421-448.Crossref, Google Scholar · Zbl 1168.92313
[31] Küfer KH, Monz M, Scherrer A, Süss P (2009) Multicriteria optimization in intensity modulated radiotherapy planning. Pardalos PM, Romeijn HE, eds. Handbook of Optimization in Medicine (Springer, New York), 1-45.Crossref, Google Scholar
[32] Lawson CL, Hanson RJ, Kincaid DR, Krogh FT (1979) Basic linear algebra subprograms for fortran usage. ACM Trans. Math. Software 5(3):308-323.Crossref, Google Scholar · Zbl 0412.65022
[33] Lee T, Hammad M, Chan TCY, Craig T, Sharpe MB (2013) Predicting objective function weights from patient anatomy in prostate IMRT treatment planning. Medical Phys. 40(12):121706.Crossref, Google Scholar
[34] Li R, Xing L (2013) An adaptive planning strategy for station parameter optimized radiation therapy (SPORT): Segmentally boosted VMAT. Medical Phys. 40(5):050701.Crossref, Google Scholar
[35] Li R, Xing L, Horst KC, Bush K (2014) Nonisocentric treatment strategy for breast radiation therapy: A proof of concept study. Internat. J. Radiation Oncology Biol. Phys. 88(4):920-926.Crossref, Google Scholar
[36] Li N, Zarepisheh M, Uribe-Sanchez A, Moore K, Tian Z, Zhen X, Graves YJ, et al.. (2013) Automatic treatment plan re-optimization for adaptive radiotherapy guided with the initial plan DVHs. Phys. Medicine Biol. 58(24):8725-8738.Crossref, Google Scholar
[37] Lim GJ, Holder A, Reese J (2009) A clustering approach for optimizing beam angles in IMRT planning. Mathematical Sciences Technical Reports (MSTR) 14. Accessed November 19, 2018, https://scholar.rose-hulman.edu/math_mstr/14.Google Scholar
[38] Lim GJ, Ferris MC, Wright SJ, Shepard DM, Earl MA (2007) An optimization framework for conformal radiation treatment planning. INFORMS J. Comput. 19(3):366-380.Link, Google Scholar · Zbl 1241.90199
[39] Lloyd S (1982) Least squares quantization in PCM. IEEE Trans. Inform. Theory 28(2):129-137.Crossref, Google Scholar · Zbl 0504.94015
[40] Lu R, Radke RJ, Yang J, Happersett L, Yorke E, Jackson A (2008) Reduced-order constrained optimization in IMRT planning. Phys. Medicine Biol. 53(23):6749-6766.Crossref, Google Scholar
[41] Martin BC, Bortfeld TR, Castañon DA (2007) Accelerating IMRT optimization by voxel sampling. Phys. Medicine Biol. 52(24):7211-7228.Crossref, Google Scholar
[42] Moore KL, Appenzoller LM, Tan J, Michalski JM, Thorstad WL, Mutic S (2014) Clinical implementation of dose-volume histogram predictions for organs-at-risk in IMRT planning. J. Phys. Conf. Ser. 489(1):012055.Crossref, Google Scholar
[43] Otto K (2014) Real-time interactive treatment planning. Phys. Medicine Biol. 59(17):4845-4859.Crossref, Google Scholar
[44] Parikh N, Boyd S (2014) Block splitting for distributed optimization. Math. Programming Comput. 6(1):77-102.Crossref, Google Scholar · Zbl 1305.90291
[45] Peng F, Jia X, Gu X, Epelman MA, Romeijn HE, Jiang SB (2012) A new column-generation-based algorithm for VMAT treatment plan optimization. Phys. Medicine Biol. 57(14):4569-4588.Crossref, Google Scholar
[46] Pugachev A, Xing L (2002) Incorporating prior knowledge into beam orientation optimization in IMRT. Internat. J. Radiation Oncology Biol. Phys. 54(5):1565-1574.Crossref, Google Scholar
[47] Rennen G, van Dam ER, den Hertog D (2013) Enhancement of sandwich algorithms for approximating higher-dimensional convex pareto sets. INFORMS J. Comput. 23(4):493-517.Link, Google Scholar · Zbl 1243.90204
[48] Romeijn HE, Ahuja RK, Dempsey JF, Kumar A, Li JG (2003) A novel linear programming approach to fluence map optimization for intensity modulated radiation therapy treatment planning. Phys. Medicine Biol. 48(21):3521-3542.Crossref, Google Scholar
[49] Scherrer A, Küfer KH, Bortfeld T, Monz M, Alonso F (2005) IMRT planning on adaptive volume structures—a decisive reduction in computational complexity. Phys. Medicine Biol. 50(9):2033-2053.Crossref, Google Scholar
[50] Sculley D (2010) Web-scale k-means clustering. WWW ’10: Proc. 19th Internat. Conf. World Wide Web (Association for Computing Machinery, New York), 1177-1178.Crossref, Google Scholar
[51] Siem AYD, den Hertog D, Hoffmann AL (2011) A method for approximating univariate convex functions using only function value evaluations. INFORMS J. Comput. 23(4):591-604.Link, Google Scholar · Zbl 1243.90173
[52] Tropp JA (2004) Topics in sparse approximation. PhD thesis, University of Texas at Austin, Austin.Google Scholar
[53] Udell M, Horn C, Zadeh R, Boyd S (2016) Generalized low rank models. Foundations Trends Mach. Learn. 9(1):1-118.Crossref, Google Scholar · Zbl 1350.68221
[54] Xu R, Wunsch DC (2005) Survey of clustering algorithms. IEEE Trans. Neural Networks 16(3):645-678.Crossref, Google Scholar
[55] Xu R, Wunsch DC (2010) Clustering algorithms in biomedical research: A review. IEEE Rev. Biomedicine Engrg. 3:120-154.Crossref, Google Scholar
[56] Zarepisheh M, Ye Y, Boyd S, Li R, Xing L (2014a) SU-E-T-295: Simultaneous beam sampling and aperture shape optimization for station parameter optimized radiation therapy (SPORT). Medical Phys. 41(6):292.Crossref, Google Scholar
[57] Zarepisheh M, Long T, Li N, Tian Z, Romeijn HE, Jia X, Jiang SB (2014b) A DVH-guided IMRT optimization algorithm for automatic treatment planning and adaptive radiotherapy replanning. Medical Phys. 41(6):061711.Crossref, Google Scholar
[58] Zhang HH,
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.