On the impact of symmetry-breaking constraints on spatial Branch-and-Bound for circle packing in a square |
| |
Authors: | Alberto Costa Pierre Hansen Leo Liberti |
| |
Institution: | 1. LIX, École Polytechnique, 91128 Palaiseau, France;2. GERAD, HEC, 3000 chemin de la Côte-S.te-Catherine, H3T 2A7 Montreal, Canada |
| |
Abstract: | We study the problem of packing equal circles in a square from the mathematical programming point of view. We discuss different formulations, we analyze 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: | |
本文献已被 ScienceDirect 等数据库收录! |
|