http://www.cnr.it/ontology/cnr/individuo/prodotto/ID7073

Primal Separation for 0/1 Polytopes (Articolo in rivista)

Type

Label

Anno

Alternative label

Eisenbrand, F.; Rinaldi, G.; Ventura, P. (2003)
Primal Separation for 0/1 Polytopes
in Mathematical programming
(literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori

Pagina inizio

Pagina fine

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume

Rivista

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#descrizioneSinteticaDelProdotto

One of the fundamental theorems of polyhedral combinatorics states the polynomial time equivalence between the problem of optimizing a linear function over a polyhedron and the problem of finding an hyperplane (if it exists) that separates a given point from the same polytope (dual separation). This theorem has been the basis for the most relevant algorithmic developments over the last twenty year for the solution of hard combinatorial and integer optimization problems. Recently, there is an increasing interest in the so called \"primal\" approach where the separating hyperplane is also required to \"touch\" a specified vertex of the polyhedron (primal separation). This papers, among other results, establishes the \"primal\" analog of the above result. I.e., it states the polynomial time equivalence between the problem of optimizing a linear function over a polyhedron and the problem of separating (in the primal sense) a given point from the same polyhedron in the case when the polyhedron is a 0-1 polytope. This is the case for most of the combinatorial optimization problems and for the integer optimization problems with 0-1 variables. The paper has been published in one of the top journals in Optimization. (literal)

Note

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni

Eisenbrand, F.: Max Plank Institut fuer Informatik, Saarbrucken, Germany -- Rinaldi, G. and Ventura, P.: Istituto di Analisi dei Sistemi ed Informatica \"A. Ruberti\" - CNR (literal)

Titolo

Abstract

The 0/1 primal separation problem is: Given an extreme point $\bar{x}$ of a 0/1 polytope $P$ and some point $x^*$, find an inequality which is tight at $\bar{x}$, violated by $x^*$ and valid for $P$ or assert that no such inequality exists. It is known that this separation variant can be reduced to the standard separation problem for $P$. We show that 0/1 optimization and 0/1 primal separation are polynomial time equivalent. This implies that the problems 0/1 optimization, 0/1 standard separation, 0/1 augmentation, and 0/1 primal separation are polynomial time equivalent. Then we provide polynomial time primal separation procedures for matching, stable set, maximum cut, and maximum bipartite graph problems, giving evidence that these algorithms are conceptually simpler and easier to implement than their corresponding counterparts for standard separation. In particular, for perfect matching we present an algorithm for primal separation that rests only on simple max-flow computations. Consequently, we obtain a very simple proof that a maximum weight perfect matching of a graph can be computed in polynomial time. In contrast, the known standard separation method involves Padberg and Rao's minimum odd cut algorithm, which itself is based on the construction of a Gomory-Hu tree. (literal)

Prodotto di

Autore CNR

Insieme di parole chiave

Autore CNR di

Prodotto

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi

Insieme di parole chiave di

data.CNR.it