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)
Mathematical model and efficient algorithms for object packing problem. (English) Zbl 1228.05117
Summary: The article is devoted to mathematical models and practical algorithms for solving the cutting and packing (C&P) problem. We review and further enhance the main tool of our studies - phi-functions. Those are constructed here for 2D and 3D objects (unlike other standard tools, such as No-Fit Polygons, which are restricted to the 2D geometry). We also demonstrate that in many realistic cases the phi-functions can be described by quite simple formulas without radicals and other complications. Lastly, a general solution strategy using the phi-functions is outlined and illustrated by several 2D and 3D examples.

05B40Packing; covering (combinatorics)
68U05Computer graphics; computational geometry
Full Text: DOI
[1] Agarwal, P. K.; Flato, E.; Halperin, D.: Polygon decomposition for efficient construction of Minkowski sums, Comput. geom. Theory appl. 21, 29-61 (2002) · Zbl 0991.68124 · doi:10.1016/S0925-7721(01)00041-4
[2] Albano, A.; Sapuppo, G.: Optimal allocation of two-dimensional irregular shapes using heuristic search methods, IEEE transl. System man cybernetics 10, 242-248 (1980)
[3] R.C. Art, An approach to the two-dimensional irregular cutting stock problem, Tech. Report 36.Y08, IBM Cambridge Scientific Centre, 1966
[4] Bennell, J. A.; Dowsland, K. A.: Hybridising tabu search with optimisation techniques for irregular stock cutting, Management sci. 47, 1160-1172 (2001)
[5] Bennell, J. A.; Oliveira, J. F.: The geometry of nesting problems: A tutorial, European J. Oper. res. 184, 397-415 (2008) · Zbl 1136.90030 · doi:10.1016/j.ejor.2006.11.038
[6] J. Bennell, G. Scheithauer, Yu. Stoyan, T. Romanova, Tools of mathematical modelling of arbitrary object packing problems, Ann. Oper. Res., doi:10.1007/s10479-008-0456-5 · Zbl 1201.90167
[7] Bennell, J. A.; Song, X.: A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums, Comput. oper. Res. 35, 267-281 (2008) · Zbl 1136.65023 · doi:10.1016/j.cor.2006.02.026
[8] Birgin, E. G.; Martinez, J. M.; Nishihara, F. H.; Ronconi, D. P.: Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization, Comput. oper. Res. 33, 3535-3548 (2006) · Zbl 1110.90072 · doi:10.1016/j.cor.2005.03.031
[9] Burke, E.; Hellier, R.; Kendall, G.; Whitwell, G.: A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem, Oper. res. 54, 587-601 (2006) · Zbl 1167.90623 · doi:10.1287/opre.1060.0293
[10] Dighe, R.; Jakiela, M. J.: Solving pattern nesting problems with genetic algorithms employing task decomposition and contact, Evol. comput. 3, 239-266 (1996)
[11] Gan, M.; Gopinathan, N.; Jia, X.; Williams, R. A.: Predicting packing characteristics of particles of arbitrary shapes, Kona 22, 82-93 (2004)
[12] Ghosh, P. K.: An algebra of polygons through the notion of negative shapes, CVGIP: image understanding 54, 119-144 (1991) · Zbl 0774.68118 · doi:10.1016/1049-9660(91)90078-4
[13] Gill, P. E.; Murray, W.; Wright, M. G. H.: Practical optimization, (1981) · Zbl 0503.90062
[14] Gomes, A. M.; Oliveira, J. F.: A 2-exchange heuristic for nesting problems, European J. Oper. res. 141, 359-370 (2002) · Zbl 1081.90611 · doi:10.1016/S0377-2217(02)00130-3
[15] Gomes, A. M.; Oliveira, J. F.: Solving irregular strip packing problems by hybridising simulated annealing and linear programming, European J. Oper. res. 171, 811-829 (2006) · Zbl 1116.90088 · doi:10.1016/j.ejor.2004.09.008
[16] Li, Z.; Milenkovic, V.: Compaction and separation algorithms for non-convex polygons and their applications, European J. Oper. res. 84, 539-561 (1995) · Zbl 1127.90403 · doi:10.1016/0377-2217(95)00021-H
[17] D.A. Mahadevan, Optimization in computer-aided pattern packing, Ph.D. Thesis, North Carolina State University, 1984
[18] Milenkovic, V.: Rotational polygon overlap minimization and compaction, Comput. geom. 10, 305-318 (1998) · Zbl 0904.68174 · doi:10.1016/S0925-7721(98)00012-1
[19] Milenkovic, V.: Rotational polygon containment and minimum enclosure using only robust 2D constructions, Comput. geom. 13, 3-19 (1999) · Zbl 0930.68152 · doi:10.1016/S0925-7721(99)00006-1
[20] Milenkovic, V. J.; Daniels, K.: Translational polygon containment and minimal enclosure using mathematical programming, Int. trans. Oper. res. 6, 525-554 (1999)
[21] Oliveira, J. F.; Ferreira, J. S.: Algorithms for nesting problems, applied simulated annealing, Lecture notes in econom. And math. Systems 396, 255-274 (1993)
[22] Pankratov, A. V.; Stoyan, Y.: Placement of non-convex polygons with rotations into a non-convex polygon, , 29-36 (2006)
[23] G. Scheithauer, Y.G. Stoyan, T. Romanova, A. Krivulya, Covering a polygonal region by rectangles, Comput. Optimiz. Appl., doi:10.1007/s10589-009-9258-1 · Zbl 1219.90147
[24] Stoyan, Yu.: Mathematical methods for geometric design, , 67-86 (1983)
[25] Stoyan, Y. G.; Chugay, A.: Packing cylinders and rectangular parallelepipeds with distances between them, European J. Oper. res. 197, 446-455 (2008) · Zbl 1159.90487 · doi:10.1016/j.ejor.2008.07.003
[26] Scheithauer, G.; Stoyan, Yu.G.; Romanova, T. Ye.: Mathematical modeling of interactions of primary geometric 3D objects, Cybernet. systems anal. 41, 332-342 (2005) · Zbl 1102.68684 · doi:10.1007/s10559-005-0067-y
[27] Stoyan, Y. G.; Ponomarenko, L. D.: Minkowski sum and hodograph of the dense placement vector function, Rep. ukrainian SSR acad. Sci., ser. A 10 (1977) · Zbl 0375.50010
[28] Stoyan, Y.; Gil, M.; Terno, J.; Romanova, T.; Scheithauer, G.: Construction of a phi-function for two convex polytopes, Appl. math. 2, 199-218 (2002) · Zbl 1053.90009 · doi:10.4064/am29-2-6
[29] Stoyan, Y.; Scheithauer, G.; Gil, N.; Romanova, T.: $\Phi $-functions for complex 2D-objects, 4OR: quarterly J. Belgian, French and italian operations research soc. 2, 69-84 (2004) · Zbl 1125.90382 · doi:10.1007/s10288-003-0027-1
[30] Stoyan, Yu.; Terno, J.; Scheithauer, G.; Gil, N.; Romanova, T.: Phi-functions for primary 2D-objects, Studia informatica universalis 2, 1-32 (2001)
[31] Watson, P. D.; Tobias, A. M.: An efficient algorithm for the regular W1 packing of polygons in the infinite plane, J. oper. Res. soc. 50, 1054-1062 (1999) · Zbl 1054.90626
[32] Zoutendijk, G.: Methods of feasible directions, A study in linear and non-linear programming (1960) · Zbl 0097.35408
[33] Zoutendijk, G.: Nonlinear programming, computational methods, Integer and nonlinear programming (1970) · Zbl 0336.90057