13 out 2020
14:00 Master's Defense Fully distance
Theme
The Balanced Connected k-Partition Problem: Polyhedra and Algorithms
Student
Matheus Jun Ota
Advisor / Teacher
Flavio Keidi Miyazawa
Brief summary
Given a fixed integer k \ geq 2, the problem of the balanced connected k-partition (BCPk) consists of partitioning a graph into k mutually disjointly connected subgraphs with similar weights. Formally, given a connected graph G with non-negative weights at 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 in G, and the weight of the lightest class is the largest possible. This problem, known to be NP-difficult, has been extensively investigated by several approaches and perspectives: exact algorithms, approximation algorithms for some values of k and graph classes, variants close to the problem and results of inappropriability. On the practical side, BCPk is used to model problems in image processing, cluster analysis, operating systems and robotics. In this work we propose two formulations based on Mixed Linear Programming for BCPk and a formulation based on Integer Linear Programming. The first two formulations are based on flows and have a polynomial number of variables and constraints. The last formulation contains only binary variables and a potentially large number of inequalities that can be separated in polynomial time. We introduced new valid inequalities for the latter model and designed corresponding polynomial separation algorithms. In addition, we conducted a polyhedral study associated with this formulation. To our knowledge, this is the first polyhedral study for BCPk in the literature. Using the OpenStreetMap platform and public data on crime in certain regions, we generate new instances based on the application of police patrolling. Computational experiments show that the exact algorithms based on our formulations are superior to the best exact methods found in the literature.
Examination Board
Headlines:
| Flávio Keidi Miyazawa | IC / UNICAMP |
| Eduardo Uchoa Barboza | UFF |
| Ricardo Fukasawa | University of Waterloo / Canada |
Substitutes:
| Eduardo Candido Xavier | IC / UNICAMP |
| Luis Augusto Angelotti Meira | FT / UNICAMP |