A Complementary Column Generation Approach for the Graph Equipartition Problem

Simple item page
dc.contributor.authorAl-Ykoob, Salem M.en
dc.contributor.authorSherali, Hanif D.en
dc.contributor.departmentIndustrial and Systems Engineeringen
dc.date.accessioned2021-01-12T15:10:19Zen
dc.date.available2021-01-12T15:10:19Zen
dc.date.issued2020-03-23en
dc.description.abstractThis paper investigates the problem of partitioning a complete weighted graph into complete subgraphs, each having the same number of vertices, with the objective of minimizing the sum of edge weights of the resulting subgraphs. This NP-complete problem arises in many applications such as assignment and scheduling-related group partitioning problems and micro-aggregation techniques. In this paper, we present a mathematical programming model and propose a complementary column generation approach to solve the resulting model. A dual based lower bounding feature is also introduced to curtail the notorious tailing-off effects often induced when using column generation methods. Computational results are presented for a wide range of test problems.en
dc.description.notesThis work was supported by Kuwait University under Research Grant No. [SM03/14].en
dc.description.sponsorshipKuwait University [SM03/14]en
dc.format.mimetypeapplication/pdfen
dc.identifier.doihttps://doi.org/10.15388/20-INFOR391en
dc.identifier.eissn1822-8844en
dc.identifier.issn0868-4952en
dc.identifier.issue1en
dc.identifier.urihttp://hdl.handle.net/10919/101856en
dc.identifier.volume31en
dc.language.isoenen
dc.rightsCreative Commons Attribution 4.0 Internationalen
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/en
dc.subjectgraph partitioningen
dc.subjectcolumn generationen
dc.subjectcomplementary column generationen
dc.subjectmixed-integer programmingen
dc.titleA Complementary Column Generation Approach for the Graph Equipartition Problemen
dc.title.serialInformaticaen
dc.typeArticle - Refereeden
dc.type.dcmitypeTexten
dc.type.dcmitypeStillImageen

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
infor391.pdf
Size:
183.33 KB
Format:
Adobe Portable Document Format
Description:
Download

Collections

Scholarly Works, Industrial and Systems Engineering