Efficient Reduction of Polynomial Zero-One Optimization to the Quadratic Case (Articolo in rivista)

Type
Label
  • Efficient Reduction of Polynomial Zero-One Optimization to the Quadratic Case (Articolo in rivista) (literal)
Anno
  • 2007-01-01T00:00:00+01:00 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi
  • 10.1137/050646500 (literal)
Alternative label
  • Buchheim, C.; Rinaldi, G. (2007)
    Efficient Reduction of Polynomial Zero-One Optimization to the Quadratic Case
    in SIAM journal on optimization (Print)
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Buchheim, C.; Rinaldi, G. (literal)
Pagina inizio
  • 1398 (literal)
Pagina fine
  • 1413 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 18 (literal)
Rivista
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroFascicolo
  • 4 (literal)
Note
  • Mathematical Reviews on the web (MathSciNet) (literal)
  • Google Scholar (literal)
  • ISI Web of Science (WOS) (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • Buchheim, C.: Institut fuer Informatik, Universitaet zu Koeln, Pohligstr. 1, 50969 Koeln, Germany (literal)
Titolo
  • Efficient Reduction of Polynomial Zero-One Optimization to the Quadratic Case (literal)
Abstract
  • We address the problem of optimizing a polynomial with real coefficients over binary variables. We show that a complete polyhedral description of the linearization of such a problem can be derived in a simple way from the polyhedral description of the linearization of some quadratic optimization problem. The number of variables in the latter linearization is only slightly larger than in the former. If polynomial constraints are present in the original problem, then their linearized counterparts carry over to the linearized quadratic problem unchanged. If the original problem formulation does not contain any constraints, we obtain a reduction to unconstrained quadratic zero-one optimization, which is equivalent to the well-studied max-cut problem. The separation problem for general unconstrained polynomial zero-one optimization thus reduces to the separation problem for the cut polytope. This allows us to transfer the entire knowledge gained for the latter polytope by intensive research and, in particular, the sophisticated separation techniques that have been developed. We report preliminary experimental results obtained with a straightforward implementation of this approach. (literal)
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


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