Lifting and Separation Procedures for the Cut Polytope (Articolo in rivista)

Type
Label
  • Lifting and Separation Procedures for the Cut Polytope (Articolo in rivista) (literal)
Anno
  • 2014-01-01T00:00:00+01:00 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi
  • 10.1007/s10107-013-0688-2 (literal)
Alternative label
  • Thorsten Bonato, Michael Juenger, Gerhard Reinelt, Giovanni Rinaldi (2014)
    Lifting and Separation Procedures for the Cut Polytope
    in Mathematical programming
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Thorsten Bonato, Michael Juenger, Gerhard Reinelt, Giovanni Rinaldi (literal)
Pagina inizio
  • 351 (literal)
Pagina fine
  • 378 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 146 (literal)
Rivista
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#pagineTotali
  • 28 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • Bonato, Reinelt: Institut fuer Informatik, Universitaet Heidelberg Juenger: Institut fuer Informatik, Universitaet Koeln Rinaldi: Istituto di Analisi dei Sistemi ed Informatica \"A. Ruberti\" - CNR (literal)
Titolo
  • Lifting and Separation Procedures for the Cut Polytope (literal)
Abstract
  • The max-cut problem and the associated cut polytope on complete graphs have been extensively studied over the last 25 years. However, in comparison, only little research has been conducted for the cut polytope on arbitrary graphs, in particular separation algorithms have received only little attention. In this study we describe new separation and lifting procedures for the cut polytope on general graphs. These procedures exploit algorithmic and structural results known for the cut polytope on complete graphs to generate valid, and sometimes facet defining, inequalities for the cut polytope on arbitrary graphs in a cutting plane framework. We report computational results on a set of well-established benchmark problems. (literal)
Prodotto di
Autore CNR

Incoming links:


Autore CNR di
Prodotto
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
data.CNR.it