Integer programming is a powerful modeling tool for a variety of decision making problems such as in telecommunications network design and in routing and scheduling. Integer programming models of realistic problems are large in size and pose serious challenge to available software. This creates an urgent need for solution methodologies that can deal with their size and complexity. In this thesis, we focus on the theoretieal development, implementation and testing of a novel methodology:​ an interior-point branch-and-price algorithm with cut generation for large scale integer programming.

The methodology applies to any integer program but is built for a general class of integer programming that has a large, possibly exponential set of constraints. It starts by applying a decomposition method to the complicating constraints. We focus on Lagrangian relaxation or Dantzig-Wolfe decomposition;​ both lead to a master problem with an exponential number of variables and constraints. The same analysis applies when one starts by relaxing the exponential constraints and then applying a decomposition method. In both cases, one has to solve iteratively a master problem that is updated by appending violated cuts and columns. For that, we propose a cut and column generation algorithm based on analytie centers.

The cut and column generation algorithm solves a restricted master problem using a primaI. analytic center cutting plane method to obtain a bound on the original problem. The bound may be poor in quality since most of the complicating constraints are relaxed. To strengthen the bound, we generate violated constraints and append them to the master problem. At this point we use available information to warm-start the solution of the updated restrieted master problem. This is done using a dual Newton method to calculate the next analytic center, after whieh we proceed with the primal method.

The bound is then embedded within a branch-and-bound algorithm leading to a branch-and-price algorithm. In fact, the algorithm is more than a branchand-priee since it is able to deal with valid cuts added at the level of the master problem. This is a major step towards an interior-point branch-andcut-and-price algorithm. For an efficient integration of the cut and column generation algorithm within branch-and-bound, we use available information from a parent node to warm-start the calculation of the bound at child nodes. This is achieved by a dual Newton method.

We use the interior-point branch-and-price algorithm with cut generation to solve the capacitated minimum spanning tree problem on directed and undirected graphs. The problem is characterized by an exponential number of cut-capacity constraints. These are relaxed in a Lagrangian fashion. To generate capacity cuts, we propose a procedure that strengthens the cuts by lifting them. This improved the lower bound significantly. The proposed algorithm outperformed the literature in terms of the problem size solved, the quality of the lower bound and the size of the search tree both on directed and undirected instances with general demand. We also tested the algorithm on benchmark undirected instances with unit demand from the literature. Even though the quality of the bound was not as good as the literature, there is much room for improvement in future research.

The proposed method is a general tool that is suit able for problems with an exponential number of constraints such as the subtour elimination constraints in traveling salesman problems or the cut-capacity constraints in vehicle routing problems. It is also applicable to any general integer pro gram that is modeled using a large set of valid inequalities.

La programmation en nombre entier est un outil de modélisation puissant et largement utilisé dans les problèmes d'aide à la décision tels que les réseaux de télécommunications, l'ordonnancement et le routage de véhicules. Néanmoins, les logiciels et les algorithmes disponibles sont souvent confrontés à des problèmes concrets fortement contraints et se traduisant en des programmes en nombre entier de grande taille. Pour relever ce défi, il est primordial d'élaborer de nouvelles méthodes de résolution performantes et proposant des solutions de bonnes qualités en un temps raisonnable. Cette thèse propose une méthode nouvelle basée sur un algorithme de "branch-and-price" avec génération de coupes pour la résolution de programmes en nombre entier de grande taille. Un développement théorique de l'algorithme proposé a été validé par une phase d'implémentation et de tests donnant lieu à de très bon résultas.

On considère une classe générale de programmes en nombre entier avec un nombre exponentiel de contraintes. Ces programmes en nombre entier modélisant des applications concrêtes ont l'avantage d'être bien formulés et structurés. C'est en exploitant judicieusement cette propriété qu'il est possible de développer des méthodes exactes efficaces pour des problèmes concrets de taille raisonnable.

L'approche proposée est une méthode itérative qui commence par une relaxation des contraintes exponentielles suivie par une méthode de décomposition tels que la relaxation lagrangienne, la décomposition lagrangienne ou la décomposition de Dantzig-Wolfe et menant à un problème maître avec un nombre exponentiels de variables et de contraintes. Pour le résoudre, nous proposons un algorithme de génération de colonnes et de coupes basé sur le centre analytique. Ce dernier résout un problème maître restreint en utilisant une méthode de centre analytique primale pour aboutir à une borne du problème original. Mais, vu que la majorité des contraintes difficiles sont relâchées, la borne obtenue n'est pas de bonne qualité. La borne est ainsi améliorée en ajoutant des colonnes correspondant aux contraintes violées au problème plus élargi. Après quoi, on utilise une méthode de point-intèrieur duale pour calculer le centre analytique.

La borne est intégrée dans un algorithme de séparation et évaluation progressive "branch-and-bound" menant à un algorithme de "branch-and-price" avec generation de coupes. Ceci est une étape primordiale vers un algorithme de "branch-and-cut-and-price" avec point intérieur. Pour une intégration efficace de l'algorithme de génération de coupes et de colonnes avec l'algorithme de branch-and-bound, on utilise l'information disponible d'un nud parent pour calculer les bornes des nuds fils après branchement.

Nous avons appliqué cette nouvelle méthode pour résoudre le problème d'arbre de recouvrement minimal avec capacité. Le sous-problème obtenu par relaxation est un arbre de recouvrement minimal avec contrainte de degré. pour le résoudre, Nous utilisons un algorithme de génération de coupes et de colonnes, où les colonnes ajoutés correspondent aux contraintes de capacité violées. Ceci améliore de façon significative les bornes inférieures.

Les résultats numériques sont encourageants par comparaison à ceux de la littérature. En effet, l'algorithme améliore les résultats du point de vue qualité des bornes inférieures, tailles des problèmes résolus et taille de l'arbre d'énumiration (espace de recherche). Néanmoins, la qualité bornes obtenues sur des instances non orientées de la littérature est moins bonne, ce qui fait l'objet d'un des perspectives de ces travaux.