Exact methods for solving covering problems with trees subject to capacity constraints

Dans ce document, nous étudions deux problèmes de sectorisation et proposons plusieurs méthodes de résolution exactes basées sur la décomposition de Dantzig-Wolfe et la génération de colonnes. Nous proposons deux modélisations en fonction de la manière d’appréhender l’objectif du problème qui consiste à obtenir des secteurs compacts. Pour chacune des modélisations, nous comparons des approches de résolution exactes basées sur des formulations compactes ou sur des formulations étendues obtenues par la décomposition de Dantzig-Wolfe. Le premier type de modèles proposé définit la fonction objectif à la manière d’un problème de p-median. Concernant les méthodes de résolution pour ce type de modèle, l’accent est mis sur l’accélération de la convergence de l’algorithme de génération de colonnes en mettant en place des techniques d’agrégation de contraintes afin de réduire la dégénérescence de l’algorithme du simplexe. Les expérimentations numériques montrent que la méthode d’agrégation de contraintes proposée permet effectivement de réduire le nombre d’itérations dégénérées. Cependant, elle ne suffit pas à accélérer l’algorithme de branch-and-price. Le choix d’utilisation de la formulation compacte ou de la formulation étendue dépend du type d’instances résolu. Le second type de modèles formule l’objectif d’une manière assez proche de celui des problèmes de p-centre. L’utilisation d’un tel objectif complexifie la résolution des sous-problèmes de génération de colonnes. L’accent est donc mis sur la conception d’algorithmes de branch-and-bound et de programmation dynamique pour les résoudre efficacement. Les expériences montrent que l’algorithme de branch-and-price surpasse les approches de résolution utilisant une formulation compacte du problème.In this document, we study two districting problems and propose several exact methods, based on Dantzig-Wolfe decomposition and column generation, to solve them. For each model, we compare exact approaches based either on compact formulations or on extended formulations obtained using Dantzig-Wolfe decomposition. The first type of model that we propose defines the objective function in a p-median problem fashion. Regarding the methods used to solve that kind of model, we emphasize accelerating the convergence of the column generation algorithm by designing constraint aggregation techniques in order to reduce the degeneracy in the simplex algorithm. Numerical experiments show that this constraint aggregation method indeed reduces the proportion of degenerated iterations. However, it is not enough to speed up the branch-and-price algorithm. Choosing to tackle the problem through either a compact formulation or an extended formulation depends on the structure of the instances to solve. The second type of model formulates the objective function in a way quite similar to that of p-centre problems. Using such an objective function induces complex column generation subproblems. We focus on designing branch-and-bound and dynamic programming algorithms in order to solve them efficiently. Experiments show that the branch-and-price approach surpasses any proposed method based on compact formulations of the problem