×

An interior-point implementation developed and tuned for radiation therapy treatment planning. (English) Zbl 1387.90124

Summary: While interior-point methods share the same fundamentals, the implementation determines the actual performance. In order to attain the highest efficiency, different applications may require differently tuned implementations. In this paper we describe an implementation specifically designed for optimisation in radiation therapy. These problems are large-scale nonlinear (and sometimes nonconvex) constrained optimisation problems, consisting of both sparse and dense data. Several application-specific properties are exploited to enhance efficiency. Permuting, tiling and mixed precision arithmetic allow the algorithm to optimally process the mixed dense and sparse data matrices (making this step 2.2 times faster, and overall runtime reduction of \(55\%\)) and scalability (16 threads resulted in a speed-up factor of 9.8 compared to singlethreaded performance, against a speed-up factor of 7.7 for the less optimised implementation). Predefined cost-functions are hard-coded and the computationally expensive second derivatives are written in canonical form, and combined if multiple cost-functions are defined for the same clinical structure. The derivatives are then computed using a scaled matrix-matrix product. A cheap initialisation strategy based on the background knowledge reduces the number of iterations by \(11\%\). We also propose a novel combined Mehrotra-Gondzio approach. The algorithm is extensively tested on a dataset consisting of 120 patients, distributed over 6 tumour sites/approaches. This test dataset is made publicly available.

MSC:

90C06 Large-scale problems in mathematical programming
90C25 Convex programming
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
90C51 Interior-point methods
90C90 Applications of mathematical programming
97M40 Operations research, economics (aspects of mathematics education)
97M60 Biology, chemistry, medicine (aspects of mathematics education)

References:

[1] Alber, M., Meedt, G., Nüsslin, F.: On the degeneracy of the IMRT optimization problem. Med. Phys. 29, 2584-2589 (2002). doi:10.1118/1.1500402 · doi:10.1118/1.1500402
[2] Alber, M., Reemtsen, R.: Intensity modulated radiotherapy treatment planning by use of a barrier-penalty multiplier method. Optim. Methods Softw. 22, 391-411 (2007). doi:10.1080/10556780600604940 · Zbl 1170.90529 · doi:10.1080/10556780600604940
[3] Aleman, D.M., Glaser, D., Romeijn, H.E., Dempsey, J.F.: Interior point algorithms: guaranteed optimality for fluence map optimization in IMRT. Phys. Med. Biol. 55, 5467-5482 (2010). doi:10.1088/0031-9155/55/18/013 · doi:10.1088/0031-9155/55/18/013
[4] Aleman, D.M., Romeijn, H.E., Dempsey, J.F.: A response surface approach to beam orientation optimization in intensity modulated radiation therapy treatment planning. INFORMS J. Comput. 21, 62-76 (2009). doi:10.1287/ijoc.1080.0279 · doi:10.1287/ijoc.1080.0279
[5] ATLAS: Building the general matrix multiply from the L1 cache-contained multiply. http://www.netlib.org/atlas/developer/atlas_contrib/node11.html
[6] Benson, H., Shanno, D., Vanderbei, R.: Interior-point methods for nonconvex nonlinear programming: filter methods and merit functions. Comput. Optim. Appl. 23, 257-272 (2002). doi:10.1023/A:1020533003783 · Zbl 1022.90017 · doi:10.1023/A:1020533003783
[7] Benson, H., Shanno, D., Vanderbei, R.: A comparative study of large-scale nonlinear optimization algorithms. In: High Performance Algorithms and Software for Nonlinear Optimization, pp. 95-127. Springer, New York (2003). doi:10.1007/978-1-4613-0241-4_5 · Zbl 1066.90138
[8] Bokrantz, R.: Multicriteria optimization for managing tradeoffs in radiation therapy treatment planning. Ph.D. thesis, KTH Royal Institute of Technology, Sweden (2013)
[9] Breedveld, S., Craft, D., van Haveren, R., Heijmen, B.: Multi-criteria optimisation and decision-making in radiotherapy (submitted) (2017) · Zbl 1430.90503
[10] Breedveld, S., Heijmen, B.: TROTS - The Radiotherapy Optimisation Test Set. http://www.erasmusmc.nl/radiotherapytrots/ (2016) · Zbl 1190.65053
[11] Breedveld, S., Heijmen, B.: Data for TROTS—the radiotherapy optimisation test set. Data Br. 12, 143-149 (2017). doi:10.1016/j.dib.2017.03.037 · doi:10.1016/j.dib.2017.03.037
[12] Breedveld, S., Storchi, P., Heijmen, B.: The equivalence of multi-criteria methods for radiotherapy plan optimization. Phys. Med. Biol. 54, 7199-7209 (2009). doi:10.1088/0031-9155/54/23/011 · doi:10.1088/0031-9155/54/23/011
[13] Breedveld, S., Storchi, P., Keijzer, M., Heemink, A.W., Heijmen, B.: A novel approach to multi-criteria inverse planning for IMRT. Phys. Med. Biol. 52, 6339-6353 (2007). doi:10.1088/0031-9155/52/20/016 · doi:10.1088/0031-9155/52/20/016
[14] Breedveld, S., Storchi, P., Keijzer, M., Heijmen, B.: Fast, multiple optimizations of quadratic dose objective functions in IMRT. Phys. Med. Biol. 51, 3569-3579 (2006). doi:10.1088/0031-9155/51/14/019 · doi:10.1088/0031-9155/51/14/019
[15] Breedveld, S., Storchi, P., Voet, P., Heijmen, B.: iCycle: integrated, multicriterial beam angle, and profile optimization for generation of coplanar and noncoplanar IMRT plans. Med. Phys. 39, 951-963 (2012). doi:10.1118/1.3676689 · doi:10.1118/1.3676689
[16] Buttari, A., Langou, J., Kurzak, J., Dongarra, J.: A class of parallel tiled linear algebra algorithms for multicore architectures. Parallel Comput. 35, 38-53 (2009). doi:10.1016/j.parco.2008.10.002 · doi:10.1016/j.parco.2008.10.002
[17] Catalyürek, Ü., Aykanat, C.: Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication. IEEE Trans. Parallel Distrib. 10, 673-693 (1999). doi:10.1109/71.780863 · doi:10.1109/71.780863
[18] Chen, W., Craft, D., Madden, T., Zhang, K., Kooy, H., Herman, G.: A fast optimization algorithm for multicriteria intensity modulated proton therapy planning. Med. Phys. 37, 4938-4945 (2010). doi:10.1118/1.3481566 · doi:10.1118/1.3481566
[19] Craft, D.L., Halabi, T.F., Shih, H.A., Bortfeld, T.R.: Approximating convex Pareto surfaces in multiobjective radiotherapy planning. Med. Phys. 33, 3399-3407 (2006). doi:10.1118/1.2335486 · doi:10.1118/1.2335486
[20] CUTEst: CUTEst—a constrained and unconstrained testing environment on steroids. http://ccpforge.cse.rl.ac.uk/gf/project/cutest/wiki/
[21] Dong, P., Lee, P., Ruan, D., Long, T., Romeijn, E., Yang, Y., Low, D., Kupelian, P., Sheng, K.: 4Pi non-coplanar liver SBRT: a novel delivery technique. Int. J. Radiat. Oncol. Biol. Phys. 85, 1360-1366 (2012). doi:10.1016/j.ijrobp.2012.09.028 · doi:10.1016/j.ijrobp.2012.09.028
[22] Gertz, M., Nocedal, J., Sartenaer, A.: A starting-point strategy for nonlinear interior methods. Appl. Math. Lett. 17, 945-952 (2004). doi:10.1016/j.aml.2003.09.005 · Zbl 1087.90084 · doi:10.1016/j.aml.2003.09.005
[23] Gibbs, N., Poole, W., Stockmeyer, P.: A comparison of several bandwidth and profile reduction algorithms. ACM Trans. Math. Softw. 2(4), 322-330 (1976). doi:10.1145/355705.355707 · Zbl 0345.65014 · doi:10.1145/355705.355707
[24] Gondzio, J.: Implementing Cholesky factorization for interior point methods of linear programming. Optimization 27, 121-140 (1993). doi:10.1080/02331939308843876 · Zbl 0819.65097 · doi:10.1080/02331939308843876
[25] Gondzio, J.: Multiple centrality corrections in a primal-dual method for linear programming. Comput. Optim. Appl. 6, 137-157 (1996). doi:10.1007/BF00249643 · Zbl 0860.90084 · doi:10.1007/BF00249643
[26] Gondzio, J.: Matrix-free interior-point method. Comput. Optim. Appl. 51, 457-480 (2012). doi:10.1007/s10589-010-9361-3 · Zbl 1241.90179 · doi:10.1007/s10589-010-9361-3
[27] Gondzio, J., González-Brevis, P., Munari, P.: New developments in the primal-dual column generation technique. Eur. J. Oper. Res. 224, 41-51 (2013). doi:10.1016/j.ejor.2012.07.024 · Zbl 1292.90318 · doi:10.1016/j.ejor.2012.07.024
[28] Gondzio, J., Grothey, A.: A new unblocking technique to warmstart interior point methods based on sensitivity analysis. SIAM J. Optim. 19, 1184-1210 (2008). doi:10.1137/060678129 · Zbl 1177.90411 · doi:10.1137/060678129
[29] Gorissen, B.L.: On Newton based algorithms for inverse planning of intensity-modulated proton therapy (submitted) (2016)
[30] Gustavson, F.G.: Two fast algorithms for sparse matrices: multiplication and permuted transposition. ACM Trans. Math. Softw. 4, 250-269 (1978). doi:10.1145/355791.355796 · Zbl 0384.65016 · doi:10.1145/355791.355796
[31] Halabi, T., Craft, D., Bortfeld, T.: Dose-volume objectives in multi-criteria optimization. Phys. Med. Biol. 51, 3809-3818 (2006). doi:10.1088/0031-9155/51/15/014 · doi:10.1088/0031-9155/51/15/014
[32] Van Haveren, R., Breedveld, S.: A canonical and computationally efficient form for the gradient and Hessian of simple composite functions in nonlinear programming (submitted) (2017)
[33] Van Haveren, R., Breedveld, S., Keijzer, M., Voet, P., Heijmen, B., Ogryczak, W.: Lexicographic extension of the reference point method applied in radiation therapy treatment planning. Eur. J. Oper. Res. (in press) (2017). doi:10.1016/j.ejor.2017.04.062 · Zbl 1380.90307
[34] Van Haveren, R., Ogryczak, W., Verduijn, G., Keijzer, M., Heijmen, B., Breedveld, S.: Fast and fuzzy multi-objective radiotherapy treatment plan generation for head-and-neck cancer patients with the lexicographic reference point method (LRPM). Phys. Med. Biol. 62, 4318 (2017). doi:10.1088/1361-6560/62/11/4318 · doi:10.1088/1361-6560/62/11/4318
[35] Hock, W., Schittkowski, K.: Test Examples for Nonlinear Programming Codes. Springer, New York (1981) · Zbl 0452.90038 · doi:10.1007/978-3-642-48320-2
[36] Hoffmann, A.L., Siem, A.Y.D., den Hertog, D., Kaanders, J.H.A.M., Huizenga, H.: Derivative-free generation and interpolation of convex Pareto optimal IMRT plans. Phys. Med. Biol. 51, 6349-6369 (2006). doi:10.1088/0031-9155/51/24/005 · doi:10.1088/0031-9155/51/24/005
[37] Jee, K.W., McShan, D.L., Fraass, B.A.: Lexicographic ordering: intuitive multicriteria optimization for IMRT. Phys. Med. Biol. 52, 1845-1861 (2007). doi:10.1088/0031-9155/52/7/006 · doi:10.1088/0031-9155/52/7/006
[38] Kurzak, J., Ltaief, H., Dongarra, J., Badia, R.: Scheduling dense linear algebra operations on multicore processors. Concurr. Comput. Pract. Exp. 22, 15-44 (2009). doi:10.1002/cpe.1467 · doi:10.1002/cpe.1467
[39] Li, R., Xing, L.: An adaptive planning strategy for station parameter optimized radiation therapy (SPORT): Segmentally boosted VMAT. Med. Phys. 40, 050701 (2013). doi:10.1118/1.4802748 · doi:10.1118/1.4802748
[40] Llacer, J., Deasy, J.O., Bortfeld, T.R., Solberg, T.D., Promberger, C.: Absence of multiple local minima effects in intensity modulated optimization with dose-volume constraints. Phys. Med. Biol. 48, 183-210 (2003). doi:10.1088/0031-9155/48/2/304 · doi:10.1088/0031-9155/48/2/304
[41] Lustig, I., Marsten, R., Shanno, D.: On implementing Mehrotraś predictor-corrector interior-point method for linear programming 2, 435-449 (1992). doi:10.1137/0802022 · Zbl 0771.90066
[42] Mehrotra, S.: On the implementation of a primal-dual interior point method. SIAM J. Optim. 2, 575-601 (1992). doi:10.1137/0802028 · Zbl 0773.90047 · doi:10.1137/0802028
[43] Men, C., Romeijn, E., Taşkin, C., Dempsey, J.: An exact approach to direct aperture optimization in IMRT treatment planning. Phys. Med. Biol. 52, 7333-7352 (2007). doi:10.1088/0031-9155/52/24/009 · doi:10.1088/0031-9155/52/24/009
[44] Netlib: Netlib. http://www.netlib.org/lp/
[45] Niemierko, A.: Reporting and analyzing dose distributions: a concept of equivalent uniform dose. Med. Phys. 24, 103-110 (1997). doi:10.1118/1.598063 · doi:10.1118/1.598063
[46] Nocedal, J., Wright, S.: Numerical Optimization. Springer, New York (2000) · Zbl 0930.65067
[47] Pagès, A., Gondzio, J., Nabona, N.: Warmstarting for interior point methods applied to the long-term power planning problem. Eur. J. Oper. Res. 197, 112-125 (2009). doi:10.1016/j.ejor.2008.05.022 · Zbl 1157.90498 · doi:10.1016/j.ejor.2008.05.022
[48] Paige, C.C., Saunders, M.A.: LSQR: an algorithm for sparse linear equations and sparse least squares. ACM Trans. Math. Softw. 8, 43-71 (1982). doi:10.1145/355984.355989 · Zbl 0478.65016 · doi:10.1145/355984.355989
[49] Pellegrini, F.: Software package and libraries for sequential and parallel graph partitioning, static mapping and clustering, sequential mesh and hypergraph partitioning, and sequential and parallel sparse matrix block ordering. http://www.labri.fr/perso/pelegrin/scotch/ (2012)
[50] Pissanetsky, S.: Sparse Matrix Technology. Academic, London (1984) · Zbl 0536.65019
[51] Rocha, H., Dias, J., Ferreira, B., Lopes, M.: Noncoplanar beam angle optimization in IMRT treatment planning using pattern search methods. J. Phys. Conf. Ser. 616, 12014-12023 (2015) · doi:10.1088/1742-6596/616/1/012014
[52] Romeijn, H.E., Ahuja, R.K., Dempsey, J.F., Kumar, A.: A column generation approach to radiation therapy treatment planning using aperture modulation. SIAM J. Optim. 15, 838-862 (2005). doi:10.1137/040606612 · Zbl 1077.90084 · doi:10.1137/040606612
[53] Romeijn, H.E., Ahuja, R.K., Dempsey, J.F., Kumar, A., Li, J.G.: A novel linear programming approach to fluence map optimization for intensity modulated radiation therapy treatment planning. Phys. Med. Biol. 48, 3521-3542 (2003). doi:10.1088/0031-9155/48/21/005 · doi:10.1088/0031-9155/48/21/005
[54] Romeijn, H.E., Dempsey, J.F., Li, J.G.: A unifying framework for multi-criteria fluence map optimization models. Phys. Med. Biol. 49, 1991-2013 (2004). doi:10.1088/0031-9155/49/10/011 · doi:10.1088/0031-9155/49/10/011
[55] Rossi, L., Breedveld, S., Aluwini, S., Heijmen, B.: Non-coplanar beam angle class solutions to replace time-consuming patient-specific beam angle optimization in robotic prostate SBRT. Int. J. Radiat. Oncol. Biol. Phys. 92, 762-770 (2015). doi:10.1016/j.ijrobp.2015.03.013 · doi:10.1016/j.ijrobp.2015.03.013
[56] Rossi, L., Breedveld, S., Heijmen, B.J.M., Voet, P.W.J., Lanconelli, N., Aluwini, S.: On the beam direction search space in computerized non-coplanar beam angle optimization for IMRT - prostate SBRT. Phys. Med. Biol. 57, 5441-5458 (2012). doi:10.1088/0031-9155/57/17/5441 · doi:10.1088/0031-9155/57/17/5441
[57] Shanno, D.F., Vanderbei, R.J.: Interior-point methods for nonconvex nonlinear programming: orderings and higher-order methods. Math. Program. Ser. B 87, 303-316 (2000). doi:10.1007/s101070050116 · Zbl 1054.90091 · doi:10.1007/s101070050116
[58] Sharfo, A.W., Voet, P., Breedveld, S., Mens, J.W., Hoogeman, M., Heijmen, B.: Comparison of VMAT and IMRT strategies for cervical cancer patients using automated planning. Radiother. Oncol. 114, 395-401 (2015). doi:10.1016/j.radonc.2015.02.006 · doi:10.1016/j.radonc.2015.02.006
[59] Simon, H.: Partitioning of unstructured problems for parallel processing. Comput. Syst. Eng. 2, 135-148 (1991). doi:10.1016/0956-0521(91)90014-V · doi:10.1016/0956-0521(91)90014-V
[60] Sonneveld, P., van Gijzen, M.B.: IDR(s): a family of simple and fast algorithms for solving large nonsymmetric linear systems. SIAM J. Sci. Comput. 31, 1035-1062 (2008). doi:10.1137/070685804 · Zbl 1190.65053 · doi:10.1137/070685804
[61] Thörnqvist, S., Hysing, L.B., Zolnáy, A.G., Söhn, M., Hoogeman, M.S., Muren, L.P., Bentzen, L., Heijmen, B.J.M.: Treatment simulations with a statistical deformable motion model to evaluate margins for multiple targets in radiotherapy for high-risk prostate cancer. Radiother. Oncol. 109, 344-349 (2013). doi:10.1016/j.radonc.2013.09.012 · doi:10.1016/j.radonc.2013.09.012
[62] Tian, Z., Peng, F., Folkerts, M., Tan, J., Jia, X., Jiang, S.: Multi-GPU implementation of a VMAT treatment plan optimization algorithm. Med. Phys. 42, 2841-2852 (2015). doi:10.1118/1.4919742 · doi:10.1118/1.4919742
[63] Vanderbei, R.: Nonlinear optimization models. http://orfe.princeton.edu/ · Zbl 1257.90049
[64] Vanderbei, R.J.: LOQO: an interior point code for quadratic programming. Optim. Methods Softw. 11, 451-484 (1999). doi:10.1080/10556789908805759 · Zbl 0973.90518 · doi:10.1080/10556789908805759
[65] Vanderbei, R.J., Shanno, D.F.: An interior point algorithm for nonconvex nonlinear programming. Comput. Optim. Appl. 13, 231-252 (1999). doi:10.1023/A:1008677427361 · Zbl 1040.90564 · doi:10.1023/A:1008677427361
[66] Voet, P., Breedveld, S., Dirkx, M., Levendag, P., Heijmen, B.: Integrated multi-criterial optimization of beam angles and intensity profiles for coplanar and non-coplanar head and neck IMRT and implications for VMAT. Med. Phys. 39, 4858-4865 (2012). doi:10.1118/1.4736803 · doi:10.1118/1.4736803
[67] Voet, P., Dirkx, M., Breedveld, S., Al-Mamgani, A., Incrocci, L., Heijmen, B.: Fully automated VMAT plan generation for prostate cancer patients. Int. J. Radiat. Oncol. Biol. Phys. 88, 1175-1179 (2014). doi:10.1016/j.ijrobp.2013.12.046 · doi:10.1016/j.ijrobp.2013.12.046
[68] Voet, P., Dirkx, M., Breedveld, S., Fransen, D., Levendag, P., Heijmen, B.: Towards fully automated multi-criterial plan generation: a prospective clinical study. Int. J. Radiat. Oncol. Biol. Phys. 85, 866-872 (2013). doi:10.1016/j.ijrobp.2012.04.015 · doi:10.1016/j.ijrobp.2012.04.015
[69] Van de Water, S., Kooy, H., Heijmen, B., Hoogeman, M.: Shortening delivery times of intensity modulated proton therapy by reducing proton energy layers during treatment plan optimization. Int. J. Radiat. Oncol. Biol. Phys. 92, 460-468 (2015). doi:10.1016/j.ijrobp.2015.01.031 · doi:10.1016/j.ijrobp.2015.01.031
[70] Wilkens, J.J., Alaly, J.R., Zakarian, K., Thorstad, W.L., Deasy, J.O.: IMRT treatment planning based on prioritizing prescription goals. Phys. Med. Biol. 52, 1675-1692 (2007). doi:10.1088/0031-9155/52/6/009 · doi:10.1088/0031-9155/52/6/009
[71] Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM Publishers, Philadelphia (1997) · Zbl 0863.65031 · doi:10.1137/1.9781611971453
[72] Wu, Q., Mohan, R.: Algorithms and functionality of an intensity modulated radiotherapy optimization system. Med. Phys. 27, 701-711 (2000). doi:10.1118/1.598932 · doi:10.1118/1.598932
[73] Yildirim, E.A., Wright, S.J.: Warm-start strategies in interior-point methods for linear programming. SIAM J. Optim. 12, 782-810 (2002). doi:10.1137/S1052623400369235 · Zbl 1007.90079 · doi:10.1137/S1052623400369235
[74] Ziegenhein, P., Kamerling, C., Bangert, M., Kunkel, J., Oelfke, U.: Performance-optimized clinical IMRT planning on modern CPUs. Phys. Med. Biol. 58, 3705-3715 (2013). doi:10.1088/0031-9155/58/11/3705 · doi:10.1088/0031-9155/58/11/3705
[75] Zinchenko, Y., Craig, T., Keller, H., Terlaky, T., Sharpe, M.: Controlling the dose distribution with gEUD-type constraints within the convex radiotherapy optimization framework. Phys. Med. Biol. 53, 3231-3250 (2008). doi:10.1088/0031-9155/53/12/011 · doi:10.1088/0031-9155/53/12/011
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.