Treatment planning for brachytherapy: an integer programming model, two computational approaches and experiments with permanent prostate implant planning.

An integer linear programming model is proposed as a framework for optimizing seed placement and dose distribution in brachytherapy treatment planning. The basic model involves using 0/1 indicator variables to describe the placement or non-placement of seeds in a prespecified three-dimensional grid of potential locations. The dose delivered to each point in a discretized representation of the diseased organ and neighbouring healthy tissue can then be modelled as a linear combination of the indicator variables. A system of linear constraints is imposed to attempt to keep the dose level at each point to within specified target bounds. Since it is physically impossible to satisfy all constraints simultaneously, each constraint uses a variable to either record when the target dose level is achieved, or to record the deviation from the desired level. These additional variables are embedded into an objective function to be optimized. Variations on this model are discussed and two computational approaches--a branch-and-bound algorithm and a genetic algorithm--for finding 'optimal' seed placements are described. Results of computational experiments on a collection of prostate cancer cases are reported. The results indicate that both optimization algorithms are capable of producing good solutions within 5 to 15 min, and that small variations in model parameters can have a measurable effect on the dose distribution of the resulting plans.