Uma maneira de resolver problemas de programação linear de grande escala é explorar a relaxação lagrangeana das restrições \"difíceis\'\' e utilizar métodos de subgradientes. Populares por fornecerem rapidamente boas aproximações de soluções duais, eles não produzem diretamente as soluções primais. Para obtê-las com custo computacional adequado, pode-se construir seqüências ergódicas ou utilizar uma técnica proposta recentemente, denominada algoritmo do volume. As propriedades teóricas de convergência não foram bem estabelecidas nesse algoritmo, mas pequenas modificações permitem a demonstração da convergência dual. Destacam-se como adaptações o algoritmo do volume revisado, um método de feixes específico, e o algoritmo do volume incorporado ao método de variação do alvo. Este trabalho foi baseado no estudo desses algoritmos e de todos os conceitos envolvidos, em especial, análise convexa e otimização não diferenciável. Estudamos as principais diferenças teóricas desses métodos e realizamos comparações numéricas com problemas lineares e lineares inteiros, em particular, o corte máximo em grafos. / One way to solve large-scale linear programming problems is to exploit the Lagrangian relaxation of the difficult constraints and use subgradient methods. Such methods are popular as they give good approximations of dual solutions. Unfortunately, they do not directly yield primal solutions. Two alternatives to obtain primal solutions under reasonable computational cost are the construction of ergodic sequences and the use of the recently developed volume algorithm. While the convergence of ergodic sequences is well understood, the convergence properties of the volume algorithm is not well established in the original paper. This lead to some modifications of the original method to ease the proof of dual convergence. Three alternatives are the revised volume algorithm, a special case of the bundle method, and the volume algorithm incorporated by the variable target value method. The aim of this work is to study such algorithms and all related concepts, especially convex analysis and nondifferentiable optimization. We analysed the main theoretical differences among the methods and performed numerical experiments with linear and integer problems, in particular, the maximum cut problem on graphs.

Les problèmes que nous considérons dans cette thèse sont de nature combinatoire. Notre principal intérêt est le problème de restructuration de données semi-structurées. Par exemple des données stockées sous la forme d’un fichier XML sont des données semi-structurées. Ce problème peut être ramené à une instance du problème du p-médian. Le principal obstacle ici est la taille des instances qui peut devenir très grande. Certaines instances peuvent avoir jusqu’à 10000 ou 20000 sommets, ce qui implique plusieurs centaines de millions de variables. Pour ces instances, résoudre ne serait-ce que la relaxation linéaire du problème est très difficile. Lors d’expériences préliminaires nous nous sommes rendu compte que CPLEX peut résoudre des instances avec 1000 sommets dans des temps raisonnables. Mais pour des instances de 5000 sommets, il peut prendre jusqu’à 14 jours pour résoudre uniquement la relaxation linéaire. Pour ces raisons nous ne pouvons utiliser de méthodes qui considère la résolution de la relaxation linéaire comme une opération de base, comme par exemple les méthodes de coupes et de branchements. Au lieu d’utiliser CPLEX nous utilisons une implémentation parallèle (utilisant 32 processeurs) de l’algorithme du Volume. L’instance pour laquelle CPLEX demande 14 heures est résolue en 24 minutes par l’implémentation séquentielle et en 10 minutes par l’implémentation parallèle de l’algorithme du Volume. La solution de la relaxation linéaire est utilisée pour construire une solution réalisable, grâce à l’application d’une heuristique de construction gloutonne puis d’une recherche locale. Nous obtenons des résultats comparables aux résultats obtenus par les meilleures heuristiques connues à ce jour, qui utilisent beaucoup plus de mémoire et réalisent beaucoup plus d’opérations. La mémoire est importante dans notre cas, puisque nous travaillons sur des données de très grandes tailles. Nous étudions le dominant du polytope associé au problème du p-médian. Nous discutons de sa relaxation linéaire ainsi que de sa caractérisation polyédrale. Enfin, nous considérons une version plus réaliste du problème de restructuration de données semi-structurées. Grosso modo, nous ajoutons au problème du p-médian original des nouveaux sommets s’ils aident à réduire le coût global des affectations. / The problems we consider in this thesis are of combinatorial nature. Our main interest is the problem of approximating typing of a semistructured data. For example XML is a semistructured data. This problem may be reduced to an instance of the p-median problem. The main obstacle here is the size of the instances that may be very huge, about 10000 and 20000 nodes which imply several hundreds of million variables. For these instances, even solving the linear relaxation is a hard task. In some preliminary results we noticed that Cplex may solve instances of size 1000 in an acceptable time. But for some instances having 5000 nodes, it may needs 14 days for solving only the linear relaxation. Therefore, we cannot use methods that consider the linear relaxation as an elementary operation, as for example branch-and-cut methods. Instead of using Cplex we use the Volume algorithm in a parallel implementation (32 processors).For the instance where the Cplex needs 14 hours, the Volume algorithm in sequential implementation needs 24 minutes and in parallel implementation it needs 10 minutes. The solution of the linear relaxation is used to produce a feasible solution by first applying a greedy and then a local search heuristic. We notice that the results we obtain are relatively the same as those given by the best method known up today, which produces more effort and consumes more memory. Memory is important in our case since the data we consider are huge. We study the dominant of the polytope associated with the p-median problem. We discuss linear relaxation and a polyhedral characterization. Finally, we consider a more realistic version of the p-median problem when applied to the problem of approximating typing of a semistructured data. Roughly speaking, we add new nodes to the underlying graph if this help to reduce the overall cost.

Uma maneira de resolver problemas de programação linear de grande escala é explorar a relaxação lagrangeana das restrições \"difíceis\'\' e utilizar métodos de subgradientes. Populares por fornecerem rapidamente boas aproximações de soluções duais, eles não produzem diretamente as soluções primais. Para obtê-las com custo computacional adequado, pode-se construir seqüências ergódicas ou utilizar uma técnica proposta recentemente, denominada algoritmo do volume. As propriedades teóricas de convergência não foram bem estabelecidas nesse algoritmo, mas pequenas modificações permitem a demonstração da convergência dual. Destacam-se como adaptações o algoritmo do volume revisado, um método de feixes específico, e o algoritmo do volume incorporado ao método de variação do alvo. Este trabalho foi baseado no estudo desses algoritmos e de todos os conceitos envolvidos, em especial, análise convexa e otimização não diferenciável. Estudamos as principais diferenças teóricas desses métodos e realizamos comparações numéricas com problemas lineares e lineares inteiros, em particular, o corte máximo em grafos. / One way to solve large-scale linear programming problems is to exploit the Lagrangian relaxation of the difficult constraints and use subgradient methods. Such methods are popular as they give good approximations of dual solutions. Unfortunately, they do not directly yield primal solutions. Two alternatives to obtain primal solutions under reasonable computational cost are the construction of ergodic sequences and the use of the recently developed volume algorithm. While the convergence of ergodic sequences is well understood, the convergence properties of the volume algorithm is not well established in the original paper. This lead to some modifications of the original method to ease the proof of dual convergence. Three alternatives are the revised volume algorithm, a special case of the bundle method, and the volume algorithm incorporated by the variable target value method. The aim of this work is to study such algorithms and all related concepts, especially convex analysis and nondifferentiable optimization. We analysed the main theoretical differences among the methods and performed numerical experiments with linear and integer problems, in particular, the maximum cut problem on graphs.