A new mathematical model for intensity matrix decomposition using multileaf collimator

Document Type: Research Paper


Department of Industrial Engineering, Iran University of Science and Technology, Narmak, Tehran, Iran


Cancer is one of the major causes of death all over the globe and radiotherapy is considered one of its most effective treatment methods. Designing a radiotherapy treatment plan was done entirely manually in the past. RecentlyIntensity Modulated Radiation Therapy (IMRT) was introduced as a new technology with advanced medical equipmentin the recent years. IMRT provides the opportunity to deliver complex dose distributions to cancer cells while sparing the vital tissues and cells from the harmful effects of the radiations. Designing an IMRT treatment plan is a very complex matter due to the numerous calculations and parameters which must be decided for. Such treatment plan is designed in three separate phases: 1) selecting the number and the angle of the beams 2) extracting the intensity matrix or the corresponding dose map of each beam and 3) realizing each intensity matrix. The third phase has been studied in this research and a nonlinear mathematical model has been proposed for multileaf collimators. The proposed model has been linearized through two methods and an algorithm has been developed on its basis in order to solve the model with cardinality objective function. Obtained results are then compared with similar studies in the literature which reveals the capability of proposed method.


Main Subjects

Ahuja, R. K. and Hamacher, H. W., (2005), A network flow algorithm to minimize beam‐on time for
unconstrained multileaf collimator problems in cancer radiation therapy,. Networks, 45, 36-41.
Baatar, D., Boland, N., Brand, S. and Stuckey, P. J., (2007), Minimum cardinality matrix decomposition
into consecutive-ones matrices: CP and IP approaches, Integration of AI and OR Techniques in
Constraint Programming for Combinatorial Optimization Problems. Springer.
Baatar, D., Hamacher, H. W., Ehrgott, M. & Woeginger, G. J.,( 2005), Decomposition of integer matrices
and multileaf collimator sequencing., Discrete Applied Mathematics, 152, 6-34.
Bai, L. & Rubin, P. A.,(2009), Combinatorial benders cuts for the minimum tollbooth problem,
Operations Research, 57, 1510-1522.
Benders, J. F., (2005), Partitioning procedures for solving mixed-variables programming problems,
Computational Management Science, 2, 3-19.
Boland, N., Hamacher, H. W. & Lenzen, F., (2004), Minimizing beam‐on time in cancer radiation
treatment using multileaf collimators, Networks, 43, 226-240.
Cambrazard, H., O’mahony, E. & O’Sullivan, B.,(2010), Hybrid methods for the multileaf collimator
sequencing problem, Integration of AI and OR Techniques in Constraint Programming for Combinatorial
Optimization Problems. Springer.
Cambazard, H., O’mahony, E. & O’Sullivan, B.,( 2012), A shortest path-based approach to the multileaf
collimator sequencing problem., Discrete Applied Mathematics, 160, 81-99.
Collins, M. J., Kempe, D., Saia, J. & Young, M.,( 2007), Nonnegative integral subset representations of
integer sets, Information Processing Letters, 101, 129-133.

Ehrgott, M., Guller, Ç., Hamacher, H. W. & Shao, L., (2008), Mathematical optimization in intensity
modulated radiation therapy. 4OR, 6, 199-262.
Engel, K.,(2005), A new algorithm for optimal multileaf collimator field segmentation, Discrete Applied
Mathematics, 152, 35-51.
Ernst, A. T., Mak, V. H. & Mason, L. R., (2009), An exact method for the minimum cardinality problem
in the treatment planning of intensity-modulated radiotherapy,. INFORMS Journal on Computing, 21,
Gleeson, J. & Ryan, J., (1990), Identifying minimally infeasible subsystems of inequalities,. ORSA
Journal on Computing, 2, 61-63.
Kalinowski, T.,(2009), The complexity of minimizing the number of shape matrices subject to minimal
beam-on time in multileaf collimator field decomposition with bounded fluence, Discrete Applied
Mathematics, 157, 2089-2104.
Mak, V., (2007), Iterative variable aggregation and disaggregation in IP: An application, Operations
research letters, 35, 36-44.
Mason, L. R., Mak-Hau, V. H. & Ernst, A. T., (2012), An exact method for minimizing the total
treatment time in intensity-modulated radiotherapy, Journal of the Operational Research Society, 63,
Meyer, J. L., Verhey, L., Pia, L. & Wong, J., (2006), IMRT· IGRT· SBRT.
Pishvaee, M. S., Razmi, J. & Torabi, S. A., (2014), An accelerated Benders decomposition algorithm for
sustainable supply chain network design under uncertainty: A case study of medical needle and syringe
supply chain, Transportation Research Part E: Logistics and Transportation Review, 67, 14-38.
Schlegel, W. & Mahr, A., (2007), 3D conformal radiation therapy: Multimedia introduction to methods
and techniques, Springer Publishing Company, Incorporated.
Siochi, R. A. C., (1999), Minimizing static intensity modulation delivery time using an intensity solid
paradigm, International Journal of Radiation Oncology* Biology* Physics, 43, 671-680.
Taskin, Z. C. & Cevik, M.,(2013), Combinatorial Benders cuts for decomposing IMRT fluence maps
using rectangular apertures, Computers & Operations Research, 40, 2178-2186.
Taskin, Z. C., Smith, J. C. & Romeijn, H. E., (2012), Mixed-integer programming techniques for
decomposing IMRT fluence maps using rectangular apertures,. Annals of Operations Research, 196, 799-
Taskin, Z. C., Smith, J. C., Romeijn, H. E. & Dempsey, J. F.,(2010), Optimal multileaf collimator leaf
sequencing in IMRT treatment planning, Operations Research, 58, 674-690.