Michael Malmros Sørensen

The optimal graph partitioning problem: Solution method based on reducing symmetric nature and combinatorial cuts

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisTidsskriftartikelForskningpeer review

In this paper we consider the problem of partitioning the set of nodes in a graph in at most p classes, such that the sum of node weights in any class is not greater than the class capacity b, and such that the sum of edge weights, for edges connecting nodes in the same class, is maximal. This problem can be formulated as a MILP, which turns out to be completely symmetrical with respect to the p classes, and the gap between the relaxed LP solution and the optimal solution is the largest one possible. These two properties make it very difficult to solve even smaller problems. In this paper it is shown how it is possible to preassign certain nodes to certain classes, thus reducing both the symmetric nature of the formulation, the number of variables and constraints and the gap. It is also shown how the gap can be reduced even further by introducing combinatorial cuts. Computational results based on the two formulations of the problem and combinatorial cuts are presented.
OriginalsprogEngelsk
TidsskriftOR Spektrum
Vol/bind15
Nummer1
Sider (fra-til)1-8
Antal sider8
StatusUdgivet - 1993

Se relationer på Aarhus Universitet Citationsformater

ID: 116774703