Multiple Objective Linear Programming in Radiotherapy Treatment Planning
The aim of intensity modulated radiation therapy (IMRT) is to kill tumor cells while
at the same time protecting the surrounding tissue and organs from the damaging
effect of radiation. To achieve these goals computerized inverse planning systems
are used. Given the number of beams and beam directions, beam intensity profiles
that yield the best dose distribution under consideration of clinical and physical
constraints are calculated. This is called beam intensity optimization problem.
In this thesis, we first review existing mathematical models and computation
methods for the beam intensity optimization problem. Next, we formulate the beam
intensity optimization problem as a multiobjective linear programme (MOLP) with
three objectives. For clinical cases this optimization problem involves thousands of
variables and tens of thousands of constraints and existing methods such as multiobjective
simplex methods can not handle it. The rest of the thesis is dedicated to
developing methods to solve this large MOLP efficiently and to the application in
the beam intensity optimization problem.
Benson (1998c) argues that solving an MOLP in objective space needs less computation
time than solving it in decision space if the number of objectives of the
MOLP is much smaller than the number of variables. Moreover, the constraint
matrix of the problem relies on the calculation of dose deposited in tissue. Since
this calculation is always imprecise solving the MOLP exactly is not necessary in
practice. This motivates us to develop algorithms for solving an MOLP in objective
We summarize Benson’s outer approximation algorithm for solving MOLPs in
objective space and propose some small changes to improve computational performance. Then in order to approximate the true nondominated set we propose
a modification of Benson’s algorithm which is called an approximation version of
Benson’s algorithm. Our approximation algorithm computes an inner and an outer
approximation of the nondominated set. We prove that the inner approximation
provides a set of ?-nondominated points.
The geometric duality theory of Heyde and L¨ohne (2006) defines a dual to an
MOLP and it assures us to be able to find the nondominated set of the primal MOLP
by solving its dual MOLP. Based on this we develop a dual variant of Benson’s outer
approximation algorithm to solve the dual MOLP in objective space. We prove
that solving the dual provides a weight set decomposition. We compare the primal
algorithm and the dual algorithm on small illustrative and on radiotherapy examples.
Furthermore, we propose an algorithm to solve the dual MOLP approximately but
within specified tolerance. This approximate solution set can be used to calculate an
approximation of the nondominated set of the primal MOLP.We show that this set is
an ?-nondominated set of the original primal MOLP and provide numerical evidence
that this approach can be faster than solving the primal MOLP approximately.
Considering that the set of nondominated points is infinite, it is not very useful
from the planners’ point of view. We address the problem of finding well distributed
nondominated points for an MOLP.We propose a method which combines the global
shooting and normal boundary intersection methods. By doing so, we overcome the
limitation of normal boundary intersection method that parts of the nondominated
set may be missed. Discrepancy analysis of the nondominated points from a geometry
point of view shows that this method produces evenly distributed nondominated
points. Moreover, the coverage error and the uniformity level can be measured.
Finally, we apply the algorithms developed to the beam intensity optimization
problem of 3D clinical cases with voxel size of 5mm and 3mm. A technique of
reducing the resolution in normal tissue has been used to reduce the computation
time. The results clearly illustrate the advantages of our methods.