polyhedral relaxations

Chvatal rank in binary polynomial optimization

  • Alberto Del Pia
  • Silvia Di Gregorio
    • Categories 0-1 Programming, Cutting Plane Approaches, Global Optimization Theory Tags , , , , ,

    Recently, several classes of cutting planes have been introduced for binary polynomial optimization. In this paper, we present the first results connecting the combinatorial structure of these inequalities with their Chvatal rank. We show that almost all known cutting planes have Chvatal rank 1. All these inequalities have an associated hypergraph that is beta-acyclic, thus, … Read more

    Packing circles in a square: a theoretical comparison of various convexification techniques

  • Aida Khajavirad
    • Categories Cutting Plane Approaches, Global Optimization Theory Tags , , , ,

    We consider the problem of packing congruent circles with the maximum radius in a unit square. As a mathematical program, this problem is a notoriously difficult nonconvex quadratically constrained optimization problem which possesses a large number of local optima. We study several convexification techniques for the circle packing problem, including polyhedral and semi-definite relaxations and … Read more