O metodo de geração de colunas aplicado a problemas de otimização em grafos / Column generation technique applied to graph optimization problems

AUTOR(ES)

Edna Ayako Hoshino

DATA DE PUBLICAÇÃO

2009

RESUMO

In this thesis, two combinatorial optimization problems are modeled by integer linear programming and solved using the column generation technique. Both cases correspond to generalizations of classical problems in graphs that occur in many practical situations. The first, called capacitated ring-star problem is a generalization of the vehicle routing problem and models real situations found in logistics and transportation. The second, known as the partition coloring problem, generalizes the vertex coloring problem in graphs and arises in design of fiber optics networks. The integer linear programming formulations developed in this work to model both problems are related to the Dantzing-Wolfe decomposition and use exponential number of decision variables. In these formulations, each decision variable represents a specific structure of the problem under study. For the capacitated ring-star problem, each variable is assigned to a ring-star and, for the partition coloring problem, to an independent set. The linear relaxation of this kind of model in general leads to tighter dual bounds than the ones obtained from compact models, i.e., defined over a polynomial number of variables. In this thesis, we evaluated both new formulations, comparing them to other known models for the respective problems. Moreover, in both cases, we designed and implemented exact branch-and-price and/or branch-and-cut-and-price algorithms that are able to solve the proposed models. Computational experiments were performed with these algorithms and showed that the used techniques were adequate. Both for the capacitated ring-star problem and for the partition coloring problem, we compared our results with those reported in the literature and showed that the algorithms based on column generation outperformed the previous ones

ASSUNTO(S)

graph theory vehicle routing problem combinatorial optimization problema de roteamento de veiculos teoria dos grafos integer programming otimização combinatoria programação inteira

Documentos Relacionados

• Geração de colunas para problemas de corte em duas fases
• TWO GRAPH OPTIMIZATION PROBLEMS: PIPELINE TRANSPORTATION AND SEARCHING WITH ACCESS COSTS
• Metodo da homogeneização aplicado a otimização estrutural topologica
• The discontinuous Galerkin method applied to convection-diffusion problems
• O MÉTODO HÍBRIDO DOS ELEMENTOS DE CONTORNO APLICADO A PROBLEMAS TRANSIENTES