New and improved results for packing identical unitary radius circles within triangles, rectangles and strips

被引：50

作者：

Birgin, Ernesto G. ^{[1
]}

Gentil, Jan M. ^{[1
]}

机构：

[1] Univ Sao Paulo, Inst Math & Stat, Dept Comp Sci, BR-05508090 Sao Paulo, Brazil

来源：

COMPUTERS & OPERATIONS RESEARCH | 2010年 / 37卷 / 07期

基金：

巴西圣保罗研究基金会;

关键词：

Packing; Non-linear equations system; Newton's method; Non-linear programming; AUGMENTED LAGRANGIAN-METHODS; ARBITRARY CONVEX REGIONS; EQUAL CIRCLES; OPTIMIZATION; SQUARE; ALGORITHM;

D O I：

10.1016/j.cor.2009.09.017

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The focus of study in this paper is the class of packing problems. More specifically, it deals with the placement of a set of N circular items of unitary radius inside an object with the aim of minimizing its dimensions. Differently shaped containers are considered, namely circles, squares, rectangles, strips and triangles. By means of the resolution of non-linear equations systems through the Newton-Raphson method, the herein presented algorithm succeeds in improving the accuracy of previous results attained by continuous optimization approaches up to numerical machine precision. The computer implementation and the data sets are available at http://www.ime.usp.br/similar to egbirgin/packing/. (C) 2009 Elsevier Ltd, All rights reserved.

引用

页码：1318 / 1327

页数：10

共 22 条

[1] ON AUGMENTED LAGRANGIAN METHODS WITH GENERAL LOWER-LEVEL CONSTRAINTS [J].

Andreani, R. ;

Birgin, E. G. ;

Martinez, J. M. ;

Schuverdt, M. L. .

SIAM JOURNAL ON OPTIMIZATION, 2008, 18 (04) :1286-1309

[2] Augmented Lagrangian methods under the constant positive linear dependence constraint qualification [J].

Andreani, R. ;

Birgin, E. G. ;

Martinez, J. M. ;

Schuverdt, M. L. .

MATHEMATICAL PROGRAMMING, 2008, 111 (1-2) :5-32

[3] Minimizing the object dimensions in circle and sphere packing problems [J].

Birgin, E. G. ;

Sobral, F. N. C. .

COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (07) :2357-2375

[4] Structured minimal-memory inexact quasi-Newton method and secant preconditioners for augmented Lagrangian optimization [J].

Birgin, E. G. ;

Martinez, J. M. .

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2008, 39 (01) :1-16

[5] Method of sentinels for packing items within arbitrary convex regions [J].

Birgin, E. G. ;

Martinez, J. M. ;

Mascarenhas, W. F. ;

Ronconi, D. P. .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2006, 57 (06) :735-746

[6] Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization [J].

Birgin, E. G. ;

Martinez, J. M. ;

Nishihara, F. H. ;

Ronconi, D. P. .

COMPUTERS & OPERATIONS RESEARCH, 2006, 33 (12) :3535-3548

[7] Numerical comparison of Augmented Lagrangian algorithms for nonconvex problems [J].

Birgin, EG ;

Castillo, RA ;

Martínez, JM .

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2005, 31 (01) :31-55

[8] Optimizing the packing of cylinders into a rectangular container:: A nonlinear approach [J].

Birgin, EG ;

Martínez, JM ;

Ronconi, DP .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2005, 160 (01) :19-33

[9]

Bondy A., 2008, GRAPH THEORY

[10]

Dennis J E, 1996, NUMERICAL METHODS UN

← 1 2 3 →