Mixed Integer Programming for Radiotherapy Optimization

在美国，每年大约有120万新的癌症病例，其中大约一半接受放射治疗。外照射治疗将来自患者身体外的高能射束引导至肿瘤。使用广泛使用的适形放射治疗方法，射线以多个角度定位，每个角度的形状都与肿瘤相匹配。最新的技术，调强放射治疗(IMRT)，将整个射束分解成更细小的射束，实际上，每个射束都可以被分配一个单独的强度。放射治疗计划的问题是选择一组射束/射束，并为它们分配强度，以将肿瘤剂量推高到附近健康组织允许的最高水平。即使是符合耐受性限制的肿瘤剂量的微小增量，每年也可以改善数千人的生命。这项研究的目标是开发适合放射治疗的计算方法，该方法可以在可用于治疗计划的24-48小时内计算出指定百分比的最佳可行计划。为了确定剂量的体积分布，肿瘤学家通常将组织结构的不规则几何形状建模为大量嵌入的离散点的联合。假设传输到一个点的剂量可以近似为射束强度的线性，治疗计划优化的任务可以被建模为具有对应于这些强度的变量的混合整数规划(MIP)，以及限制每个组织点处的剂量的约束。剂量-体积约束要求每个正常器官体积的特定部分接受低于其损伤阈值的剂量，通过收集多项选择组中每个组织的点约束来实施，并用二元变量描述备选方案。研究将开发和测试通用MIP方法的两个贡献，以便能够为放射治疗计划问题找到计算高效的解决方案。其目的是提供满足规定约束且目标值位于最优附近的可证明范围内的解决方案。其中第一个将通过构造和添加新的有效的不等式来加强多项选择(剂量-体积)约束的MIP公式的LP松弛。第二个将采用列生成方法来处理海量调强放射治疗公式。代替对调强放射治疗波束内每个波束的强度进行建模，整个波束强度图案将被表示为单个列并根据需要生成。

0120145LangerThere are approximately 1.2 million new cases of cancer each year in the US and about half undergo treatment with radiation therapy. External beam treatment directs a collection of high energy beams from outside the patient's body towards the tumor. Using the widespread method of conformal radiotherapy, beams are positioned at multiple angles, each shaped to match the tumor. The newest technique, intensity modulated radiotherapy (IMRT), breaks down whole beams into finer beamlets, each of which can, in effect, be assigned a separate intensity. The radiation therapy planning problem is to choose a set of beams/beamlets and assign intensities to them to push tumor dose as high as the tolerances of nearby healthy tissue will allow. Even small increments in tumor dose consistent with tolerance constraints can improve thousands of lives per year. The objective of the proposed research is to develop computational methods tailored to radiation therapy that can compute feasible plans provably within a specified percent of the best possible within the 24-48 hours available for treatment planning.To determine volume distributions of dose, oncologists typically model the irregular geometry of tissue structures as the union of a large number of embedded discrete points. Given that the dose delivered to a point can be approximated as linear in the beam intensities, the task of treatment planning optimization can be modeled as mixed-integer program (MIP) with variables corresponding to those intensities, and constraints limiting the dose at each of the tissue points. Dose-volume constraints, which require a specified fraction of each normal organ volume receive a dose below its threshold for damage, are enforced by collecting point constraints for each tissue in a multiple-choice group with alternatives delineated with binary variables.The research will develop and test two contributions to generic MIP methodology in order to enable computationally efficient solutions to be be found for the radiotherapy planning problem. The aim is to provide solutions that satisfy prescribed constraints with an objective value that lies within a provable bound around the optimum. The first of these will strengthen LP relaxations of MIP formulations for the multiple-choice (dose--volume) constraints by constructing and adding new valid inequalities. The second will adapt a column-generation approach to deal with the massive IMRT formulations. Instead of modeling the intensity of each beamlet within an IMRT beam, whole patterns of beamlet intensities will be represented as single columns and generated as required.