Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement

Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement

0.00 Avg rating0 Votes
Article ID: iaor20073113
Country: Netherlands
Volume: 4
Issue: 1
Start Page Number: 87
End Page Number: 102
Publication Date: Mar 2007
Journal: Discrete Optimization
Authors: ,
Keywords: game theory, programming: branch and bound
Abstract:

Given a complete graph Kn=(V,E) with edge weight ce on each edge, we consider the problem of partitioning the vertices of graph Kn into subcliques that have at least S vertices, so as to minimize the total weight of the edges that have both endpoints in the same subclique. In this paper, we consider using the branch-and-price method to solve the problem. We demonstrate the necessity of cutting planes for this problem and suggest effective ways of adding cutting planes in the branch-and-price framework. The NP hard pricing problem is solved as an integer programming problem. We present computational results on large randomly generated problems.

Reviews

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