Optimal decomposition of IMRT fluence maps using combinatorial benders cuts

Abstract

The main aim of this thesis is to determine optimal decomposition of Intensity Modulated Radiation Therapy (IMRT) uence maps using rectangular apertures. A uence map can be represented as an integer matrix, which denotes the intensity pro le to be delivered to a patient through a given beam angle. IMRT treatment machinery considered in this case can form rectangular apertures using conventional jaws, and hence, do not need sophisticated multi-leaf collimator (MLC) devices. The number of apertures used to deliver the uence map needs to be minimized in order to treat the patient e ciently. From a mathematical point of view, the problem is equivalent to a minimum cardinality matrix decomposition problem. A combinatorial Benders decomposition approach is proposed in this thesis to solve this problem to optimality. First, mixed integer programming formulation of the problem is presented. After that, a customized version of the combinatorial Benders decomposition for this rectangular decomposition problem is introduced. There are several model improvements that increase e ciency of this algorithm. For this aim, several valid inequalities, heuristics to nd initial feasible solutions, algorithms to improve solutions found and single branch-and-bound tree approach are discussed. In the nal part of the thesis, the ef- cacy of the combinatorial Benders decomposition approach is demonstrated on a set of test instances derived from actual clinical data. Besides, results obtained by using this approach are compared with the ones from the literature and solutions obtained by solving a mixed-integer programming formulation of the model.