A fast algorithm for identifying minimum size instances of the equivalence classes of the Pallet Loading Problem

In this paper, a novel and fast algorithm for identifying the Minimum Size Instance (MSI) of the equivalence class of the Pallet Loading Problem (PLP) is presented. The new algorithm is based on the fact that the PLP instances of the same equivalence class have the property that the aspect ratios of their items belong to an open interval of real numbers. This interval characterises the PLP equivalence classes and is referred to as the Equivalence Ratio Interval (ERI) by authors of this paper. The time complexity of the new algorithm is two polynomial orders lower than that of the best known algorithm. The authors of this paper also suggest that the concept of MSI and its identifying algorithm can be used to transform the non-integer PLP into its equivalent integer MSI.     

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

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

The G4-Heuristic for the Pallet Loading Problem

A new heuristic for the well-known (two-dimensional orthogonal) pallet loading problem (PLP) is proposed in this paper. This heuristic, referred to as G4-heuristic, is based on the definition of the so-called G4-structure of packing patterns. The G4-structure is a generalization of the common used block structure of packing patterns which requires the same orientation of packed boxes within each block. The G4-heuristic yields in approximately 99% of the test instances an optimal solution and solves all instances exactly where at most 50 boxes are contained in an optimal packing. Although the algorithm is pseudo-polynomial the computational experiments reported show that also instances with more than 200 packed boxes in an optimal solution can be handled with a small amount of computational time. Moreover, so far there is not known any instance where the gap between optimal value and the value obtained by the G4-heuristic is larger than one box.     

Analysis of upper bounds for the Pallet Loading Problem

This paper is concerned with upper bounds for the well-known Pallet Loading Problem (PLP), which is the problem of packing identical boxes into a rectangular pallet so as to maximize the number of boxes fitted. After giving a comprehensive review of the known upper bounds in the literature, we conduct a detailed analysis to determine which bounds dominate which others. The result is a ranking of the bounds in a partial order. It turns out that two of the bounds dominate all others: a bound due to Nelissen and a bound obtained from the linear programming relaxation of a set packing formulation. Experiments show that the latter is almost always optimal and can be computed quickly.     

基于对角转轮样式的托盘装箱优化模型

针对托盘装箱问题(PLP),建立了对角转轮样式下具有托盘柔性的整数规划模型,设计了求解模型的启发式算法,并利用VB程序对模型的最优解及装箱图谱进行了讨论分析,结果表明:对角转轮样式就提高具有较大长、宽比箱子的装载效率以及解决装箱压缝问题方面具有明显的优势;而柔性也是影响托盘装载效率的重要因素之一,具有较大的回报率.     

关于一类几何极值问题

设平面上边长为１和２的闭矩形区域为Ｒ，Ｓ是Ｒ上一个有限点集，ｆ（Ｓ）是Ｓ中任意两点之间的最小距离，ｆＲ（ｎ）＝ｍａｘｆ（Ｓ），本文给出了当２≤ｎ≤６时，ｆＲ（ｎ）的精确值以及相应的图形．     

The minimum size of a finite subspace partition

A subspace partition of P=PG(n,q) is a collection of subspaces of P whose pairwise intersection is empty. Let σ_q(n,t) denote the minimum size (i.e., minimum number of subspaces) in a subspace partition of P in which the largest subspace has dimension t. In this paper, we determine the value of σ_q(n,t) for . Moreover, we use the value of σ_q(2t+2,t) to find the minimum size of a maximal partial t-spread in PG(3t+2,q).     

A Note on a Packing Problem in Transitive Tournaments

Let TT_n be a transitive tournament on n vertices. We show that for any directed acyclic graph G of order n and of size not greater than two directed graphs isomorphic to G are arc disjoint subgraphs of TT_n. Moreover, this bound is generally the best possible. The research partially supported by KBN grant 2 P03A 016 18     

The Clustered Orienteering Problem

In this paper we study a generalization of the Orienteering Problem (OP) which we call the Clustered Orienteering Problem (COP). The OP, also known as the Selective Traveling Salesman Problem, is a problem where a set of potential customers is given and a profit is associated with the service of each customer. A single vehicle is available to serve the customers. The objective is to find the vehicle route that maximizes the total collected profit in such a way that the duration of the route does not exceed a given threshold. In the COP, customers are grouped in clusters. A profit is associated with each cluster and is gained only if all customers belonging to the cluster are served. We propose two solution approaches for the COP: an exact and a heuristic one. The exact approach is a branch-and-cut while the heuristic approach is a tabu search. Computational results on a set of randomly generated instances are provided to show the efficiency and effectiveness of both approaches.     

A Network Approach to a Geometric Packing Problem

We investigate a geometric packing problem (derived from an industrial setting) that involves fitting patterns of regularly spaced disks without overlap. We first derive conditions for achieving a feasible placement of a given set of patterns and then construct a network formulation that facilitates the calculation of such a placement. A heuristic utilizing this network representation is also outlined. Additionally, we show a connection to the well-known Periodic Scheduling Problem.     

The Held—Karp algorithm and degree-constrained minimum 1-trees

In this note we propose to find a degree-constrained minimum 1-tree in the Held—Karp algorithm [5, 6] for the symmetric traveling-salesman problem, and show that it is reduced to finding a minimum common basis of two matroids.     

The undirected m-Capacitated Peripatetic Salesman Problem

In the m-Capacitated Peripatetic Salesman Problem (m-CPSP) the aim is to determine m Hamiltonian cycles of minimal total cost on a graph, such that all the edges are traversed less than the value of their capacity. This article introduces three formulations for the m-CPSP. Two branch-and-cut algorithms and one branch-and-price algorithm are developed. Tests performed on randomly generated and on TSPLIB Euclidean instances indicate that the branch-and-price algorithm can solve instances with more than twice the size of what is achievable with the branch-and-cut algorithms.     

A trichotomy for a class of equivalence relations

Let Xn, n ∈ N be a sequence of non-empty sets, ψn : Xn2 → IR+. We consider the relation E = E((Xn, ψn)n∈N) on ∏n∈N Xn by (x, y) ∈ E((Xn, ψn)n∈N) <=>Σn∈Nψn(x(n), y(n)) < +∞. If E is an equiv- alence relation and all ψn, n ∈ N, are Borel, we show a trichotomy that either IRN/e1≤B E, E1≤B E, or E≤B E0. We also prove that, for a rather general case, E((Xn, ψn)n∈N) is an equivalence relation iff it is an ep-like equivalence relation.     

广义Bochner-Riesz乘子的等价性及其应用——献给陆善镇教授75华诞

本文研究下面这两个函数,（1-｜x｜^ρ1）＋^α和（1-｜x｜^ρ2）＋^α,其中ρ1,ρ2和α均为正实数,文献上称这类函数为广义Bochner-Riesz乘子.本文将证明,当α给定时,对任意的ρ1〉0和ρ2〉0,这两个函数作为乘子,其乘子算子的L^p有界性和Hp有界性是等价的.     

The Delivery Man Problem with time windows

In this paper, a variant of the Traveling Salesman Problem with Time Windows is considered, which consists in minimizing the sum of travel durations between a depot and several customer locations. Two mixed integer linear programming formulations are presented for this problem: a classical arc flow model and a sequential assignment model. Several polyhedral results are provided for the second formulation, in the special case arising when there is a closed time window only at the depot, while open time windows are considered at all other locations. Exact and heuristic algorithms are also proposed for the problem. Computational results show that medium size instances can be solved exactly with both models, while the heuristic provides good quality solutions for medium to large size instances.     

Lipschitz equivalence of a class of general Sierpinski carpets

In this paper, we discuss the Lipschitz equivalence of a class of general Sierpinski carpets in which all non-trivial connected components are line segments. We define a bijection between two link-separated sets with same type by pairing off the basic sets using the indexing by the corresponding symbol space and get a sufficient condition that two general Sierpinski carpets are Lipschitz equivalent. Several examples will be given to illustrate our idea.     

应用迭代法求解一类非线性问题

本文应用迭代法求解一类有限维非线性问题,该方法是求解线性问题的雅可比迭代法在非线性问题上的推广,且此迭代方法具有几何收敛性质.     

最大流问题的逆问题

讨论了最大流问题的逆问题,提出了ｆ＾０截的概念,给出并证明了逆问题有解的充要条件;当逆问题有解时,把逆问题转化为找一个容量网络的最小截的问题;最后,给出了一个复杂度为Ｏ（│Ｖ│＾３）的多项式算法。