The goal of radiotherapy is to cover a target area with a desired radiation dose while keeping the exposition of non-target areas as low as possible in order to reduce radiation side effects. In the case of Intensity Modulated Proton Therapy (IMPT), the dose distribution is typically designed via a treatment planning optimisation process based on classical optimisation algorithms on some objective functions.We investigate the planning optimisation problem under the point of view of the Theory of Complexity in general and, in particular, of the Combinatorial Optimisation Theory. We firstly give a formal definition of a simplified version of the problem that is in the complexity class NPO.We prove that above version is computationally hard, i.e. it belongs to the class NPO$\setminus$PTAS if $\mathbb{NP}\neq \mathbb{P}$.We show how Combinatorial Optimisation Theory can give valuable tools, both conceptual and practical, in treatment plan definition, opening the way for new deterministic algorithms with bounded time complexity which have to support the technological evolution up to adaptive plans exploiting near real time solutions.
Citation: Emma Altobelli, Maurizio Amichetti, Alessio Langiu, Francesca Marzi, Filippo Mignosi, Pietro Pisciotta, Giuseppe Placidi, Fabrizio Rossi, Giorgio Russo, Marco Schwarz, Stefano Smriglio, Sabina Vennarini. Combinatorial optimisation in radiotherapy treatment planning[J]. AIMS Medical Science, 2018, 5(3): 204-223. doi: 10.3934/medsci.2018.3.204
The goal of radiotherapy is to cover a target area with a desired radiation dose while keeping the exposition of non-target areas as low as possible in order to reduce radiation side effects. In the case of Intensity Modulated Proton Therapy (IMPT), the dose distribution is typically designed via a treatment planning optimisation process based on classical optimisation algorithms on some objective functions.We investigate the planning optimisation problem under the point of view of the Theory of Complexity in general and, in particular, of the Combinatorial Optimisation Theory. We firstly give a formal definition of a simplified version of the problem that is in the complexity class NPO.We prove that above version is computationally hard, i.e. it belongs to the class NPO$\setminus$PTAS if $\mathbb{NP}\neq \mathbb{P}$.We show how Combinatorial Optimisation Theory can give valuable tools, both conceptual and practical, in treatment plan definition, opening the way for new deterministic algorithms with bounded time complexity which have to support the technological evolution up to adaptive plans exploiting near real time solutions.
| [1] |
Wilson RR (1946) Radiological use of fast protons. Radiology 47: 487–491. doi: 10.1148/47.5.487
|
| [2] | Chuong MD, Mehta MP, Langen K, et al. (2014) Is proton beam therapy better than standard radiation therapy? The available evidence points to benefits of proton beam therapy, Clinical advances in hematology and oncology 12:861–864. http://europepmc.org/abstract/MED/ 25674846 |
| [3] | Ezzell GA, Galvin JM, Low D, et al. (2003) Guidance document on delivery, treatment planning, and clinical implementation of IMRT: Report of the IMRT subcommittee of the AAPM radiation therapy committee. Medical Physics 30: 2089–2115. https://doi.org/10.1118/1.1591194 |
| [4] | Hartmann J, Wölfelschneider J, Stache C, et al. (2016) Novel technique for high-precision stereotactic irradiation of mouse brains. Strahlentherapie und Onkologie 192: 806–814. https: //doi.org/10.1007/s00066-016-1014-8 |
| [5] | Lomax A (1999) Intensity modulation methods for proton radiotherapy. Physics in Medicine and Biology 44: 185. https://doi.org/10.1259/bjr.20150195 |
| [6] | Pieplenbosch S (2015) Potential Benefits of Proton Therapy in Clinic, Master's thesis. |
| [7] | van de Schoot AJAJ, de Boer P, Crama KF, et al. (2016) Dosimetric advantages of proton therapy compared with photon therapy using an adaptive strategy in cervical cancer. Acta Oncologica 55: 892–899. https://doi.org/10.3109/0284186X.2016.1139179 |
| [8] | Zelefsky MJ, Fuks Z, Happersett L, et al. (2000) Clinical experience with intensity modulated radiation therapy (IMRT) in prostate cancer. Radiotherapy and Oncology 55: 241–249. https: //doi.org/10.1016/S0167-8140(99)00100-0 |
| [9] | Börgers C (1999) The Radiation Therapy Planning Problem: 1–16, Springer New York, New York, NY, https://doi.org/10.1007/978-1-4612-1550-9_1 |
| [10] | De Ruysscher D, Sterpin E, Haustermans K, et al. (2015) Tumour movement in proton therapy: Solutions and remaining questions: A review. Cancers 7: 1143–1153. https://doi.org/10. 3390/cancers7030829 |
| [11] | Engelsman M, Schwarz M, Dong L (2013) Physics controversies in Proton Therapy. Seminars in Radiation Oncology 23: 88–96. https://doi.org/10.1016/j.semradonc.2012.11.003 |
| [12] | Grutters JP, Kessels AG, Pijls-Johannesma M, et al. (2010) Comparison of the effectiveness of radiotherapy with photons, protons and carbon-ions for non-small cell lung cancer: A meta-analysis. Radiotherapy and Oncology 95: 32–40. https://doi.org/10.1016/j.radonc.2009.08.003 |
| [13] | Kabarriti R, Mark D, Fox J, et al. (2015) Proton therapy for the treatment of pediatric head and neck cancers: A review. International Journal of Pediatric Otorhinolaryngology 79: 1995–2002. https://doi.org/10.1016/j.ijporl.2015.10.042 |
| [14] | Lee KA, O'Sullivan C, Daly P, et al. (2017) Proton therapy in paediatric oncology: an Irish perspective. Irish Journal of Medical Science 186: 577–582. https://doi.org/10.1007/ s11845-016-1520-9 |
| [15] | Mohan R, Grosshans D (2017) Proton therapy - present and future. Advanced Drug Delivery Reviews 109: 26–44. |
| [16] | Salama JK, Willett CG (2014) Is proton beam therapy better than standard radiation therapy? A paucity of practicality puts photons ahead of protons. Clinical advances in hematology and oncology 12: 861, 865–6, 869. http://europepmc.org/abstract/MED/25674847 |
| [17] | Schulz-Ertner D, Tsujii H (2007) Particle radiation therapy using proton and heavier ion beams. Journal of Clinical Oncology 25: 953–964. https://doi.org/10.1200/JCO.2006.09.7816 |
| [18] | Fellin F, Azzeroni R, Maggio A, et al. (2013) Helical tomotherapy and intensity modulated proton therapy in the treatment of dominant intraprostatic lesion: A treament planning comparison. Radiotherapy and Oncology 107: 207–212. https://doi.org/10.1016/j.radonc.2013.02. 016 |
| [19] | Fredriksson A (2013) Robust optimization of radiation therapy accounting for geometric uncertainty, PhD thesis. |
| [20] | Giap H, Roda D, Giap F (2015) Can proton beam therapy be clinically relevant for the management of lung cancer? Translational Cancer Research 4. https://doi.org/10.3978/j.issn. 2218-676X.2015.08.15 |
| [21] | Guta B (2003) Subgradient Optimization Methods in Integer Programming with an Application to a Radiation Therapy Problem, PhD thesis. http://nbn-resolving.de/urn/resolver.pl? urn:nbn:de:bsz:386-kluedo-16224 |
| [22] | McGowan SE, Burnet NG, Lomax AJ (2013) Treatment planning optimisation in proton therapy. The British Journal of Radiology 86: 20120288–20120288. https://doi.org/10.1259/bjr. 20120288 |
| [23] | Schwarz M (2011) Treatment planning in proton therapy. The European Physical Journal Plus 126: 67. https://doi.org/10.1140/epjp/i2011-11067-y |
| [24] | Schwarz M, Cattaneo GM, Marrazzo L (2017) Geometrical and dosimetrical uncertainties in hypofractionated radiotherapy of the lung: A review. Physica Medica 36: 126–139. https://doi.org/10.1016/j.ejmp.2017.02.011 |
| [25] | Schwarz M, Molinelli S (2016) What can particle therapy add to the treatment of prostate cancer?. Physica Medica 32: 485–491. https://doi.org/10.1016/j.ejmp.2016.03.017 |
| [26] | Alber M, Meedt G, N¨usslin F, et al. (2002) On the degeneracy of the IMRT optimization problem. Med Physics 29: 2584–2589. https://doi.org/10.1118/1.1500402 |
| [27] | Edimo P, Clermont C, Kwato M, et al. (2009) Evaluation of a commercial VMC++ Monte Carlo based treatment planning system for electron beams using EGSnrc/BEAMnrc simulations and measurements. Physica Medica: European Journal of Medical Physics 25: 111–121. https://doi.org/10.1016/j.ejmp.2008.07.001 |
| [28] | Li H, Liu W, Park P, et al. (2014) Evaluation of the systematic error in using 3d dose calculation in scanning beam proton therapy for lung cancer. Journal of Applied Clinical Medical Physics 15: 47–56. https://doi.org/10.1120/jacmp.v15i5.4810 29. Paganetti H (2012) Range uncertainties in proton therapy and the role of Monte Carlo simulations. Physics in Medicine and Biology 57: R99–R117 https://doi.org/10.1088/0031-9155/57/ 11/R99 |
| [29] | 30. Spirou SV, Chui CS (1998) A gradient inverse planning algorithm with dose-volume constraints. Medical Physics 25: 321–333. https://doi.org/10.1118/1.598202 |
| [30] | 31. Amichetti M (2016) The actual interest in radiotherapy for the utilization of proton beam, highlighting physics basis, technology and common clinical indications. J Tumor 4: 378–385. |
| [31] | 32. Brombal L, Barbosa D, Belcari N, et al. (2017) Proton therapy treatment monitoring with inbeam pet: investigating space and time activity distributions. Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment. https://doi.org/10.1016/j.nima.2017.05.002 |
| [32] | 33. Kiely JPB, White BM (2016) Robust proton pencil beam scanning treatment planning for rectal cancer radiation therapy. International Journal of Radiation Oncology*Biology*Physics 95: 208– 215. https://doi.org/10.1016/j.ijrobp.2016.02.037 |
| [33] | 34. Moignier A, Gelover E, Wang D, et al. (2016) Theoretical benefits of dynamic collimation in pencil beam scanning proton therapy for brain tumors: Dosimetric and radiobiological metrics. International Journal of Radiation Oncology*Biology*Physics 95: 171–180. https://doi.org/ 10.1016/j.ijrobp.2015.08.030 |
| [34] | 35. Scalco E, Schwarz M, Sutto M, et al. (2016) Evaluation of different ct lung anatomies for proton therapy with pencil beam scanning delivery, using a validated non-rigid image registration method. Acta Oncologica 55: 647–651. https://doi.org/10.3109/0284186X.2015.1105383 36. Schwarz M, Algranati C, Widesott L, et al. (2016) Clinical Pencil Beam Scanning: Present and Future Practices, Springer India, New Delhi, 95–110. https://doi.org/10.1007/ 978-81-322-2622-2_7 |
| [35] | 37. Cao W, Lim GJ, Lee A, et al. (2012) Uncertainty incorporated beam angle optimization for IMPT treatment planning. Medical Physics 39: 5248–5256. https://doi.org/10.1118/1.4737870 |
| [36] | 38. Fredriksson A, Forsgren A, Härdemark B (2011) Minimax optimization for handling range and setup uncertainties in proton therapy. Medical Physics 38: 1672–1684. https://doi.org/10. 1118/1.3556559 |
| [37] | 39. Li H, Zhu XR, Zhang X (2015) Reducing dose uncertainty for spot-scanning proton beam therapy of moving tumors by optimizing the spot delivery sequence. International Journal of Radiation Oncology*Biology*Physics 93: 547–556. https://doi.org/10.1016/j.ijrobp.2015.06. 019 |
| [38] | 40. Liu W, Frank SJ, Li X, et al. (2013) PTV-based IMPT optimization incorporating planning risk volumes vs robust optimization. Medical Physics 40: 021709. https://doi.org/10.1118/1. 4774363 |
| [39] | 41. Liu W, Li Y, Li X, et al. (2012) Influence of robust optimization in intensity-modulated proton therapy with different dose delivery techniques. Medical Physics 3089–3101. https://doi. org/10.1118/1.4711909 |
| [40] | 42. Liu W, Zhang X, Li Y, et al. (2012) Robust optimization of intensity modulated proton therapy. Medical Physics 39: 1079–1091. https://doi.org/10.1118/1.3679340 |
| [41] | 43. Alber M, Reemtsen R (2007) Intensity modulated radiotherapy treatment planning by use of a barrier-penalty multiplier method. Optimization Methods Software 22: 391–. https://doi. org/10.1080/10556780600604940 |
| [42] | 44. Dionisi F, Ben-Josef E (2014) The use of proton therapy in the treatment of gastrointestinal cancers: Liver. Cancer Journal 20: 371–377. |
| [43] | 45. Kessler ML, Mcshan DL, Epelman MA, et al. (2005) Costlets: A generalized approach to cost functions for automated optimization of IMRT treatment plans. Optimization and Engineering 6: 421–448. https://doi.org/10.1007/s11081-005-2066-2 |
| [44] | 46. Schwarz M, Pierelli A, Fiorino C, et al. (2011) Helical tomotherapy and intensity modulated proton therapy in the treatment of early stage prostate cancer: A treatment planning comparison. Radiotherapy and Oncology 98: 74–80. https://doi.org/10.1016/j.radonc.2010.10.027 |
| [45] | 47. Witte MG, van der Geer J, Schneider C, et al. IMRT optimization including random and systematic geometric errors based on the expectation of tcp and ntcp. Medical Physics,34: 3544–3555. https://doi.org/10.1118/1.2760027 |
| [46] | 48. Bokrantz R, Fredriksson A (2017) Necessary and su cient conditions for pareto e ciency in robust multiobjective optimization. European J Operational Res. https://doi.org/10.1016/ j.ejor.2017.04.012 |
| [47] | 49. Janssen F, Landry G, Lopes PC, et al. (2014) Factors influencing the accuracy of beam range estimation in proton therapy using prompt gamma emission. Physics in Medicine and Biology 59: 4427. https://doi.org/10.1088/0031-9155/59/15/4427 |
| [48] | 50. Cheung JP (2014) Image-Guided Proton Therapy for Online Dose-Evaluation and Adaptive Planning, PhD thesis. http://digitalcommons.library.tmc.edu/utgsbs_dissertations/439 |
| [49] | 51. Dionisi F, Avery S, Lukens JN, et al. (2014) Proton therapy in adjuvant treatment of gastric cancer: Planning comparison with advanced x-ray therapy and feasibility report. Acta Oncologica 53: 1312–1320. https://doi.org/10.3109/0284186X.2014.912351 |
| [50] | 52. Grant JD, Chang JY (2014) Proton-based stereotactic ablative radiotherapy in early-stage nonsmall-cell lung cancer. BioMed Research International |
| [51] | 53. Krämer M, Jäkel O, Haberer T, et al. (2000) Treatment planning for heavy-ion radiotherapy: physical beam model and dose optimization. Physics in Medicine and Biology 45: 3299. https: //doi.org/10.1088/0031-9155/45/11/313 54. Riboldi M, Baroni G (2015) Challenges and opportunities in image guided particle therapy, in: 37th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC), 5227–5230. |
| [52] | 55. Widesott L, Amichetti M, Schwarz M (2008) Proton therapy in lung cancer: Clinical outcomes and technical issues. A systematic review. Radiotherapy and Oncology 86: 154–164. https: //doi.org/10.10 6/j.radonc.2008.01.003 |
| [53] | 56. Widesott L, Lomax AJ, Schwarz M (2012) Is there a single spot size and grid for intensity modulated proton therapy? Simulation of head and neck, prostate and mesothelioma cases. Medical Physics 39: 1298–1308. https://doi.org/10.1118/1.3683640 |
| [54] | 57. Boland N, Hamacher HW, Lenzen F (2004) Minimizing beam-on time in cancer radiation treatment using multileaf collimators, Networks 43: 226–240, https://doi.org/10.1002/net. 20007 58. Cantone MC, Ciocca M, Dionisi F, et al. (2013) Application of failure mode and effects analysis to treatment planning in scanned proton beam radiotherapy. Radiation Oncology 8: 127. https: //doi.org/10.1186/1748-717X-8-127 |
| [55] | 59. Hoffmann L, Alber M, Jensen MF, et al. (2017) Adaptation is mandatory for intensity modulated proton therapy of advanced lung cancer to ensure target coverage. Radiotherapy and Oncology 122: 400–405. https://doi.org/10.1016/j.radonc.2016.12.018 |
| [56] | 60. Jäkel O, Hartmann GH, Karger CP, et al. (2000) Quality assurance for a treatment planning system in scanned ion beam therapy. Medical Physics 27: 1588–1600. https://doi.org/10.1118/1.599025 |
| [57] | 61. Lewis MW (2009) On the use of guided design search for discovering significant decision variables in the fixed-charge capacitated multicommodity network design problem. Networks 53: 6–18. https:/ doi.org/10.1002/net.20255 62. van de Schoot AJAJ, Visser J, van Kesteren Z, et al. (2016) Beam configuration selection for robust intensity-modulated proton therapy in cervical cancer using pareto front comparison. Physics in Medicine and Biology 61: 1780. https://doi.org/10.1088/0031-9155/61/4/1780 |
| [58] | 63. Baatar D, HamacherHW, Ehrgott M, et al. (2005) Decomposition of integer matrices and multileaf collimator sequencing. Discrete Applied Mathematics 152: 6–34, https://doi.org/10.1016/j.dam.2005.04.008 |
| [59] | 64. Ausiello G, Marchetti-Spaccamela A, Crescenzi P, et al. (1999) Complexity and Approximation, Springer Berlin Heidelberg, https://doi.org/10.1007/978-3-642-58412-1 |
| [60] | 65. Bovet DP, Crescenzi P (1994) Introduction to the Theory of Complexity, Prentice Hall International (UK) Ltd., Hertfordshire, UK, UK. |
| [61] | 66. Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NPCompleteness. W. H. Freeman. |
| [62] | 67. Felzenszwalb P, Huttenlocher D (2004) Effcient graph-based image segmentation. International Journal of Computer Vision 59: 167–181. https://doi.org/10.1023/B:VISI.0000022288. 19776.77 |
| [63] | 68. A compendium of NP optimization problems, 2005. Available from: https://www.nada.kth. se/~viggo/problemlist/compendium.html |
| [64] | 69. Alimonti P, Kann V (1997) Hardness of approximating problems on cubic graphs, in Proceedings of the Third Italian Conference on Algorithms and Complexity CIAC '97, Springer-Verlag, London, UK, UK, 1997, 288–298. https://doi.org/10.1007/3-540-62592-5_80 |
Figures(5)
Emma Altobelli, Maurizio Amichetti, Alessio Langiu, Francesca Marzi, Filippo Mignosi, Pietro Pisciotta, Giuseppe Placidi, Fabrizio Rossi, Giorgio Russo, Marco Schwarz, Stefano Smriglio, Sabina Vennarini. Combinatorial optimisation in radiotherapy treatment planning[J]. AIMS Medical Science, 2018, 5(3): 204-223. doi: 10.3934/medsci.2018.3.204
DownLoad: