## 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 language | English (US) |
---|---|

State | Published - Jan 1 2014 |

Event | 2014 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2014 - Fort Lauderdale, United States Duration: Jan 6 2014 → Jan 8 2014 |

### Conference

Conference | 2014 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2014 |
---|---|

Country | United States |

City | Fort Lauderdale |

Period | 1/6/14 → 1/8/14 |

## All Science Journal Classification (ASJC) codes

- Applied Mathematics
- Artificial Intelligence