Packing circles in a square: a theoretical comparison of various convexification techniques
aida khajavirad (aida.khajaviradgmail.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.
Entry Submitted: 03/19/2017
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|