Please use this identifier to cite or link to this item:
http://bibdigital.epn.edu.ec/handle/15000/19635
Title: | Métodos exactos para el problema de k-particionamiento con restricciones de tamaño y peso |
Authors: | Arias Navarrete, Yohandra Rubi Escobar Ortiz, Ana Julia |
Keywords: | INVESTIGACIÓN OPERATIVA ALGORITMO BRANCH & CUT PROGRAMACIÓN |
Issue Date: | 3-Aug-2018 |
Publisher: | Quito, 2018. |
Citation: | Arias Navarrete, Y. R., & Escobar Ortiz, A. J. (2018). Métodos exactos para el problema de k-particionamiento con restricciones de tamaño y peso. 98 hojas. Quito : EPN. |
Abstract: | Let G := (V, E) be a undirected graph with edge costs and node weigths. The partition problem over G is defined as finding a partition of V in a fixed number of subsets of nodes (or cliques), such that the sum of the cost of the edges with both ending nodes in the same subset is minimized. In this work an integer lineal programing model for the k− partition problem with size and weight restrictions is formulated, and this model is compared to the model proposed in Recalde et al. [2016]. For the two linear formulations, a Branch & Cut method will be used as an exact solving method. Furthermore, different types of cutting plane, such as triangular inequialities, 2-partition and cover planes will be included. Finally, computational results based upon both real and simulated instances are presented |
Description: | Sea G:= (V, E) un grafo no dirigido con función de costos sobre las aristas y pesos sobre los nodos. El problema de particionamiento sobre G, consiste en dividir a V en subconjuntos o cliques con el fin de minimizar la suma de los costos de las aristas que conectan los nodos de cada subconjunto. En el presente trabajo se formulará un modelo de programación lineal entera para el problema de k−particionamiento con restricciones de tamaño y peso, que será comparado con el modelo propuesto por Recalde et al. [2016]. Para las dos formulaciones lineales se usará un algoritmo tipo Branch & Cut como método exacto de solución, en los que se incluirán diferentes clases de planos cortantes como las desigualdades triangulares, 2-partición y de cubrimiento conocidas como cover. Finalmente, resultados computacionales basados en instancias reales y simuladas son reportadas. |
URI: | http://bibdigital.epn.edu.ec/handle/15000/19635 |
Type: | bachelorThesis |
Appears in Collections: | Tesis Matemáticas (MAT) |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
CD-9038.pdf | 647,45 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.