Cones of nonnegative quadratic pseudo-boolean functions

Endre Boros, Isabella Lari

Research output: Contribution to conferencePaper

1 Scopus citations

Abstract

Numerous combinatorial optimization problems can be formulated as the minimization of a quadratic pseudo-Boolean function in n variables, which on its own turn is equivalent with a linear programming problem over the so called Boolean Quadric Polytope (BQ) in (Formula presented.) dimension (Padberg, 1989). This polytope is very well studied, still we know in fact very little about its structure and its facets (complete description is known only for n ≤ 6.) It is known and easy to see that the facets of BQ are in a one to one correspondence with the extremal rays of the cone of nonnegative quadratic pseudo-Boolean functions. Consequently, subcones of this cone correspond to polyhedral relaxations of BQ. Several such relaxations were introduced in the past with several open question remaining regarding the relation of these relaxations. The aim of this short note is to fill in some of these gaps and bring more clarity to the relations between the corresponding polyhedral hierarchies. Our approach utilizes the above cited connection to the cone of nonnegative quadratic pseudo-Boolean functions and is rather algebraic.

Original languageEnglish (US)
StatePublished - Jan 1 2014
Event2014 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2014 - Fort Lauderdale, United States
Duration: Jan 6 2014Jan 8 2014

Conference

Conference2014 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2014
CountryUnited States
CityFort Lauderdale
Period1/6/141/8/14

All Science Journal Classification (ASJC) codes

  • Applied Mathematics
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Cones of nonnegative quadratic pseudo-boolean functions'. Together they form a unique fingerprint.

Cite this