Packing problems: Difference between revisions

Revision as of 15:43, 25 April 2022

Revision as of 06:12, 27 April 2022

Line 1:

{{short description|Problems which attempt to find the most efficient way to pack objects into containers}}

{{about|geometric packing problems|numerical packing problems|Knapsack problem}}

[[File:Seissand.png|thumb|[[Sphere]]s or [[circle]]s packed loosely (top) and more densely (bottom)]]

Line 4 ⟶ 5:

{{Puzzles |topics}}

'''Packing problems''' are a class of [[optimization problem]]s in [[mathematics]] that involve attempting to pack objects together into containers. The goal is to either pack a single container as [[Packing density|densely]] as possible or pack all objects using as few containers as possible. Many of these problems can be related to real -life [[packaging]], storage and transportation issues. Each packing problem has a dual [[covering problem]], which asks how many of the same objects are required to completely cover every region of the container, where objects are allowed to overlap.

In a [[bin packing problem]], you are given:

* A 'containers'container'', (usually a single two- or three-dimensional [[convex region]], orpossibly anof infinite space)size. Multiple containers may be given depending on the problem.

* A set of ''objects' ', some or all of which must be packed into one or more containers. The set may contain different objects with their sizes specified, or a single object of a fixed dimension that can be used repeatedly.

Usually the packing must be without overlaps between goods and other goods or the container walls. In some variants, the aim is to find the configuration that packs a single container with the maximal [[packing density]]. More commonly, the aim is to pack all the objects into as few containers as possible.<ref>{{cite journal|authors= Lodi, A., Martello, S., Monaci, M.|title = Two-dimensional packing problems: A survey| journal = European Journal of Operational Research|year = 2002|publisher = Elsevier|doi=10.1016/s0377-2217(02)00123-6|volume=141|issue = 2|pages=241–252}}</ref> In some variants the overlapping (of objects with each other and/or with the boundary of the container) is allowed but should be minimized.

==Packing in infinite space==