Branch-and-Price-and-Cut on the Clique Partition Problem with
Minimum Clique Size Requirement
Download the paper,
in pdf.
Authors:
Xiaoyun Ji
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
jix at rpi.edu
John E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
mitchj at rpi.edu
Citation details:
Discrete Optimization, 4 (1), 2007, pages 87-102.
Abstract:
Given a complete graph $K_{n}=(V,E)$ with edge weight $c_{e}$ on each
edge, we
consider the problem of partitioning the vertices of graph $K_{n}$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.
Download the paper,
in pdf.
Return to my list of papers.