Solving Partition Problems : A Branch-and-Cut Approach based on Semidefinite Programming

ISBN-13: 9783639136210 / Angielski / Miękka / 2009 / 104 str.

Bissan Ghaddar

Opis

The minimum k-partition (MkP) problem is the problemof partitioning the set of vertices of a graph into kdisjoint subsets so as to minimize the total weightof the edges joining vertices in the same partition.The main contribution is the design andimplementation of a novel iterative clusteringheuristic (ICH) based on semide nite programming to nd feasible solutions for the MkP problem. Wecompare ICH to the hyperplane rounding techniques,and the computational results support the conclusionthat ICH consistently provides better feasiblesolutions for the MkP problem. We use ICH in abranch-and-cut algorithm to provide feasiblesolutions at each node of the branch-and-bound tree.The branch-and-cut algorithm computes globallyoptimal solutions for dense graphs with up to 60vertices, for grid graphs with up to 100 vertices,and for different values of k, providing the bestexact approach to date for k 2.

O autorze

Bissan Ghaddar is a Ph.D. candidate in Operations Research at the
University of Waterloo Canada since 2007. Her research interest
is mainly focused on combinatorial optimization techniques and
their application to problems arising in industry. Her recent
research includes the application of polynomial programming to
solve binary quadratic problems.