Xiaoyun Ji – Optimization Online

The Clique Partition Problem with Minimum Clique Size Requirement

Published: 2005/05/06

Branch and Cut Algorithms, Cutting Plane Approaches, Polyhedra

Given a complete graph K = (V , E), with edge weight ce on each edge, we consider the problem of partitioning the vertices of graph K into subcliques that each have at least S vertices, so as to minimize the total weight of the edges that have both endpoints in the same subclique. It … Read more

Finding optimal realignments in sports leagues using a branch-and-cut-and-price approach

Published: 2005/02/17

Xiaoyun Ji

John E. Mitchell

Applications - OR and Management Sciences, Branch and Cut Algorithms branch-and-price, clustering, graph equipartition, micro-a ggregation, realignment

The sports team realignment problem can be modelled as $k$-way equipartition: given a complete graph $K_{n}=(V,E)$, with edge weight $c_{e}$ on each edge, partition the vertices $V$ into $k$ divisions that have exactly $S$ vertices, so as to minimize the total weight of the edges that have both endpoints in the same division. In this … Read more