A parallel optimisation approach for the realisation problem in intensity modulated radiotherapy treatment planning

作     者：Mason, Luke R. Mak-Hau, Vicky H. Ernst, Andreas T. 

作者机构：Biarri Windsor Vic 3181 Australia Deakin Univ Sch Informat Technol Burwood Vic 3125 Australia CSIRO Math Informat & Stat Clayton Vic 3169 Australia 

出 版 物：《COMPUTATIONAL OPTIMIZATION AND APPLICATIONS》 (计算优化及其应用)

年 卷 期：2015年第60卷第2期

页      面：441-477页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：Deakin University Postgraduate Research Scholarships Deakin University's CRGS Grant 

主　　题：IMRT Combinatorial optimization Constraint programming Parallel programming 

摘      要：We propose a parallel algorithm for computing exact solutions to the problem of minimizing the number of multileaf collimator apertures needed in step-and-shoot intensity modulated radiotherapy. These problems are very challenging particularly as the problem size increases. Here, we investigate how advanced parallel computing methods can be applied to these problems with a focus on the issues that are peculiar to parallel search algorithms and do not arise in their serial counterparts. A previous paper by the authors presented the MU-RD method for solving such problems using a serial constraint programming based search method. This method is being used as the starting point for a parallel implementation. The key challenges in creating a parallel implementation are ensuring that the CPUs are not starved of work and avoiding unnecessary computation due to the rearrangement of the search order in the parallel version. We show that efficient parallel optimisation is possible by dynamically changing the way work is split with potentially multiple tree search processes as well as parallel search of nodes. A weakly sorted queueing system is used to ensure appropriate prioritisation of tasks. Numerical results are presented to demonstrate the effectiveness of our algorithms in scaling from 8 to 64 CPUs.