Mixed integer programming (MIP) provides an important modeling and decision support tool for a wide variety of real-life problems. Unfortunately, practical MIPs are large-scale in size and pose serious difficulties to the available solution methodology and software.

This thesis presents a novel solution approach for large-scale mixed integer programming that integrates three bodies of research:​ interior point methods, decomposition techniques and branch-and-bound approaches. The combination of decomposition concepts and branch-and-bound is commonly known as branch-and-price, while the integration of decomposition concepts and interior point methods lead to the analytic centre cutting plane method (ACCPM). Unfortunately, the use of interior point methods within branch-and-bound methods could not compete with simplex based branch-and-bound due to the inabilityof "warm" starting.

The motivation for this study stems from the success of branch-and-price and ACCPM in solving integer and non-differentiable optimization problems respectively and the quest for a method that efliciently integrates interior-point methods and branch-and-bound.

The proposed approach is called an Interior Point Branch-and-Price method (IP-B&P) and works as follows. First, a problem's structure is exploited using Lagrangean relaxation. Second, the resulting master problem is solved using ACCPM. Finally, the overall approach is incorporated within a branch-andbound scheme. The resulting method is more than the combination of three different techniques. It addresses and fixes complications that arise as a result of this integration. This includes the restarting of the interior-point methods, the branching rule and the exploitation of past information as a warm start.

In the first part ofthe thesis, we gjve the details of the interior-point branchand-priee method. We start by providing, discussing and implementing new ideas within ACCPM, then detail the IP-B&P method and its different components. To show the practical applicability of IP-B&P, we use the method as a basis for a new solution methodology for the production-distribution system design (PDSD) problem in supply chain management. In this second part of the thesis, we describe a two-level Lagrangean relaxation heuristic for the PDSD. The numerical results show the superiority of the method in providing the optimal solution for most of the problems attempted.

Cette thèse présente une nouvelle approche de resolution pour la programmation en nombre entier de grande taille. L'approche intègre trois corps de recherche:​ méthodes de points interieurs, techniques de décomposition et méthodes d'évaluation et de separation progressive (branch-and-bound). La combinaison des concepts de décomposition et de branch-and-bound est généralement connue sous le nom "branch-and-price", alors que l'intégration des concepts de décomposition et les méthodes de points intérieures mènent à la méthode du centre analytique (ACCPM). Malheureusement, l'utilisation des méthodes de points intérieures dans les approches de branch-and-bound n'a pas pu rivaliser avec les approches de branch-and-bound basées sur le simplex. La raison est due à la difficulté associée avec l'initialisation de la méthode de points interieurs.

La motivation pour cette étude provient du succès du branch-and-price et de l'ACCPM en résolvant des problèmes en nombres entiers et d'optimisation non-différentiable respectivement, et la recherche d'une méthode efficace qui intègre les méthodes de points interieurs et les methodes de branch-and-bound.

L'approche proposée s'appelle une méthode de branch-and-price basée sur les points intérieurs (Interior Point Branch-and-Price method:​ IP-B&P). D'abord, la structure d'un problème est exploitée en utilisant la relaxation Lagrangéenne. Puis, le dual Lagrangéen est résolu avec l'ACCPM. Enfin, l'approche globale est incorporée dans une procedure d'évaluation et de separation progressive. La méthode résultante est plus que la combinaison de trois techniques différentes. Elle mène a des complications qui résultent en raison de cette intégration. Ceci inclut l'initialisation des méthodes de points intérieurs, la règle de branchement et l'utilisation d'information déjà genérée comme un "warm start" .

Dans la première partie de la thèse, nous décrivons en détail la méthode IP-B&P. Nous commençons par discuter et implenter de nouvelles idées dans ACCPM, puis nous détaillons la méthode IP-B&P et ses différents composants. Pour montrer l'applicabilité pratique de la méthode IP-B&P, nous l'utilisons dans une nouvelle méthodologie de resolution pour le problème de la conception de systèmes de production-distribution (PDSD) dans la gestion des chaines d'approvisionnements. Nous proposons une relaxation lagrangéenne à deux niveaux pour le PDSD. Les résultats numériques montrent la supériorité de la méthode en trouvant la solution optimale pour la plupart des problèmes essayées.