zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization. (English) Zbl 1110.90072
Summary: The orthogonal packing of rectangular items in an arbitrary convex region is considered in this work. The packing problem is modeled as the problem of deciding for the feasibility or infeasibility of a set of nonlinear equality and inequality constraints. A procedure based on nonlinear programming is introduced and numerical experiments which show that the new procedure is reliable are exhibited. We address the problem of packing orthogonal rectangles within an arbitrary convex region. We aim to show that smooth nonlinear programming models are a reliable alternative for packing problems and that well-known general-purpose methods based on continuous optimization can be used to solve the models. Numerical experiments illustrate the capabilities and limitations of the approach.

90C25Convex programming
90C27Combinatorial optimization
Full Text: DOI
[1] Dyckhoff, H.; Scheithauer, G.; Terno, J.: Cutting and packing: an annotated bibliography. Annotated bibliographies in combinatorial optimization, 393-412 (1997) · Zbl 1068.90509
[2] Lodi, A.; Martello, S.; Monaci, M.: Two-dimensional packing problems: a survey. European journal of operational research 141, 241-252 (2003) · Zbl 1081.90576
[3] Tarnowski, A.; Terno, J.; Scheithauer, G.: A polynomial-time algorithm for the guillotine pallet loading problem. Infor 32, 275-287 (1994) · Zbl 0824.90117
[4] Dowsland, K. A.: An exact algorithm for the pallet loading problem. European journal of operational research 84, 78-84 (1987) · Zbl 0614.90084
[5] Morabito, R.; Morales, S.: A simple and effective recursive procedure for the manufacturer’s pallet loading problem. Journal of the operational research society 49, 819-828 (1998) · Zbl 1140.90517
[6] Lins, L.; Lins, S.; Morabito, R.: An L-approach for packing (l,w)-rectangles into rectangular and L-shaped pieces. Journal of the operational research society 54, 777-789 (2003) · Zbl 1060.90063
[7] Birgin EG, Morabito R, Nishihara FH. A note on an L-approach for solving the manufacturer’s pallet loading problem. Journal of the Operational Research Society, to appear, doi:10.1057/palgrave.jors.2601960. · Zbl 1142.90469
[8] Beasley, J. E.: A population heuristic for constrained two-dimensional non-guillotine cutting. European journal of operational research 156, 601-627 (2004) · Zbl 1056.90011
[9] Birgin EG, Martínez JM, Mascarenhas WF, Ronconi DP. Method of Sentinels for packing objects whitin arbitrary regions, Technical Report MCDO 040221 (www.ime.usp.br/∼egbirgin), Department of Applied Mathematics, UNICAMP, Brazil, 2004.
[10] Martínez, J. M.; Martínez, L.: Packing optimization for automated generation of complex system’s initial configurations for molecular dynamics and docking. Journal of computational chemistry 24, 819-825 (2003)
[11] Birgin, E. G.; Martínez, J. M.; Ronconi, D. P.: Optimizing the packing of cylinders into a rectangular container: a nonlinear approach. European journal of operational research 160, 19-33 (2005) · Zbl 1067.90133
[12] Mladenović N, Plastria F, Urošević D. Reformulation descent applied to circle packing problems. Computers & Operations Research 2005;32:2419 -- 34. · Zbl 1066.90092
[13] Stoyan, Y. G.; Yaskov, G.: A mathematical model and a solution method for the problem of placing various-sized circles into a strip. European journal of operational research 156, 590-600 (2004) · Zbl 1056.90018
[14] Wang, H.; Huang, W.; Zhang, Q.; Xu, D.: An improved algorithm for the packing of unequal circles within a larger containing circle. European journal of operational research 141, 440-453 (2002) · Zbl 1081.90593
[15] Birgin, E. G.; Martínez, J. M.: Large-scale active-set box-constrained optimization method with spectral projected gradients. Computational optimization and applications 23, 101-125 (2002) · Zbl 1031.90012
[16] Birgin, E. G.; Martínez, J. M.; Raydan, M.: Nonmonotone spectral projected gradient methods on convex sets. SIAM journal on optimization 10, 1196-1211 (2000) · Zbl 1047.90077
[17] Birgin, E. G.; Martínez, J. M.; Raydan, M.: Algorithm 813: SPG-software for convex-constrained optimization. ACM transactions on mathematical software 27, 340-349 (2001) · Zbl 1070.65547
[18] Andreani R, Birgin EG, Martínez JM, Yuan J. Spectral projected gradient and variable metric methods for optimization with linear inequalities. IMA Journal of Numerical Analysis 2005;25:221 -- 52. · Zbl 1072.90051
[19] Birgin EG, Castillo R, Martínez JM. Numerical comparison of augmented Lagrangian algorithms for nonconvex problems. Computational Optimization and Applications 2005;31:31 -- 56. · Zbl 1101.90066
[20] Jr., J. E. Dennis; Schnabel, R. B.: Numerical methods for unconstrained optimization and nonlinear equations. (1983) · Zbl 0579.65058
[21] Luenberger, D. G.: Linear and nonlinear programming. (1984) · Zbl 0571.90051
[22] Birgin, E. G.; Martínez, J. M.: A box constrained optimization algorithm with negative curvature directions and spectral projected gradients. Computing 15, No. Suppl., 49-60 (2001) · Zbl 1002.65067