Aarhus University Seal / Aarhus Universitets segl

Michael Malmros Sørensen

Polyhedral Computations for the Simple Graph Partitioning Problem

Publikation: Working paperForskning

Dokumenter

  • L 2005 02

    Forlagets udgivne version, 230 KB, PDF-dokument

  • Erhvervsøkonomisk Institut
  • CORAL - Centre for Operations Research Applications in Logistics
The simple graph partitioning problem is to partition an edge-weighted graph into mutually disjoint subgraphs, each containing no more than b nodes, such that the sum of the weights of all edges in the subgraphs is maximal. In this paper we present a branch-and-cut algorithm for the problem that uses several classes of facet-defining inequalities as cuttingplanes. These are b-tree, clique, cycle with ear, multistar, and S, Tinequalities. Descriptions of the separation procedures that are used for these inequality classes are also given. In order to evaluate the usefulness of the inequalities and the overall performance of the branch-and-cut algorithm several computational experiments are conducted. We present some of the results of these experiments.
OriginalsprogEngelsk
UdgiverAarhus School of Business, Department of Accounting, Finance and Logistics
ISBN (Elektronisk)87-7882-080-4
StatusUdgivet - 2005

Se relationer på Aarhus Universitet Citationsformater

Download-statistik

Ingen data tilgængelig

ID: 32342785