Por favor, use este identificador para citar o enlazar este ítem: http://bibdigital.epn.edu.ec/handle/15000/19635
Título: Métodos exactos para el problema de k-particionamiento con restricciones de tamaño y peso
Autor: Arias Navarrete, Yohandra Rubi
Escobar Ortiz, Ana Julia
Palabras clave: INVESTIGACIÓN OPERATIVA
ALGORITMO BRANCH & CUT
PROGRAMACIÓN
Fecha de publicación: 3-ago-2018
Editorial: Quito, 2018.
Citación: 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.
Resumen: 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
Descripción: 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
Tipo: bachelorThesis
Aparece en las colecciones:Tesis Matemáticas (MAT)

Ficheros en este ítem:
Fichero Descripción TamañoFormato 
CD-9038.pdf647,45 kBAdobe PDFVisualizar/Abrir


Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.