Home  About us  Contact
 

Packing Problem (packing + problem)

Distribution by Scientific Domains
Mathematics and Statistics44%

Selected Abstracts

Adaptive beam search lookahead algorithms for the circular packing problem

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 5 2010
Hakim Akeb
Abstract This paper addresses the circular packing problem (CPP), which consists in packing n circles Ci, each of known radius ri, i,N={1, ,, n}, into the smallest containing circle C. The objective is to determine the radius r of C as well as the coordinates (xi, yi) of the center of Ci, i,N. CPP is solved using two adaptive algorithms that adopt a binary search to determine r, and a beam search to check the feasibility of packing n circles into C when the radius is fixed at r. A node of level ,, ,=1, ,, n, of the beam search tree corresponds to a partial packing of , circles of N into C. The potential of each node of the tree is assessed using a lookahead strategy that, starting with the partial packing of the current node, assigns each unpacked circle to its maximum hole degree position. The beam search stops either when the lookahead strategy identifies a feasible packing or when it has fathomed all nodes. The computational tests on a set of benchmark instances show the effectiveness of the proposed adaptive algorithms. [source]

Solving the irregular strip packing problem via guided local search for overlap minimization

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 6 2009
Shunji Umetani
Abstract The irregular strip-packing problem (ISP) requires a given set of non-convex polygons to be placed without overlap within a rectangular container having a fixed width and a variable length, which is to be minimized. As a core sub-problem to solve ISP, we consider an overlap minimization problem (OMP) whose objective is to place all polygons into a container with given width and length so that the total amount of overlap between polygons is made as small as possible. We propose to use directional penetration depths to measure the amount of overlap between a pair of polygons, and present an efficient algorithm to find a position with the minimum overlap for each polygon when it is translated in a specified direction. Based on this, we develop a local search algorithm for OMP that translates a polygon in horizontal and vertical directions alternately. Then we incorporate it in our algorithm for OMP, which is a variant of the guided local search algorithm. Computational results show that our algorithm improves the best-known values of some well-known benchmark instances. [source]

Approximation schemes for ordered vector packing problems

NAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 1 2003
Alberto Caprara
In this paper we deal with the d -dimensional vector packing problem, which is a generalization of the classical bin packing problem in which each item has d distinct weights and each bin has d corresponding capacities. We address the case in which the vectors of weights associated with the items are totally ordered, i.e., given any two weight vectors ai, aj, either ai is componentwise not smaller than aj or aj is componentwise not smaller than ai. An asymptotic polynomial-time approximation scheme is constructed for this case. As a corollary, we also obtain such a scheme for the bin packing problem with cardinality constraint, whose existence was an open question to the best of our knowledge. We also extend the result to instances with constant Dilworth number, i.e., instances where the set of items can be partitioned into a constant number of totally ordered subsets. We use ideas from classical and recent approximation schemes for related problems, as well as a nontrivial procedure to round an LP solution associated with the packing of the small items. © 2002 Wiley Periodicals, Inc. Naval Research Logistics, 2003 [source]

On d -threshold graphs and d -dimensional bin packing

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2004
Alberto Caprara
Abstract We illustrate efficient algorithms to find a maximum stable set and a maximum matching in a graph with n nodes given by the edge union of d threshold graphs on the same node set, in case the d graphs in the union are known. Actually, because the edge set of a threshold graph can be implicitly represented by assigning values to the nodes, we assume that we know these values for each of the d graphs in the union. We present an O(n log n + nd,1) time algorithm to find a maximum stable set and an O(n2) time algorithm to find a maximum matching, in case d is constant. For the case d = 2, the running time of the latter is reduced to O(n log n) provided an additional technical condition is satisfied. The natural application of our results is the fast computation of lower bounds for the d -dimensional bin packing problem, for which the compatibility relations between items are represented by the edge union of d threshold graphs with one node for each item, the value of the node for the i -th graph being equal to the size of the item on the i -th dimension. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 266,280 2004 [source]

An unexpected co-crystal with a variable degree of order: 1:1 rac -1,2-cyclohexanediol/triphenylphosphine oxide

ACTA CRYSTALLOGRAPHICA SECTION B, Issue 6 2007
Maxime A. Siegler
A 1:1 co-crystal of rac - trans -1,2-C6H10(OH)2 and (C6H5)3PO has been found that is unusual because there are no strong interactions between the two kinds of molecules, which are segregated into layers. Furthermore, neither pure rac -1,2-cyclohexanediol (CHD) nor pure triphenylphosphine oxide (TPPO) has any obvious packing problem that would make the formation of inclusion complexes likely. The TPPO layers are very much like those found in two of the four known polymorphs of pure TPPO. The hydrogen-bonded ribbons of CHD are similar to those found in other vic -diol crystals. The co-crystals are triclinic (space group P), but the deviations from monoclinic symmetry (space group C2/c) are small. The magnitudes of those deviations depend on the solvent from which the crystal is grown; the deviations are largest for crystals grown from acetone, smallest for crystals grown from toluene, and intermediate for crystals grown from ethanol. The deviations arise from incomplete enantiomeric disorder of the R,R and S,S diols; this disorder is not required by symmetry in either space group, but occupancy factors are nearly 0.50 when the structure is refined as monoclinic. When the structure is refined as triclinic the deviations of the occupancy factors from 0.50 mirror the deviations from monoclinic symmetry because information about the partial R,R/S,S ordering is transmitted from one diol layer to the next through the very pseudosymmetric TPPO layer. Analyses suggest individual CHD layers are at least mostly ordered. The degree of order seems to be established at the time the crystal is grown and is unlikely to change with heating or cooling. Thermal data suggest the existence of the co-crystal is a consequence of kinetic rather than thermodynamic factors. [source]

Solid-state compounds of stereoisomers: cis and trans isomers of 1,2-cyclohexanediol and 2,3-tetralindiol

ACTA CRYSTALLOGRAPHICA SECTION B, Issue 3 2007
Michael A. Lloyd
The phases of 1,2,3,4-tetrahydro-2,3-naphthalenediol (or 2,3-tetralindiol) and of 1,2-cyclohexanediol have been investigated. The structure of a very stable 1:1 compound (or co-crystal) of the cis and trans isomers of 2,3-tetralindiol, the existence of which has been known for nearly a century, has finally been determined. No evidence of any analogous compound between the cis and trans isomers of 1,2-cyclohexanediol has been found. The formation of solid-state compounds of stereoisomers is rare; it probably occurs only if the crystal packing of at least one of the isomers is unfavorable, e.g. if at least one of the melting points is lower than expected. Compound formation is usually unlikely because of the difficulty of simultaneously optimizing the translational spacings for both isomers, but that packing problem is avoided in the cis/trans compound of 2,3-tetralindiol because the two isomers are in very similar environments. In the structures of the individual 2,3-tetralindiol isomers there are clear conflicts between the competing packing requirements of the 1,2-diol moiety and the aromatic ring system; these conflicts are resolved better in the co-crystal than in the structures of the individual isomers. [source]

Approximation schemes for ordered vector packing problems

NAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 1 2003
Alberto Caprara
In this paper we deal with the d -dimensional vector packing problem, which is a generalization of the classical bin packing problem in which each item has d distinct weights and each bin has d corresponding capacities. We address the case in which the vectors of weights associated with the items are totally ordered, i.e., given any two weight vectors ai, aj, either ai is componentwise not smaller than aj or aj is componentwise not smaller than ai. An asymptotic polynomial-time approximation scheme is constructed for this case. As a corollary, we also obtain such a scheme for the bin packing problem with cardinality constraint, whose existence was an open question to the best of our knowledge. We also extend the result to instances with constant Dilworth number, i.e., instances where the set of items can be partitioned into a constant number of totally ordered subsets. We use ideas from classical and recent approximation schemes for related problems, as well as a nontrivial procedure to round an LP solution associated with the packing of the small items. © 2002 Wiley Periodicals, Inc. Naval Research Logistics, 2003 [source]

Approximation algorithms for channel allocation problems in broadcast networks

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2006
Rajiv Gandhi
Abstract We study two packing problems that arise in the area of dissemination-based information systems; a second theme is the study of distributed approximation algorithms. The problems considered have the property that the space occupied by a collection of objects together could be significantly less than the sum of the sizes of the individual objects. In the Channel Allocation Problem, there are requests that are subsets of topics. There are a fixed number of channels that can carry an arbitrary number of topics. All the topics of each request must be broadcast on some channel. The load on any channel is the number of topics that are broadcast on that channel; the objective is to minimize the maximum load on any channel. We present approximation algorithms for this problem, and also show that the problem is MAX-SNP hard. The second problem is the Edge Partitioning Problem addressed by Goldschmidt, Hochbaum, Levin, and Olinick (Networks, 41:13,23, 2003). Each channel here can deliver topics for at most k requests, and we aim to minimize the total load on all channels. We present an O(n1/3),approximation algorithm, and also show that the algorithm can be made fully distributed with the same approximation guarantee; we also generalize the (nondistributed) Edge Partitioning Problem of graphs to the case of hypergraphs. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(4), 225,236 2006 [source]