Articles liés à Solving Partition Problems: A Branch-and-Cut Approach...

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

Ghaddar, Bissan

 
9783639136210: Solving Partition Problems: A Branch-and-Cut Approach based on Semidefinite Programming
Couverture souple
ISBN 10 : 3639136217 ISBN 13 : 9783639136210
Editeur : VDM Verlag, 2009

Synopsis

The minimum k-partition (MkP) problem is the problem of partitioning the set of vertices of a graph into k disjoint subsets so as to minimize the total weight of the edges joining vertices in the same partition. The main contribution is the design and implementation of a novel iterative clustering heuristic (ICH) based on semide?nite programming to ?nd feasible solutions for the MkP problem. We compare ICH to the hyperplane rounding techniques, and the computational results support the conclusion that ICH consistently provides better feasible solutions for the MkP problem. We use ICH in a branch-and-cut algorithm to provide feasible solutions at each node of the branch-and-bound tree. The branch-and-cut algorithm computes globally optimal solutions for dense graphs with up to 60 vertices, for grid graphs with up to 100 vertices, and for different values of k, providing the best exact approach to date for k > 2.

Les informations fournies dans la section « Synopsis » peuvent faire référence à une autre édition de ce titre.

Présentation de l'éditeur

The minimum k-partition (MkP) problem is the problem of partitioning the set of vertices of a graph into k disjoint subsets so as to minimize the total weight of the edges joining vertices in the same partition. The main contribution is the design and implementation of a novel iterative clustering heuristic (ICH) based on semide?nite programming to ?nd feasible solutions for the MkP problem. We compare ICH to the hyperplane rounding techniques, and the computational results support the conclusion that ICH consistently provides better feasible solutions for the MkP problem. We use ICH in a branch-and-cut algorithm to provide feasible solutions at each node of the branch-and-bound tree. The branch-and-cut algorithm computes globally optimal solutions for dense graphs with up to 60 vertices, for grid graphs with up to 100 vertices, and for different values of k, providing the best exact approach to date for k > 2.

Biographie de l'auteur

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.

Les informations fournies dans la section « A propos du livre » peuvent faire référence à une autre édition de ce titre.

Éditeur
VDM Verlag
Date d'édition
2009
Langue
anglais
ISBN 10 
3639136217
ISBN 13 
9783639136210
Reliure
Broché
Nombre de pages
104
Coordonnées du fabricant
non disponible
Personne responsable
non disponible