货物尺寸相同的2维装箱问题的等价类

在生产与储运领域,把小长方体货物(盒子)装入大长方体箱子是一项重要的工作.本文涉及的问题是把相同尺寸(a×b×c)的盒子装到一个箱子X×Y×Z中,使所装入箱子的盒子数量为最大.由于某些条件的限止,有时要求货物只能按一个重力方向进行装箱,从而使装箱问题变为把尺寸相同的2维盒子(a×b)填装到一个2维箱子X ×Y中.本文讨论当盒子尺寸(a×b包括b×a)给定,箱子尺寸充分大时,在本文所给的等价意义下,共有多少种互不等价的箱子X×Y.     

与装箱（切割）问题有关的数论结果

在生产与储运领域,把（小的）矩形货物装入（大的）矩形箱子是一项重要的工作。本文回答了以下的问题：设有一个长度为X的一维箱子以及设有两种（或三种）长度分别为α,b （或α,b,c)的人货物许多,问在什么条件下,可以（或不能）用这些货物（假定货物数量不限）装满箱子？或当两（或三）种货物的长度α,b（或α,b,c）给定时,一维箱子的长度X为多大时,用这两（ 或三）种货物能或不能装满箱子？不能被这些货物装满的箱子有多少个？     

组合最优化问题的近似算法(续)

<正> 3.装箱问题(B)有 n 个物体 e_1,e_2,…,e_n,设 e_i 的体积为 w_i.现在有一批相同的箱子 B_1,B_2,…,每只箱子的容量都为 C.我们要求把这 n 个物件都装入箱子里,使得每个箱子里的装入物件总体积不超过 C,并且用的箱子个数最小.装箱问题在运筹学和计算机科学中,都有较广泛的应用,如下料问题,计算机记忆单元的分配问题等.不难看出,装箱问题是集合划分问题的对偶.装箱问题有几个ε-近似算法,我们只介绍其中的三个,并且只对其中之一给予证明.(a)NF 算法.     

一类带多重核元集在线装箱问题

本文讨论了一类在线变尺寸装箱问题,假定箱子的尺寸可以是不同的.箱子是在线到达的,仅当箱子到达后其尺寸才知道.给定一个带有核元的物品表及其上的核元关系图.我们的目标是要将表中元素装入到达的箱子中,保证任何箱子所装物品不互为核元,即所装物品对应的点所导出的子图是个空图,并使得所用的箱子总长最小.我们证明了该问题是NPHard的,并给出了基于图的点染色、图的团分解和基于背包问题的近似算法,给出了算法的时间复杂度和性能界.     

强向量拟均衡问题解的存在性(英文)

设X是一个实的Hausdorff拓扑向量空间,Y是一个实的局部凸向量空间,C是Y中的闭凸锥,K（?）X是一个紧子集.F:X×X→Y是一个双向量函数,G:K→2K是一个集合值映射.我们考虑下面的强拟均衡问题:存在x∈G（x）,使得对任意的y∈G（x）,成立F（x,y）∈C.本文证明了当F是半连续时,上述问题解的存在性结论.     

物品大小不超过1/2的一维在线装箱模型研究

研究主要针对所有装入物品大小上限为1/2时的一维装箱问题模型展开,根据物品尺寸大小划分的思想,提出一种新的一维在线装箱算法.本模型中,物品在线到来,对即将到来的物品信息及物品数量未知,算法执行过程中,首先根据物品尺寸大小将物品划分成7大类,再根据欲先设定的packing规则,将对应类物品放入对应类型箱子中,任何时刻,算法最多打开7个箱子.算法设计过程中,不再需要额外的空间存储物品,物品一旦装入箱子不允许取出重装,箱子关闭后不允许再打开装其他物品.最后,通过详细的分析计算,验证出本算法能获得1.4236的渐近竞争比.同时通过实例构建得出问题新的下界为1.4231,将上下界之间的缝隙缩小至0.0005.     

箱子是在线到达的带核元变尺寸装箱问题

本文考虑了一类箱子在线到达的带核元变尺寸装箱问题．假定箱子的尺寸可以是不同的．箱子是在线到达的，仅当箱子到达后其尺寸才知道．给定一个带有核元的物件表，目标是要将表中元素装入到达的箱子中，使得所用的箱子总长最小．我们首先证明了该问题是强NP—Hard，其次分析了经典算法NF(D)和FF(D)的性能界，指出NF(D)和FF(D)算法的性能界可以任意大．最后我们给出了相应的修改算法MNF(D)和MFF(D)，证明了它们的性能界都是3，此界是紧的．     

带参量的非合作装箱博弈

带参量的非合作装箱博弈是指:每个物品的尺寸都介于0和参量x(0相似文献   

Banach空间中线性流形的单值度量投影算子部分

为了研究Banach空间集值线性映射包含y∈M(x)的最小范数极值解,其中X,Y为Banach空间,M X×Y为线性流形,本文引入Banach空间X×Y中线性流形的单值度量算子部分,并给出了该算子部分的结构的刻划.为在另文将Lee S J与NashedM Z所引进并研究的Hilbert空间中集值线性映射包含的最小二乘解推广到Banach空间奠定了理论基础.     

含向量的方程

在高三的一本数学复习资料中,有一道关于含向量的方程的解的存在性的问题.下面在该题求解的基础上探讨一下怎样判断和解含向量的方程.　　题目　已知a,b,c为非零向量且a⊥b,x∈R,x1,x2 是方程ax2 + bx + c=0的两实根,求证:x1=x2 .1　解法探讨错解　因为a⊥b则a·b=0 .b·(ax2 + bx+ c) =0 ,(b·a) x2 + b2 x+ b·c=0 ,∴　x=- b·cb2 .故,原方程只有唯一解,所以x1=x2 .错因分析　“将原方程两边同点乘b”,不是同解变形.b·(ax2 + b·x+ c) =0成立时,除了ax2 + bx+ c=0外,还有可能是b⊥(ax2 + bx+ c) .所以- (b·c) / b2不一定是原方程的解.…     

Counting dissections into integral squares

A squared rectangle is a rectangle dissected into squares. Similarly a rectangled rectangle is a rectangle dissected into rectangles. The classic paper ‘The dissection of rectangles into squares’ of Brooks, Smith, Stone and Tutte described a beautiful connection between squared rectangles and harmonic functions. In this paper we count dissections of a rectangle into a set of integral squares or a set of integral rectangles. Here, some squares and rectangles may have the same size. We introduce a method involving a recurrence relation of large sized matrices to enumerate squared and rectangled rectangles of a given sized rectangle and propose the asymptotic behavior of their growth rates.     

Polychromatic colorings of rectangular partitions

A rectangular partition is a partition of a plane rectangle into an arbitrary number of non-overlapping rectangles such that no four rectangles share a corner. In this note, it is proven that every rectangular partition admits a vertex coloring with four colors such that every rectangle, except possibly the outer rectangle, has all four colors on its boundary. This settles a conjecture of Dinitz et al. [Y. Dinitz, M.J. Katz, R. Krakovski, Guarding rectangular partitions, in: Abstracts 23rd Euro. Workshop Comput. Geom., 2007, pp. 30-33]. The proof is short, simple and based on 4-edge-colorability of a specific class of planar graphs.     

On rectangular cartograms

A rectangular cartogram is a type of map where every region is a rectangle. The size of the rectangles is chosen such that their areas represent a geographic variable (e.g., population). Good rectangular cartograms are hard to generate: The area specifications for each rectangle may make it impossible to realize correct adjacencies between the regions and so hamper the intuitive understanding of the map.

We present the first algorithms for rectangular cartogram construction. Our algorithms depend on a precise formalization of region adjacencies and build upon existing VLSI layout algorithms. Furthermore, we characterize a non-trivial class of rectangular subdivisions for which exact cartograms can be computed efficiently. An implementation of our algorithms and various tests show that in practice, visually pleasing rectangular cartograms with small cartographic error can be generated effectively.     

Optimal rectangle packing

We consider the NP-complete problem of finding an enclosing rectangle of minimum area that will contain a given a set of rectangles. We present two different constraint-satisfaction formulations of this problem. The first searches a space of absolute placements of rectangles in the enclosing rectangle, while the other searches a space of relative placements between pairs of rectangles. Both approaches dramatically outperform previous approaches to optimal rectangle packing. For problems where the rectangle dimensions have low precision, such as small integers, absolute placement is generally more efficient, whereas for rectangles with high-precision dimensions, relative placement will be more effective. In two sets of experiments, we find both the smallest rectangles and squares that can contain the set of squares of size 1×1, 2×2,…,N×N, for N up to 27. In addition, we solve an open problem dating to 1966, concerning packing the set of consecutive squares up to 24×24 in a square of size 70×70. Finally, we find the smallest enclosing rectangles that can contain a set of unoriented rectangles of size 1×2, 2×3, 3×4,…,N×(N+1), for N up to 25.     

A block-based layer building approach for the 2D guillotine strip packing problem

We examine the 2D strip packing problems with guillotine-cut constraint, where the objective is to pack all rectangles into a strip with fixed width and minimize the total height of the strip. We combine three most successful ideas for the orthogonal rectangular packing problems into a single coherent algorithm: (1) packing a block of rectangles instead of a single rectangle in each step; (2) dividing the strip into layers and pack layer by layer; and (3) unrolling and repacking the top portion of the solutions where usually wasted space occurs. Computational experiments on benchmark test sets suggest that our approach rivals existing approaches.     

An effective recursive partitioning approach for the packing of identical rectangles in a rectangle

In this work, we deal with the problem of packing (orthogonally and without overlapping) identical rectangles in a rectangle. This problem appears in different logistics settings, such as the loading of boxes on pallets, the arrangements of pallets in trucks and the stowing of cargo in ships. We present a recursive partitioning approach combining improved versions of a recursive five-block heuristic and an L-approach for packing rectangles into larger rectangles and L-shaped pieces. The combined approach is able to rapidly find the optimal solutions of all instances of the pallet loading problem sets Cover I and II (more than 50?000 instances). It is also effective for solving the instances of problem set Cover III (almost 100?000 instances) and practical examples of a woodpulp stowage problem, if compared to other methods from the literature. Some theoretical results are also discussed and, based on them, efficient computer implementations are introduced. The computer implementation and the data sets are available for benchmarking purposes.     

A heuristic for the circle packing problem with a variety of containers

In this paper we present a heuristic algorithm based on the formulation space search method to solve the circle packing problem. The circle packing problem is the problem of finding the maximum radius of a specified number of identical circles that can be fitted, without overlaps, into a two-dimensional container of fixed size. In this paper we consider a variety of containers: the unit circle, unit square, rectangle, isosceles right-angled triangle and semicircle. The problem is formulated as a nonlinear optimization problem involving both Cartesian and polar coordinate systems.Formulation space search consists of switching between different formulations of the same problem, each formulation potentially having different properties in terms of nonlinear optimization. As a component of our heuristic we solve a nonlinear optimization problem using the solver SNOPT.Our heuristic improves on previous results based on formulation space search presented in the literature. For a number of the containers we improve on the best result previously known. Our heuristic is also a computationally effective approach (when balancing quality of result obtained against computation time required) when compared with other work presented in the literature.     

4-Block heuristic for the rectangle packing problem

In this paper the rectangle packing problem (RPP) is considered. The RPP consists in finding a packing pattern of small rectangles within a larger rectangle such that the area utilization is maximized. We develop new heuristics for the RPP which are based on the G4-heuristic for the pallet loading problem. In addition to the general RPP we take also into account further restrictions which are of practical interest.     

Improved local search algorithms for the rectangle packing problem with general spatial costs

The rectangle packing problem with general spatial costs is to pack given rectangles without overlap in the plane so that the maximum cost of the rectangles is minimized. This problem is very general, and various types of packing problems and scheduling problems can be formulated in this form. For this problem, we have previously presented local search algorithms using a pair of permutations of rectangles to represent a solution. In this paper, we propose speed-up techniques to evaluate solutions in various neighborhoods. Computational results for the rectangle packing problem and a real-world scheduling problem exhibit good prospects of the proposed techniques.     

Finding squares and rectangles in sets of points

A number of problems concerning sets of points in the plane are studied, e.g. establishing whether it contains a subset of size 4, which are the vertices of a square or rectangle. Both the problems of finding axis-parallel squares and rectangles, and arbitrarily oriented squares and rectangles are studied. Efficient algorithms are obtained for all of them. Furthermore, we investigate the generalizations tod-dimensional space, where the problem is to find hyperrectangles and hypercubes. Also, upper and lower bounds are given for combinatorial problems on the maxium number of subsets of size 4, of which the points are the vertices of a square or rectangle. Then we state an equivalence between the problem of finding rectangles, and the problem of findingK _{2, 2} subgraphs in bipartite graphs. Thus we immediately have an efficient algorithm for this graph problem.This work was partially supported by the ESPRIT Basic Research Action No. 3075 (project ALCOM). Work of the second author was also supported by the Dutch Organisation for Scientific Research (N.W.O.).