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

被引：19

作者：

Costa, Alberto ^{[1
]}

Hansen, Pierre ^{[1
,2
]}

Liberti, Leo ^{[1
]}

机构：

[1] Ecole Polytech, LIX, F-91128 Palaiseau, France

[2] HEC, GERAD, Montreal, PQ H3T 2A7, Canada

来源：

DISCRETE APPLIED MATHEMATICS | 2013年 / 161卷 / 1-2期

关键词：

Symmetry; Reformulation; Narrowing; Circle packing; Nonconvex NLP; GLOBAL OPTIMIZATION; EQUAL CIRCLES; ALGORITHM; GRAPHS;

D O I：

10.1016/j.dam.2012.07.020

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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. (c) 2012 Elsevier B.V. All rights reserved.

引用

页码：96 / 106

页数：11

共 29 条

[11] A Spatial Branch-and-Bound Framework for the Global Optimization of Kinetic Models of Metabolic Networks [J].

Pozo, C. ;

Guillen-Gosalbez, G. ;

Sorribas, A. ;

Jimenez, L. .

INDUSTRIAL & ENGINEERING CHEMISTRY RESEARCH, 2011, 50 (09) :5225-5238

[12] Global optimization of nonlinear least-squares problems by branch-and-bound and optimality constraints [J].

Amaran, Satyajith ;

Sahinidis, Nikolaos V. .

TOP, 2012, 20 (01) :154-172

[13] Global optimization of nonlinear least-squares problems by branch-and-bound and optimality constraints [J].

Satyajith Amaran ;

Nikolaos V. Sahinidis .

TOP, 2012, 20 :154-172

[14] On branching-point selection for trilinear monomials in spatial branch-and-bound: the hull relaxation [J].

Emily Speakman ;

Jon Lee .

Journal of Global Optimization, 2018, 72 :129-153

[15] DATA-DRIVEN SPATIAL BRANCH-AND-BOUND ALGORITHMS FOR BLACK-BOX OPTIMIZATION [J].

Zhai, Jianyuan ;

Boukouvala, Fani .

PROCEEDINGS OF THE 9TH INTERNATIONAL CONFERENCE ON FOUNDATIONS OF COMPUTER-AIDED PROCESS DESIGN, 2019, 47 :71-76

[16] On branching-point selection for trilinear monomials in spatial branch-and-bound: the hull relaxation [J].

Speakman, Emily ;

Lee, Jon .

JOURNAL OF GLOBAL OPTIMIZATION, 2018, 72 (02) :129-153

[17] Parabolic optimal control problems with combinatorial switching constraints, part III: branch-and-bound algorithm [J].

Buchheim, Christoph ;

Gruetering, Alexandra ;

Meyer, Christian .

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2025, 90 (03) :649-689

[18] Solving Lot-Sizing Problems on Parallel Identical Machines Using Symmetry-Breaking Constraints [J].

Jans, Raf .

INFORMS JOURNAL ON COMPUTING, 2009, 21 (01) :123-136

[19] Dynamic adjustment strategy of electric bus operations: A spatial branch-and-bound method with acceleration techniques [J].

Yuan, Yin ;

Li, Shukai ;

D'Ariano, Andrea ;

Bosi, Tommaso ;

Yang, Lixing .

TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES, 2025, 171

[20] On the use of restriction of the right-hand side in spatial branch-and-bound algorithms to ensure termination [J].

Kirst, Peter ;

Fuellner, Christian .

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2025, 90 (03) :691-720

← 1 2 3 →