Métodos exactos para el problema de k-particionamiento con restricciones de tamaño y peso

Arias Navarrete, Yohandra Rubi; Escobar Ortiz, Ana Julia

Por favor, use este identificador para citar o enlazar este ítem: http://bibdigital.epn.edu.ec/handle/15000/19635

Registro completo de metadatos

Campo DC	Valor	Lengua/Idioma
dc.contributor.author	Arias Navarrete, Yohandra Rubi	-
dc.contributor.author	Escobar Ortiz, Ana Julia	-
dc.date.accessioned	2018-08-03T17:34:54Z	-
dc.date.available	2018-08-03T17:34:54Z	-
dc.date.issued	2018-08-03	-
dc.identifier.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.	es_ES
dc.identifier.other	T-FCM/0230/CD 9038	-
dc.identifier.uri	http://bibdigital.epn.edu.ec/handle/15000/19635	-
dc.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.	es_ES
dc.description.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	es_ES
dc.description.sponsorship	Torres Gordillo, Ramiro Daniel, director	es_ES
dc.language.iso	spa	es_ES
dc.publisher	Quito, 2018.	es_ES
dc.rights	openAccess	es_ES
dc.subject	INVESTIGACIÓN OPERATIVA	es_ES
dc.subject	ALGORITMO BRANCH & CUT	es_ES
dc.subject	PROGRAMACIÓN	es_ES
dc.title	Métodos exactos para el problema de k-particionamiento con restricciones de tamaño y peso	es_ES
dc.type	bachelorThesis	es_ES
Aparece en las colecciones:	Tesis Matemáticas (MAT)

Ficheros en este ítem:

Fichero	Descripción	Tamaño	Formato
CD-9038.pdf		647,45 kB	Adobe PDF	Visualizar/Abrir

Muestra el registro sencillo del ítem

BIBDIGITAL