The γ-connected assignment problem

The γ-connected assignment problem

0.00 Avg rating0 Votes
Article ID: iaor20003013
Country: Netherlands
Volume: 118
Issue: 1
Start Page Number: 127
End Page Number: 138
Publication Date: Oct 1999
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: integer, programming: dynamic
Abstract:

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 (yq) 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.

Reviews

Required fields are marked *. Your email address will not be published.