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.

The exploration of mixed-use principle as an ingredient to improve the viability and vitality of town centres in Mauritius

This thesis has been realised through a scholarship offered by the Government of Canada to the Government of the Republic of Mauritius under the Programme Canadien de Bourses de la Francophonie

Lutte intégrée au roseau commun : prévention, confinement et éradication

Les plantes envahissantes menacent la biodiversité ainsi que les activités humaines. Afin de les maîtriser, la pulvérisation d'herbicides est une méthode fréquemment employée en Amérique du Nord. Cette approche ne fait pas toujours consensus et est même parfois interdite ou restreinte, ce qui justifie le recours à d'autres options. Les alternatives peuvent toutefois s'avérer rares, comporter d'importantes limitations ou sont peu documentées. Cette étude vise à tester l’efficacité de méthodes permettant de maîtriser et de prévenir les invasions de roseau commun (Phragmites australis), l'une des plantes envahissantes les plus problématiques sur le continent nord-américain, tout en limitant au minimum l'utilisation d'herbicides. Le potentiel de quatre méthodes de lutte aux petites populations de roseau bien établies a d'abord été évalué : l’excavation avec enfouissement sur place, le bâchage, l’excavation avec enfouissement sur place combinée au bâchage, et la fauche répétée. Les résultats ont montré que l'excavation avec enfouissement sur place, avec ou sans bâchage, a entraîné une élimination presque totale des populations visées, ce qui est comparable ou supérieur à l'effet généralement obtenu avec la pulvérisation d'herbicide. Le bâchage avec des toiles opaques, maintenues pendant un an, a pour sa part entraîné une maîtrise partielle du roseau, suggérant qu'une application prolongée serait nécessaire pour l'éradication de la plante. La fauche répétée, exécutée à raison de cinq fauches par été pendant deux ans, a fourni une efficacité mitigée. Les résultats suggèrent néanmoins que la fauche pendant plusieurs années contribue à affaiblir la plante, ce qui pourrait aider à son confinement. Une méthode additionnelle a été expérimentée afin de traiter les tiges éparses de roseau tout en limitant les risques d'effets hors cibles, soit le badigeonnage manuel d’herbicide. Suite à ces tests, les résultats ont montré une diminution importante de la densité des tiges, ce qui suggère que la méthode est efficace afin d'éliminer les repousses après un traitement initial, et pourrait également être employée sur de jeunes populations clairsemées. L'effet d'un ensemencement préventif de plantes herbacées sur l'établissement de semis de roseau a également été étudié, suite à des traitements sur de vastes parcelles de sol nu. Les résultats suggèrent que la méthode est efficace afin de limiter la propagation du roseau par semences et qu'un suivi périodique suite à l'intervention serait suffisant afin de maintenir l'effet préventif.