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.
