The segmentation problem arises in the elaboration of a radiation therapy plan. After the cancer has been diagnosed and the radiation therapy sessions have been prescribed, the physician has to locate the tumor as well as the organs situated in the radiation field, called the organs at risk. The physician also has to determine the different dosage he wants to deliver in each of them and has to define a lower bound on the dosage for the tumor (which represents the minimum amount of radiation that is needed to have a sufficient control of the tumor) and an upper bound for each organ at risk (which represents the maximum amount of radiation that an organ can receive without damaging). Designing a radiation therapy plan that respects these different bounds of dosage is a complex optimization problem that is usually tackled in three steps. The segmentation problem is one of them. Mathematically, the segmentation problem amounts to decomposing a given nonnegative integer matrix A into a nonnegative integer linear combination of some binary matrices. These matrices have to respect the consecutive ones property. In clinical applications several constraints may arise that reduce the set of binary matrices which respect the consecutive ones property that we can use. We study some of them, as the interleaf distance constraint, the interleaf motion constraint, the tongue-and-groove constraint and the minimum separation constraint. We consider here different versions of the segmentation problem with different objective functions. Hence we deal with the beam-on time problem in order to minimize the total time during which the patient is irradiated. We study this problem under the interleaf distance and the interleaf motion constraints. We consider as well this last problem under the tongue-and-groove constraint in the binary case. We also take into account the cardinality and the lex-min problem. Finally, we present some results for the approximation problem. /Le problème de segmentation intervient lors de l'élaboration d'un plan de radiothérapie. Après que le médecin ait localisé la tumeur ainsi que les organes se situant à proximité de celle-ci, il doit aussi déterminer les différents dosages qui devront être délivrés. Il détermine alors une borne inférieure sur le dosage que doit recevoir la tumeur afin d'en avoir un contrôle satisfaisant, et des bornes supérieures sur les dosages des différents organes situés dans le champ. Afin de respecter au mieux ces bornes, le plan de radiothérapie doit être préparé de manière minutieuse. Nous nous intéressons à l'une des étapes à réaliser lors de la détermination de ce plan: l'étape de segmentation. Mathématiquement, cette étape consiste à décomposer une matrice entière et positive donnée en une combinaison positive entière linéaire de certaines matrices binaires. Ces matrices binaires doivent satisfaire la contrainte des uns consécutifs (cette contrainte impose que les uns de ces matrices soient regroupés en un seul bloc sur chaque ligne). Dans les applications cliniques, certaines contraintes supplémentaires peuvent restreindre l'ensemble des matrices binaires ayant les uns consécutifs (matrices 1C) que l'on peut utiliser. Nous en avons étudié certaines d'entre elles comme celle de la contrainte de chariots, la contrainte d'interdiciton de chevauchements, la contrainte tongue-and-groove et la contrainte de séparation minimum. Le premier problème auquel nous nous intéressons est de trouver une décomposition de la matrice donnée qui minimise la somme des coefficients des matrices binaires. Nous avons développé des algorithmes polynomiaux qui résolvent ce problème sous la contrainte de chariots et/ou la contrainte d'interdiction de chevauchements. De plus, nous avons pu déterminer que, si la matrice donnée est une matrice binaire, on peut trouver en temps polynomial une telle décomposition sous la contrainte tongue-and-groove. Afin de diminuer le temps de la séance de radiothérapie, il peut être désirable de minimiser le nombre de matrices 1C utilisées dans la décomposition (en ayant pris soin de préalablement minimiser la somme des coefficients ou non). Nous faisons une étude de ce problème dans différents cas particuliers (la matrice donnée n'est constituée que d'une colonne, ou d'une ligne, ou la plus grande entrée de celle-ci est bornée par une constante). Nous présentons de nouvelles bornes inférieures sur le nombre de matrices 1C ainsi que de nouvelles heuristiques. Finalement, nous terminons par étudier le cas où l'ensemble des matrices 1C ne nous permet pas de décomposer exactement la matrice donnée. Le but est alors de touver une matrice décomposable qui soit aussi proche que possible de la matrice donnée. Après avoir examiné certains cas polynomiaux nous prouvons que le cas général est difficile à approximer avec une erreur additive de O(mn) où m et n représentent les dimensions de la matrice donnée.

The segmentation problem arises in the elaboration of a radiation therapy plan. After the cancer has been diagnosed and the radiation therapy sessions have been prescribed, the physician has to locate the tumor as well as the organs situated in the radiation field, called the organs at risk. The physician also has to determine the different dosage he wants to deliver in each of them and has to define a lower bound on the dosage for the tumor (which represents the minimum amount of radiation that is needed to have a sufficient control of the tumor) and an upper bound for each organ at risk (which represents the maximum amount of radiation that an organ can receive without damaging). Designing a radiation therapy plan that respects these different bounds of dosage is a complex optimization problem that is usually tackled in three steps. The segmentation problem is one of them.<p><p>Mathematically, the segmentation problem amounts to decomposing a given nonnegative integer matrix A into a nonnegative integer linear combination of some binary matrices. These matrices have to respect the consecutive ones property. In clinical applications several constraints may arise that reduce the set of binary matrices which respect the consecutive ones property that we can use. We study some of them, as the interleaf distance constraint, the interleaf motion constraint, the tongue-and-groove constraint and the minimum separation constraint.<p><p>We consider here different versions of the segmentation problem with different objective functions. Hence we deal with the beam-on time problem in order to minimize the total time during which the patient is irradiated. We study this problem under the interleaf distance and the interleaf motion constraints. We consider as well this last problem under the tongue-and-groove constraint in the binary case. We also take into account the cardinality and the lex-min problem. Finally, we present some results for the approximation problem. <p><p>/Le problème de segmentation intervient lors de l'élaboration d'un plan de radiothérapie. Après que le médecin ait localisé la tumeur ainsi que les organes se situant à proximité de celle-ci, il doit aussi déterminer les différents dosages qui devront être délivrés. Il détermine alors une borne inférieure sur le dosage que doit recevoir la tumeur afin d'en avoir un contrôle satisfaisant, et des bornes supérieures sur les dosages des différents organes situés dans le champ. Afin de respecter au mieux ces bornes, le plan de radiothérapie doit être préparé de manière minutieuse. Nous nous intéressons à l'une des étapes à réaliser lors de la détermination de ce plan: l'étape de segmentation.<p><p>Mathématiquement, cette étape consiste à décomposer une matrice entière et positive donnée en une combinaison positive entière linéaire de certaines matrices binaires. Ces matrices binaires doivent satisfaire la contrainte des uns consécutifs (cette contrainte impose que les uns de ces matrices soient regroupés en un seul bloc sur chaque ligne). Dans les applications cliniques, certaines contraintes supplémentaires peuvent restreindre l'ensemble des matrices binaires ayant les uns consécutifs (matrices 1C) que l'on peut utiliser. Nous en avons étudié certaines d'entre elles comme celle de la contrainte de chariots, la contrainte d'interdiciton de chevauchements, la contrainte tongue-and-groove et la contrainte de séparation minimum.<p><p>Le premier problème auquel nous nous intéressons est de trouver une décomposition de la matrice donnée qui minimise la somme des coefficients des matrices binaires. Nous avons développé des algorithmes polynomiaux qui résolvent ce problème sous la contrainte de chariots et/ou la contrainte d'interdiction de chevauchements. De plus, nous avons pu déterminer que, si la matrice donnée est une matrice binaire, on peut trouver en temps polynomial une telle décomposition sous la contrainte tongue-and-groove.<p><p>Afin de diminuer le temps de la séance de radiothérapie, il peut être désirable de minimiser le nombre de matrices 1C utilisées dans la décomposition (en ayant pris soin de préalablement minimiser la somme des coefficients ou non). Nous faisons une étude de ce problème dans différents cas particuliers (la matrice donnée n'est constituée que d'une colonne, ou d'une ligne, ou la plus grande entrée de celle-ci est bornée par une constante). Nous présentons de nouvelles bornes inférieures sur le nombre de matrices 1C ainsi que de nouvelles heuristiques.<p><p>Finalement, nous terminons par étudier le cas où l'ensemble des matrices 1C ne nous permet pas de décomposer exactement la matrice donnée. Le but est alors de touver une matrice décomposable qui soit aussi proche que possible de la matrice donnée. Après avoir examiné certains cas polynomiaux nous prouvons que le cas général est difficile à approximer avec une erreur additive de O(mn) où m et n représentent les dimensions de la matrice donnée. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished