Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/352925
Type: DISSERTAÇÃO DIGITAL
Degree Level: Mestrado
Title: The balanced connected k-partition problem : polyhedra and algorithms = O problema da k-partição conexa balanceada : poliedros e algoritmos
Title Alternative: O problema da k-partição conexa balanceada : poliedros e algoritmos
Author: Ota, Matheus Jun, 1994-
Advisor: Miyazawa, Flávio Keidi, 1970-
Abstract: Resumo: Dado um inteiro fixo $k \geq 2$, o problema da $k$-partição conexa balanceada (BCPk) consiste em particionar um grafo em $k$ subgrafos conexos mutuamente disjuntos e com pesos similares. Formalmente, dado um grafo conexo G com pesos não-negativos nos vértices, desejamos encontrar uma partição $\{V_i\}_{i=1}^k$ de $V(G)$ tal que cada classe $V_i$ induz um subgrafo conexo em $G$, e o peso da classe com menor peso seja o maior possível. Esse problema, conhecido por ser NP-difícil, foi muito investigado por diversas abordagens e perspectivas: algoritmos exatos, algoritmos de aproximação para alguns valores de $k$ ou classes de grafos, variantes próximas do problema e resultados de inaproximabilidade. Do ponto de vista prático, o BCPk é utilizado para modelar problemas em processamento de imagens, análise de clusters, sistemas operacionais e robótica. Nesse trabalho, propomos duas formulações baseadas em Programação Linear Mista e uma formulação baseada em Programação Linear Inteira para o BCPk. As primeiras duas formulações são baseadas em fluxos e possuem um número polinomial de variáveis e restrições. A última formulação contém somente variáveis binárias e um número potencialmente grande de desigualdades que podem ser separadas em tempo polinomial. Introduzimos novas desigualdades válidas para esse último modelo e projetamos algoritmos de separação polinomial correspondentes. Além disso, apresentamos resultados poliédricos associados a essa formulação. Pelo que sabemos, não existe resultados dessa natureza para o BCPk na literatura. Utilizando a plataforma OpenStreetMap e os dados públicos sobre a criminalidade em certas regiões, geramos novas instâncias baseadas na aplicação de patrulhamento policial. Experimentos computacionais mostram que os algoritmos exatos baseados nas nossas formulações são superiores aos melhores métodos exatos presentes na literatura

Abstract: Given a fixed integer $k \geq 2$, the balanced connected $k$-partition problem (BCPk) consists of partitioning a graph into $k$ mutually vertex-disjoint subgraphs of similar weight. More formally, given a connected graph $G$ with non-negative weights on the vertices, we want to find a partition $\{V_i\}_{i=1}^k$ of~$V(G)$ such that each class $V_i$ induces a connected subgraph of $G$, and the weight of a class with the minimum weight is as large as possible. This problem, known to be NP-hard, has been largely investigated under different approaches and perspectives: exact algorithms, approximation algorithms for some values of $k$ or special classes of graphs, close variants of the problem, and inapproximability results. On the practical side, BCPk is used to model many applications arising in image processing, cluster analysis, operating systems and robotics. We propose two MILP formulations and one ILP formulation for BCPk. The first two are based on flows and have a polynomial number of constraints and variables. The last formulation contains only binary variables and a potentially large number of constraints that can be separated in polynomial time in the corresponding linear relaxation. We introduce new valid inequalities and design polynomial-time separation algorithms for them. Furthermore, we present polyhedral results based on this ILP formulation. To our knowledge, this is the first polyhedral study for BCPk in the literature. Using the OpenStreetMap platform and public crime data, we generated new instances based on a police patrolling application. Our computational experiments show that the exact algorithms based on the proposed formulations outperform the other approaches presented in the literature
Subject: Teoria dos grafos
Programação linear inteira
Otimização combinatória
Combinatória poliédrica
Algoritmos branch-and-cut
Language: Inglês
Editor: [s.n.]
Citation: OTA, Matheus Jun. The balanced connected k-partition problem : polyhedra and algorithms = O problema da k-partição conexa balanceada : poliedros e algoritmos. 2020. 1 recurso online (83 p.) Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação, Campinas, SP.
Date Issue: 2020
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Ota_MatheusJun_M.pdf2.79 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.