Optimization Online


On the impact of symmetry-breaking constraints on spatial Branch-and-Bound for circle packing in a square

Alberto Costa (costa***at***lix.polytechnique.fr)
Pierre Hansen (pierre.hansen***at***gerad.ca)
Leo Liberti (liberti***at***lix.polytechnique.fr)

Abstract: We study the problem of packing equal circles in a square from the mathematical programming point of view. We discuss different formulations, we analyse formulation symmetries, we propose some symmetry breaking constraints and show that not only do they tighten the convex relaxation bound, but they also ease the task of local NLP solution algorithms in finding feasible solutions. We solve the problem by means of a standard spatial Branch-and-Bound implementation, and show that our formulation improvements allow the algorithm to find very good solutions at the root node.

Keywords: Symmetry, Reformulation, Narrowing, Circle Packing, Nonconvex NLP

Category 1: Global Optimization

Category 2: Nonlinear Optimization

Category 3: Combinatorial Optimization

Citation: Published in Discrete Applied Mathematics 161(1–2):96–106, 2013. http://www.sciencedirect.com/science/article/pii/S0166218X12002855


Entry Submitted: 04/12/2011
Entry Accepted: 04/26/2011
Entry Last Modified: 11/07/2012

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