Optimization Online


On linear infeasibility arising in intensity-modulated radiation therapy inverse planning

Yair Censor (yair***at***math.haifa.ac.il)
Adi Ben-Israel (adi.benisrael***at***gmail.com)
Ying Xiao (ying.xiao***at***jeffersonhospital.org)
James M. Galvin (James.Galvin***at***jeffersonhospital.org)

Abstract: Intensity--modulated radiation therapy (IMRT) gives rise to systems of linear inequalities, representing the effects of radiation on the irradiated body. These systems are often infeasible, in which case one settles for an approximate solution, such as an {a,}--relaxation, meaning that no more than a percent of the inequalities are violated by no more than percent. For real-world IMRT problems, there is a feasible {a,}--relaxation for sufficiently large a,>0, however large values of these parameters may be unacceptable medically. The {a,}--relaxation problem is combinatorial, and for given values of the parameters can be solved exactly by Mixed Integer Programming (MIP), but this may be impractical because of problem size, and the need for repeated solutions as the treatment progresses. As a practical alternative to the MIP approach we present a heuristic non-combinatorial method for finding an approximate relaxation. The method solves a Linear Program (LP) for each pair of values of the parameters {a,} and progresses through successively increasing values until an acceptable solution is found, or is determined non-existent. The method is fast and reliable, since it consists of solving a sequence of LP's.

Keywords: Infeasibility, linear systems, alpha-beta relaxation, intensity-modulated radiation therapy, IMRT, mixed integer programming.

Category 1: Applications -- Science and Engineering

Category 2: Combinatorial Optimization (Approximation Algorithms )

Citation: Linear Algebra and its Applications, vol. 428 (2008), pp. 1406-1420.


Entry Submitted: 11/05/2007
Entry Accepted: 11/05/2007
Entry Last Modified: 04/17/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society