##
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.