Relaxação langrangena com divisão em clusters para alguns problemas de otimização modelados em grafos de conflitos / Lagrangean relaxation with clusters for some optimization problems modeled by conflict graphs

AUTOR(ES)

Glaydston Mattos Ribeiro

DATA DE PUBLICAÇÃO

2007

RESUMO

Several combinatorial optimization problems can be modeled by a special graph denoted conflict graph. When these graphs are sparses well-adapted for a previous clustering phase, i.e, when they have clusters of vertices, the edges inter clusters can be relaxed in a lagrangean fashion, and the relaxed problem can be decomposed into sub problems and solved. This is the idea of the lagrangean relaxation with clusters (LagClus). The sub problems have similar structure of the original problem. Therefore the dual bounds are better than the traditional lagrangean relaxation over all edges of the conflict graph. This is the main advantage of the LagClus. We successful applied the LagClus over different problems present in the literature: Point-Feature Cartographic Label Placement Problem (PFCLP), Manufacturers Pallet Loading Problem (MPLP), Woodpulp Stowage Problem (WSP) and Daily Photograph Scheduling Problem of an Earth Observation Satellite (DPSPEO). The decomposition of the conflict graph allows us to model the problem using the Dantzig-Wolfe decomposition, where the Restricted Master Problem (RMP) is defined by coupling constraints (all edges connecting the clusters) and the sub problem by the clusters obtained in the partitioning phase. Computational results show the equivalence between LagClus and this decomposition. This work also presents new mathematical formulations for three problems: PFCLP, WSP and DPSPEO. All these formulation are based on cutting theory. Computational tests, mainly for DPSPEO, show that when we insert interesting cuts generating new formulations, the optimal solutions can be found very quickly.

ASSUNTO(S)

relaxação lagrangeana com clusters algoritmo de geração de colunas cutting theory column generation algorithm lagrangean relaxation lagrangean relaxations with clusters relaxação lagrangeana computer science teoria de cortes

Documentos Relacionados

• Relaxação langrangena com divisão em clusters para alguns problemas de otimização modelados em grafos de conflitos
• Relaxações e método de decomposição para alguns problemas de localização de facilidades modelados em grafos
• Relaxações e método de decomposição para alguns problemas de localização de facilidades modelados em grafos
• Relaxações e método de decomposição para alguns problemas de localização de facilidades modelados em grafos
• Algoritmos para problemas de grafos com incertezas