Lagrangian-informed mixed integer programming reformulations

La programmation linéaire en nombres entiers est une approche robuste qui permet de résoudre rapidement de grandes instances de problèmes d'optimisation discrète. Toutefois, les problèmes gagnent constamment en complexité et imposent parfois de fortes limites sur le temps de calcul. Il devient alors nécessaire de développer des méthodes spécialisées afin de résoudre approximativement ces problèmes, tout en calculant des bornes sur leurs valeurs optimales afin de prouver la qualité des solutions obtenues. Nous proposons d'explorer une approche de reformulation en nombres entiers guidée par la relaxation lagrangienne. Après l'identification d'une forte relaxation lagrangienne, un processus systématique permet d'obtenir une seconde formulation en nombres entiers. Cette reformulation, plus compacte que celle de Dantzig et Wolfe, comporte exactement les mêmes solutions entières que la formulation initiale, mais en améliore la borne linéaire: elle devient égale à la borne lagrangienne. L'approche de reformulation permet d'unifier et de généraliser des formulations et des méthodes de borne connues. De plus, elle offre une manière simple d'obtenir des reformulations de moins grandes tailles en contrepartie de bornes plus faibles. Ces reformulations demeurent de grandes tailles. C'est pourquoi nous décrivons aussi des méthodes spécialisées pour en résoudre les relaxations linéaires. Finalement, nous appliquons l'approche de reformulation à deux problèmes de localisation. Cela nous mène à de nouvelles formulations pour ces problèmes; certaines sont de très grandes tailles, mais nos méthodes de résolution spécialisées les rendent pratiques.

Solution Methods for Service Network Design with Resource Management Consideration

La gestion des ressources, équipements, équipes de travail, et autres, devrait être prise en compte lors de la conception de tout plan réalisable pour le problème de conception de réseaux de services. Cependant, les travaux de recherche portant sur la gestion des ressources et la conception de réseaux de services restent limités. La présente thèse a pour objectif de combler cette lacune en faisant l’examen de problèmes de conception de réseaux de services prenant en compte la gestion des ressources. Pour ce faire, cette thèse se décline en trois études portant sur la conception de réseaux. La première étude considère le problème de capacitated multi-commodity fixed cost network design with design-balance constraints(DBCMND). La structure multi-produits avec capacité sur les arcs du DBCMND, de même que ses contraintes design-balance, font qu’il apparaît comme sous-problème dans de nombreux problèmes reliés à la conception de réseaux de services, d’où l’intérêt d’étudier le DBCMND dans le contexte de cette thèse. Nous proposons une nouvelle approche pour résoudre ce problème combinant la recherche tabou, la recomposition de chemin, et une procédure d’intensification de la recherche dans une région particulière de l’espace de solutions. Dans un premier temps la recherche tabou identifie de bonnes solutions réalisables. Ensuite la recomposition de chemin est utilisée pour augmenter le nombre de solutions réalisables. Les solutions trouvées par ces deux méta-heuristiques permettent d’identifier un sous-ensemble d’arcs qui ont de bonnes chances d’avoir un statut ouvert ou fermé dans une solution optimale. Le statut de ces arcs est alors fixé selon la valeur qui prédomine dans les solutions trouvées préalablement. Enfin, nous utilisons la puissance d’un solveur de programmation mixte en nombres entiers pour intensifier la recherche sur le problème restreint par le statut fixé ouvert/fermé de certains arcs. Les tests montrent que cette approche est capable de trouver de bonnes solutions aux problèmes de grandes tailles dans des temps raisonnables. Cette recherche est publiée dans la revue scientifique Journal of heuristics. La deuxième étude introduit la gestion des ressources au niveau de la conception de réseaux de services en prenant en compte explicitement le nombre fini de véhicules utilisés à chaque terminal pour le transport de produits. Une approche de solution faisant appel au slope-scaling, la génération de colonnes et des heuristiques basées sur une formulation en cycles est ainsi proposée. La génération de colonnes résout une relaxation linéaire du problème de conception de réseaux, générant des colonnes qui sont ensuite utilisées par le slope-scaling. Le slope-scaling résout une approximation linéaire du problème de conception de réseaux, d’où l’utilisation d’une heuristique pour convertir les solutions obtenues par le slope-scaling en solutions réalisables pour le problème original. L’algorithme se termine avec une procédure de perturbation qui améliore les solutions réalisables. Les tests montrent que l’algorithme proposé est capable de trouver de bonnes solutions au problème de conception de réseaux de services avec un nombre fixe des ressources à chaque terminal. Les résultats de cette recherche seront publiés dans la revue scientifique Transportation Science. La troisième étude élargie nos considérations sur la gestion des ressources en prenant en compte l’achat ou la location de nouvelles ressources de même que le repositionnement de ressources existantes. Nous faisons les hypothèses suivantes: une unité de ressource est nécessaire pour faire fonctionner un service, chaque ressource doit retourner à son terminal d’origine, il existe un nombre fixe de ressources à chaque terminal, et la longueur du circuit des ressources est limitée. Nous considérons les alternatives suivantes dans la gestion des ressources: 1) repositionnement de ressources entre les terminaux pour tenir compte des changements de la demande, 2) achat et/ou location de nouvelles ressources et leur distribution à différents terminaux, 3) externalisation de certains services. Nous présentons une formulation intégrée combinant les décisions reliées à la gestion des ressources avec les décisions reliées à la conception des réseaux de services. Nous présentons également une méthode de résolution matheuristique combinant le slope-scaling et la génération de colonnes. Nous discutons des performances de cette méthode de résolution, et nous faisons une analyse de l’impact de différentes décisions de gestion des ressources dans le contexte de la conception de réseaux de services. Cette étude sera présentée au XII International Symposium On Locational Decision, en conjonction avec XXI Meeting of EURO Working Group on Locational Analysis, Naples/Capri (Italy), 2014. En résumé, trois études différentes sont considérées dans la présente thèse. La première porte sur une nouvelle méthode de solution pour le "capacitated multi-commodity fixed cost network design with design-balance constraints". Nous y proposons une matheuristique comprenant la recherche tabou, la recomposition de chemin, et l’optimisation exacte. Dans la deuxième étude, nous présentons un nouveau modèle de conception de réseaux de services prenant en compte un nombre fini de ressources à chaque terminal. Nous y proposons une matheuristique avancée basée sur la formulation en cycles comprenant le slope-scaling, la génération de colonnes, des heuristiques et l’optimisation exacte. Enfin, nous étudions l’allocation des ressources dans la conception de réseaux de services en introduisant des formulations qui modèlent le repositionnement, l’acquisition et la location de ressources, et l’externalisation de certains services. À cet égard, un cadre de solution slope-scaling développé à partir d’une formulation en cycles est proposé. Ce dernier comporte la génération de colonnes et une heuristique. Les méthodes proposées dans ces trois études ont montré leur capacité à trouver de bonnes solutions.

Quantitative proteomics methods for the analysis of histone post-translational modifications

Les histones sont des protéines nucléaires hautement conservées chez les cellules des eucaryotes. Elles permettent d’organiser et de compacter l’ADN sous la forme de nucléosomes, ceux-ci representant les sous unités de base de la chromatine. Les histones peuvent être modifiées par de nombreuses modifications post-traductionnelles (PTMs) telles que l’acétylation, la méthylation et la phosphorylation. Ces modifications jouent un rôle essentiel dans la réplication de l’ADN, la transcription et l’assemblage de la chromatine. L’abondance de ces modifications peut varier de facon significative lors du developpement des maladies incluant plusieurs types de cancer. Par exemple, la perte totale de la triméthylation sur H4K20 ainsi que l’acétylation sur H4K16 sont des marqueurs tumoraux spécifiques a certains types de cancer chez l’humain. Par conséquent, l’étude de ces modifications et des événements determinant la dynamique des leurs changements d’abondance sont des atouts importants pour mieux comprendre les fonctions cellulaires et moléculaires lors du développement de la maladie. De manière générale, les modifications des histones sont étudiées par des approches biochimiques telles que les immuno-buvardage de type Western ou les méthodes d’immunoprécipitation de la chromatine (ChIP). Cependant, ces approches présentent plusieurs inconvénients telles que le manque de spécificité ou la disponibilité des anticorps, leur coût ou encore la difficulté de les produire et de les valider. Au cours des dernières décennies, la spectrométrie de masse (MS) s’est avérée être une méthode performante pour la caractérisation et la quantification des modifications d’histones. La MS offre de nombreux avantages par rapport aux techniques traditionnelles. Entre autre, elle permet d’effectuer des analyses reproductibles, spécifiques et facilite l’etude d’un large spectre de PTMs en une seule analyse. Dans cette thèse, nous présenterons le développement et l’application de nouveaux outils analytiques pour l’identification et à la quantification des PTMs modifiant les histones. Dans un premier temps, une méthode a été développée pour mesurer les changements d’acétylation spécifiques à certains sites des histones. Cette méthode combine l’analyse des histones intactes et les méthodes de séquençage peptidique afin de déterminer les changements d’acétylation suite à la réaction in vitro par l’histone acétyltransférase (HAT) de levure Rtt109 en présence de ses chaperonnes (Asf1 ou Vps75). Dans un second temps, nous avons développé une méthode d’analyse des peptides isomériques des histones. Cette méthode combine la LC-MS/MS à haute résolution et un nouvel outil informatique appelé Iso-PeptidAce qui permet de déconvoluer les spectres mixtes de peptides isomériques. Nous avons évalué Iso-PeptidAce avec un mélange de peptides synthétiques isomériques. Nous avons également validé les performances de cette approche avec des histones isolées de cellules humaines érythroleucémiques (K562) traitées avec des inhibiteurs d’histones désacétylases (HDACi) utilisés en clinique, et des histones de Saccharomyces cerevisiae liées au facteur d’assemblage de la chromatine (CAF-1) purifiées par chromatographie d’affinité. Enfin, en utilisant la méthode présentée précédemment, nous avons fait une analyse approfondie de la spécificité de plusieurs HATs et HDACs chez Schizosaccharomyces pombe. Nous avons donc déterminé les niveaux d’acétylation d’histones purifiées à partir de cellules contrôles ou de souches mutantes auxquelles il manque une HAT ou HDAC. Notre analyse nous a permis de valider plusieurs cibles connues des HATs et HDACs et d’en identifier de nouvelles. Nos données ont également permis de définir le rôle des différentes HATs et HDACs dans le maintien de l’équilibre d’acétylation des histones. Dans l’ensemble, nous anticipons que les méthodes décrites dans cette thèse permettront de résoudre certains défis rencontrés dans l’étude de la chromatine. De plus, ces données apportent de nouvelles connaissances pour l’élaboration d’études génétiques et biochimiques utilisant S. pombe.

Virtual reality rehabilitation as a treatment approach for older women with mixed urinary incontinence : a feasibility study

Background Motivated patients are more likely to adhere to treatment resulting in better outcomes. Virtual reality rehabilitation (VRR) is a treatment approach that includes video gaming to enhance motivation and functional training. Aims The study objectives were (1) to evaluate the feasibility of using a combination of pelvic floor muscles (PFM) exercises and VRR (PFM/VRR) to treat mixed urinary incontinence (MUI) in older women, (2) to evaluate the effectiveness of the PFM/VRR program on MUI symptoms, quality of life (QoL), and (3) gather quantitative information regarding patient satisfaction with this new combined training program. Methods Women 65 years and older with at least 2 weekly episodes of MUI were recruited. Participants were evaluated two times before and one time after a 12-week PFM/VRR training program. Feasibility was defined as the participants' rate of participation in and completion of both the PFM/VRR training program and the home exercise. Effectiveness was evaluated through a bladder diary, pad test, symptom and QoL questionnaire, and participant's satisfaction through a questionnaire. Results Twenty-four women (70.5 ± 3.6 years) participated. The participants complied with the study demands in terms of attendance at the weekly treatment sessions (91%), adherence to home exercise (92%) and completion of the three evaluations (96%). Post-intervention, the frequency and quantity of urine leakage decreased and patientreported symptoms and QoL improved significantly. Most participants were very satisfied with treatment (91%). Conclusion A combined PFM/VRR program is an acceptable, efficient, and satisfying functional treatment for older women with MUI and should be explore through further RCTs.

Differences in pelvic floor morphology between continent, stress urinary incontinent, and mixed urinary incontinent elderly women : an MRI study

Aims To compare magnetic resonance imaging (MRI) of the pelvic floor musculature (PFM), bladder neck and urethral sphincter morphology under three conditions (rest, PFM maximal voluntary contraction (MVC), and straining) in older women with symptoms of stress (SUI) or mixed urinary incontinence (MUI) or without incontinence. Methods This 2008–2012 exploratory observational cohort study was conducted with community-dwelling women aged 60 and over. Sixty six women (22 per group), mean age of 67.7 ± 5.2 years, participated in the study. A 3 T MRI examination was conducted under three conditions: rest, PFM MVC, and straining. ANOVA or Kruskal–Wallis tests (data not normally distributed) were conducted, with Bonferroni correction, to compare anatomical measurements between groups. Results Women with MUI symptoms had a lower PFM resting position (M-Line P = 0.010 and PC/H-line angle P = 0.026) and lower pelvic organ support (urethrovesical junction height P = 0.013) than both continent and SUI women. Women with SUI symptoms were more likely to exhibit bladder neck funneling and a larger posterior urethrovesical angle at rest than both continent and MUI women (P = 0.026 and P = 0.008, respectively). There were no significant differences between groups on PFM MVC or straining. Conclusions Women with SUI and MUI symptoms present different morphological defects at rest. These observations emphasize the need to tailor UI interventions to specific pelvic floor defects and UI type in older women.