-

 

 

 




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: 03/19/2017

Modify/Update this entry


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

 

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