Cambazard, H., O'Mahony, E., O'Sullivan, B.

Integration of {AI} and {OR} Techniques in Constraint Programming for Combinatorial Optimization Problems, 7th International Conference, CPAIOR 2010

Hybrid Methods for the Multileaf Collimator Sequencing Problem

2010

January

Published

0

Scopus: 8 ()

Andrea Lodi and Michela Milano and Paolo Toth

56

70

Bologna

14-JUN-10

18-JUN-10

The multileaf collimator sequencing problem is an important component of the effective delivery of intensity modulated radiotherapy used in the treatment of cancer. The problem can be formulated as finding a decomposition of an integer matrix into a weighted sequence of binary matrices whose rows satisfy a consecutive ones property. In this paper we extend the state-of-the-art optimisation methods for this problem, which are based on constraint programming and decomposition. Specifically, we propose two alternative hybrid methods: one based on Lagrangian relaxation and the other on column generation. Empirical evaluation on both random and clinical problem instances shows that these approaches can out-perform the state-of-the-art by an order of magnitude in terms of time. Larger problem instances than those within the capability of other approaches can also be solved with the methods proposed. © 2010 Springer-Verlag.

http://www.scopus.com/inward/record.url?eid=2-s2.0-77955455931&partnerID=40&md5=bd89e432aac01349ae185615d6f15de6

10.1007/978-3-642-13520-0_9