IDEAS home Printed from https://ideas.repec.org/p/cor/louvco/1994037.html
   My bibliography  Save this paper

Formulations and Valid Inequalities for the Node Capacitated Graph Partitioning Problem

Author

Listed:
  • FERREIRA, Carlos E.

    (Universidade de Sao Paulo, Brazil)

  • MARTIN, Alexander

    (Konrad-Zuse-Zentrum fiir Informationstechnik Berlin)

  • de SOUZA, Cid C.

    (CORE, Université catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium)

  • WEISMANTEL, Robert

    (Konrad-Zuse-Zentrum fUr Informationstechnik Berlin)

Abstract

We investigate the problem of partitioning the nodes of a graph under capacity restriction on the sum of the node weights in each subset of the partition. The objective is to minimize the sum of the costs of the edges between the subsets of the partition. This problem has a variety of applications, for instance in the design of electronic circuits and devices. We present alternative integer programming formulations for this problem and discuss the links between these formulations. Having chosen to work in the space of edges of the multicut, we investigate the convex hull of incidence vectors of feasible multicuts. In particular, several classes of inequalities are introduced, and their strength and robustness are analyzed as various problem parameters change.

Suggested Citation

  • FERREIRA, Carlos E. & MARTIN, Alexander & de SOUZA, Cid C. & WEISMANTEL, Robert, 1994. "Formulations and Valid Inequalities for the Node Capacitated Graph Partitioning Problem," LIDAM Discussion Papers CORE 1994037, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    • Handle: RePEc:cor:louvco:1994037
    as

    Download full text from publisher

    File URL: https://sites.uclouvain.be/core/publications/coredp/coredp1994.html
    Download Restriction: no
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:cor:louvco:1994037. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Alain GILLIS (email available below). General contact details of provider: https://edirc.repec.org/data/coreebe.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.