Optimization Online


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

aida khajavirad (aida.khajavirad***at***gmail.com)

Abstract: 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 assess their strength theoretically. As we demonstrate both theoretically and numerically, when embedded in branch-and-cut based global solvers, the current state-of-the-art bounding techniques are only effective for small-size circle packing problems.

Keywords: Circle packing problem, Non-overlapping constraints, Polyhedral relaxations, Semi-definite relaxations, Boolean quadric polytope.

Category 1: Global Optimization (Theory )

Category 2: Integer Programming (Cutting Plane Approaches )

Citation: Under review.

Download: [PDF]

Entry Submitted: 03/19/2017
Entry Accepted: 03/19/2017
Entry Last Modified: 07/12/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society