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 条

[21] An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints [J].

Cheng Lu ;

Zhibin Deng ;

Qingwei Jin .

Journal of Global Optimization, 2017, 67 :475-493

[22] An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints [J].

Lu, Cheng ;

Deng, Zhibin ;

Jin, Qingwei .

JOURNAL OF GLOBAL OPTIMIZATION, 2017, 67 (03) :475-493

[23] A branch-and-bound multi-parametric programming approach for non-convex multilevel optimization with polyhedral constraints [J].

Kassa, Abay Molla ;

Kassa, Semu Mitiku .

JOURNAL OF GLOBAL OPTIMIZATION, 2016, 64 (04) :745-764

[24] Avoiding symmetry-breaking spatial non-uniformity in deformable image registration via a quasi-volume-preserving constraint [J].

Aganj, Iman ;

Reuter, Martin ;

Sabuncu, Mert R. ;

Fischl, Bruce .

NEUROIMAGE, 2015, 106 :238-251

[25] A branch-and-bound procedure for the resource-constrained project scheduling problem with partially renewable resources and general temporal constraints [J].

Watermeyer, Kai ;

Zimmermann, Juergen .

OR SPECTRUM, 2020, 42 (02) :427-460

[26] Data-driven spatial branch-and-bound algorithms for box-constrained simulation-based optimization [J].

Zhai, Jianyuan ;

Boukouvala, Fani .

JOURNAL OF GLOBAL OPTIMIZATION, 2022, 82 (01) :21-50

[27] Global optimization of minimum weight truss topology problems with stress, displacement, and local buckling constraints using branch-and-bound [J].

Stolpe, M .

INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING, 2004, 61 (08) :1270-1309

[28] Data-driven spatial branch-and-bound algorithms for box-constrained simulation-based optimization [J].

Jianyuan Zhai ;

Fani Boukouvala .

Journal of Global Optimization, 2022, 82 :21-50

[29] A fast branch-and-bound algorithm for non-convex quadratic integer optimization subject to linear constraints using ellipsoidal relaxations [J].

Buchheim, Christoph ;

De Santis, Marianna ;

Palagi, Laura .

OPERATIONS RESEARCH LETTERS, 2015, 43 (04) :384-388