The γ-connected assignment problem

Given a graph and costs of assigning to each vertex one of k different colors, we want to find a minimum cost assignment such that no color q induces a subgraph with more than a given number ( γ q ) of connected components. This problem arose in the context of contiguity-constrained clustering, but...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 1999-10, Vol.118 (1), p.127-138
Main Authors: Poggi de Aragão, Marcus, Uchoa, Eduardo
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Assignment
Clustering
Cutting
Exact sciences and technology
Integer programming
Operational research and scientific management
Operational research. Management science
Operations research
Optimization. Search problems
Pricing
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a graph and costs of assigning to each vertex one of k different colors, we want to find a minimum cost assignment such that no color q induces a subgraph with more than a given number ( γ q ) of connected components. This problem arose in the context of contiguity-constrained clustering, but also has a number of other possible applications. We show the problem to be NP-hard. Nevertheless, we derive a dynamic programming algorithm that proves the case where the underlying graph is a tree to be solvable in polynomial time. Next, we propose mixed-integer programming formulations for this problem that lead to branch-and-cut and branch-and-price algorithms. Finally, we introduce a new class of valid inequalities to obtain an enhanced branch-and-cut. Extensive computational experiments are reported.
ISSN:0377-2217
1872-6860
DOI:10.1016/S0377-2217(98)00305-1