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.

Dynamic Facility Location with Modular Capacities : Models, Algorithms and Applications in Forestry

Les décisions de localisation sont souvent soumises à des aspects dynamiques comme des changements dans la demande des clients. Pour y répondre, la solution consiste à considérer une flexibilité accrue concernant l’emplacement et la capacité des installations. Même lorsque la demande est prévisible, trouver le planning optimal pour le déploiement et l'ajustement dynamique des capacités reste un défi. Dans cette thèse, nous nous concentrons sur des problèmes de localisation avec périodes multiples, et permettant l'ajustement dynamique des capacités, en particulier ceux avec des structures de coûts complexes. Nous étudions ces problèmes sous différents points de vue de recherche opérationnelle, en présentant et en comparant plusieurs modèles de programmation linéaire en nombres entiers (PLNE), l'évaluation de leur utilisation dans la pratique et en développant des algorithmes de résolution efficaces. Cette thèse est divisée en quatre parties. Tout d’abord, nous présentons le contexte industriel à l’origine de nos travaux: une compagnie forestière qui a besoin de localiser des campements pour accueillir les travailleurs forestiers. Nous présentons un modèle PLNE permettant la construction de nouveaux campements, l’extension, le déplacement et la fermeture temporaire partielle des campements existants. Ce modèle utilise des contraintes de capacité particulières, ainsi qu’une structure de coût à économie d’échelle sur plusieurs niveaux. L'utilité du modèle est évaluée par deux études de cas. La deuxième partie introduit le problème dynamique de localisation avec des capacités modulaires généralisées. Le modèle généralise plusieurs problèmes dynamiques de localisation et fournit de meilleures bornes de la relaxation linéaire que leurs formulations spécialisées. Le modèle peut résoudre des problèmes de localisation où les coûts pour les changements de capacité sont définis pour toutes les paires de niveaux de capacité, comme c'est le cas dans le problème industriel mentionnée ci-dessus. Il est appliqué à trois cas particuliers: l'expansion et la réduction des capacités, la fermeture temporaire des installations, et la combinaison des deux. Nous démontrons des relations de dominance entre notre formulation et les modèles existants pour les cas particuliers. Des expériences de calcul sur un grand nombre d’instances générées aléatoirement jusqu’à 100 installations et 1000 clients, montrent que notre modèle peut obtenir des solutions optimales plus rapidement que les formulations spécialisées existantes. Compte tenu de la complexité des modèles précédents pour les grandes instances, la troisième partie de la thèse propose des heuristiques lagrangiennes. Basées sur les méthodes du sous-gradient et des faisceaux, elles trouvent des solutions de bonne qualité même pour les instances de grande taille comportant jusqu’à 250 installations et 1000 clients. Nous améliorons ensuite la qualité de la solution obtenue en résolvent un modèle PLNE restreint qui tire parti des informations recueillies lors de la résolution du dual lagrangien. Les résultats des calculs montrent que les heuristiques donnent rapidement des solutions de bonne qualité, même pour les instances où les solveurs génériques ne trouvent pas de solutions réalisables. Finalement, nous adaptons les heuristiques précédentes pour résoudre le problème industriel. Deux relaxations différentes sont proposées et comparées. Des extensions des concepts précédents sont présentées afin d'assurer une résolution fiable en un temps raisonnable.

Studying Your Own Country. Social Scientific Knowledge For Our Times and Places; Presidential Address to the Canadian Political Science Association, St Catharines, May 28, 2014

Political science is both a generalizing and an anchored, nationally defined, discipline. Too often, the first perspective tends to crowd out the latter, because it appears more prestigious, objective, or scientific. Behind the international/national dichotomy, there are indeed rival conceptions of social science, and important ontological, epistemological and methodological assumptions. This article discusses these assumptions and stresses the critical contribution of idiographic, single-outcome studies, the importance of producing relevant, usable knowledge, and the distinctive implications of studying one’s own country, where a scholar is also a citizen, involved in more encompassing national conversations. The aim is not to reject the generalizing, international perspective, or even the comparative approach, but rather to reaffirm the importance of maintaining as well, and in fact celebrating, the production of social scientific knowledge directly relevant for our own times and places.

Asia-Pacific: a new agenda for the times ahead

The rapid growth of the populous Asian economies provokes profound economic changes and a shift in the balance of power. On the economic front, Asian leaders are confronted with the need to preserve the stability that has underpinned their prosperity, maintain an environment conducive to trade and investments and encourage domestic consumption while avoiding ecological disasters. Internationally, business competition will intensify with the strong presence of Asian manufacturers in global supply chains, growing price competition from Asian firms in domestic markets and global competition for energy, food, minerals and other commodities. Geopolitical concerns stem, in part, from Asia’s global quest for critical resources, conflicting territorial and maritime disputes and increasing military expenditures which affect security dynamics. China’s assertiveness over its periphery prompts an arm’s race in the region and concerns about Sino-American relations even though U.S.-Chinese relations may be less risky than China’s relations with its neighbours. The United States remains a key player in the Asia-Pacific region, with the capacity to alter balances and affect outcomes. Globally, the United States capacity to lead is now diminished and will continue to be so for the foreseeable future. Since no rising power is capable of exercising global leadership, a return to the "old normal" where no one power in geopolitical or economic terms dominates the world is to be expected.

Voir la guerre venir : la Première Guerre mondiale vue par The New York Times (1914-1917).

Lorsque la guerre européenne éclate en août 1914, les États-Unis adoptent officiellement une position de stricte neutralité. Le pays n’en est pas moins tiraillé de l’intérieur pour autant. Au cours des quelque deux années et demi de neutralité, plusieurs moments forts et thématiques ont redéfini le rapport des États-Unis à la guerre européenne, jusqu’à justifier l’entrée en guerre en avril 1917, et propulsant par le fait même le pays à l’avant de la scène internationale. Cependant, les analyses relatives à la couverture de la guerre par la presse américaine pendant cette période sont pratiquement inexistantes. En se penchant sur les articles en une et les éditoriaux du quotidien The New York Times, il est possible de suivre l’évolution des thématiques liées au conflit et de comparer certains évènements que l’historiographie a ciblés comme étant à l’origine de l’entrée en guerre. Le but est de voir comment le NYT présente le conflit européen, de quelles façons le journal cherche à influencer son lectorat et, surtout, comment il « voit » peu à peu le conflit s’immiscer dans la vie des Américains. Certains thèmes comme le mouvement du preparedness et le traitement de la communauté germano-américaine nous renseignent sur les changements de perception qui s’opèrent dans la couverture du NYT. L’historiographie classique présente le torpillage du paquebot Lusitania le 7 mai 1915 comme le point à l’origine de la rupture officieuse de la neutralité américaine, au profit d’un sentiment proallié. Notre analyse tend à nuancer fortement cette affirmation. D’autres moments-clés et thématiques présentées dans le NYT ont eu plus d’impact sur la neutralité américaine. Nos résultats de recherche questionnent en fait la nature et la temporalité de la « neutralité » américaine. Est-ce réellement, comme le souhaitait au départ le président américain Wilson une « neutralité bienveillante », ou de la poudre aux yeux?