装箱问题的算法及最新进展

装箱问题在经济社会发展中扮演着重要的角色,该问题研究的是寻找较好的布局方式,尽可能实现利益的最大化.装箱问题具有NP-难性质,其理论和应用研究存在一定的挑战,但因其有广泛的应用背景而受到研究者高度的关注.本文主要总结近几十年来装箱问题的研究成果,特别针对一维、二维和三维单目标装箱问题和算法,以及多目标装箱问题的算法进行概括和总结,并提出装箱问题算法上有待进一步的研究工作.     

NiO、CuO在γ-Al2O3表面分布问题的探究——第21届全国化学竞赛决赛第6题的解析

对一个全国高中化学竞赛(决赛)试题晶体部分NiO、CuO在γ-Al2O3表面的分布问题进行分析、探究,并对试题问题的设置进行了整合重组和新的设计.     

Effects of Different Amount of Crystalline Solvate Molecules on Solid Structures and Photophysical Properties of a Platinum(II) Moiety with 4,4′‐Dibromo‐2,2′‐Bipyridine Ligand

A platinum(II) complex Pt(DiBrbpy)Cl₂ ( 1 ) based on 4,4′‐dibromo‐2,2′‐bipyridine ligand was synthesized and characterized. Interestingly, two solvated phases of 1 with different amounts of crystalline CH₂Cl₂ molecules, 1· 1/3(CH₂Cl₂) (yellow) and 1· 3/2(CH₂Cl₂) (red), were obtained. In the solid state, 1· 1/3(CH₂Cl₂) exhibits a 3D supramolecular structure based on Pt(DiBrbpy)Cl₂ monomer and emits a weak yellow luminescence at 541 nm (579, sh). In contrast, 1· 3/2(CH₂Cl₂) displays a 2D layer structure based on Pt(DiBrbpy)Cl₂ dimeric units and has a strong red luminescence centered at 624 nm. The results show that crystalline solvate molecule amount can not only influence the packing structures but also photophysical properties of the platinum moiety in solid state. Furthermore, the absorption and luminescence spectra of both phases were studied by TD‐DFT calculations.     

Packing directed cycles efficiently

Let G be a simple digraph. The dicycle packing number of G, denoted ν_c(G), is the maximum size of a set of arc-disjoint directed cycles in G. Let G be a digraph with a nonnegative arc-weight function w. A function ψ from the set C of directed cycles in G to R₊ is a fractional dicycle packing of G if ∑_e∈C∈Cψ(C)?w(e) for each e∈E(G). The fractional dicycle packing number, denoted , is the maximum value of ∑_C∈Cψ(C) taken over all fractional dicycle packings ψ. In case w≡1 we denote the latter parameter by .Our main result is that where n=|V(G)|. Our proof is algorithmic and generates a set of arc-disjoint directed cycles whose size is at least ν_c(G)-o(n²) in randomized polynomial time. Since computing ν_c(G) is an NP-Hard problem, and since almost all digraphs have ν_c(G)=Θ(n²) our result is a FPTAS for computing ν_c(G) for almost all digraphs.The result uses as its main lemma a much more general result. Let F be any fixed family of oriented graphs. For an oriented graph G, let ν_F(G) denote the maximum number of arc-disjoint copies of elements of F that can be found in G, and let denote the fractional relaxation. Then, . This lemma uses the recently discovered directed regularity lemma as its main tool.It is well known that can be computed in polynomial time by considering the dual problem. We present a polynomial algorithm that finds an optimal fractional dicycle packing. Our algorithm consists of a solution to a simple linear program and some minor modifications, and avoids using the ellipsoid method. In fact, the algorithm shows that a maximum fractional dicycle packing with at most O(n²) dicycles receiving nonzero weight can be found in polynomial time.     

An investigation into two bin packing problems with ordering and orientation implications

This paper considers variants of the one-dimensional bin packing (and stock cutting) problem in which both the ordering and orientation of items in a container influences the validity and quality of a solution. Two new real-world problems of this type are introduced, the first that involves the creation of wooden trapezoidal-shaped trusses for use in the roofing industry, the second that requires the cutting and scoring of rectangular pieces of cardboard in the construction of boxes. To tackle these problems, two variants of a local search-based approximation algorithm are proposed, the first that attempts to determine item ordering and orientation via simple heuristics, the second that employs more accurate but costly branch-and-bound procedures. We investigate the inevitable trade-off between speed and accuracy that occurs with these variants and highlight the circumstances under which each scheme is advantageous.     

The multiple container loading cost minimization problem

In the shipping and transportation industry, there are several types of standard containers with different dimensions and different associated costs. In this paper, we examine the multiple container loading cost minimization problem (MCLCMP), where the objective is to load products of various types into containers of various sizes so as to minimize the total cost. We transform the MCLCMP into an extended set cover problem that is formulated using linear integer programming and solve it with a heuristic to generate columns. Experiments on standard bin-packing instances show our approach is superior to prior approaches. Additionally, since the optimal solutions for existing test data is unknown, we propose a technique to generate test data with known optimal solutions for MCLCMP.     

From random sphere packings to regular pillar arrays: effect of the macroscopic confinement on hydrodynamic dispersion

Flow and mass transport in bulk and confined chromatographic supports comprising random packings of solid, spherical particles and hexagonal arrays of solid cylinders (regular pillar arrays) are studied over a wide flow velocity range by a numerical analysis scheme, which includes packing generation by a modified Jodrey-Tory algorithm, three-dimensional flow field calculations by the lattice-Boltzmann method, and modeling of advective-diffusive mass transport by a random-walk particle-tracking technique. We demonstrate the impact of the confinement and its cross-sectional geometry (circular, quadratic, semicircular) on transient and asymptotic transverse and longitudinal dispersion in random sphere packings, and also address the influence of protocol-dependent packing disorder and the particle-aspect ratio. Plate height curves are analyzed with the Giddings equation to quantify the transcolumn contribution to eddy dispersion. Confined packings are compared with confined arrays under the condition of identical bed porosity, conduit cross-sectional area, and laterally fully equilibrated geometrical wall and corner effects on dispersion. Fluid dispersion in a regular pillar array is stronger affected by the macroscopic confinement and does not resemble eddy dispersion in random sphere packings, because the regular microstructure cannot function as a mechanical mixer like the random morphology. Giddings' coupling theory fails to preserve the nature of transverse dispersion behind the arrays' plate height curves, which approach a linear velocity-dependence as transverse dispersion becomes velocity-independent. Upon confinement this pseudo-diffusive behavior can outweigh the performance advantage of the regular over the random morphology.     

Polymorphism in Alkali Metal Uranyl Nitrates: Synthesis and Crystal Structure of γ‐K(UO2)(NO3)3

Single crystals of γ‐K(UO₂)(NO₃)₃ were prepared from aqueous solutions by evaporation. The crystal structure [orthorhombic, Pbca (61), a = 9.2559(3) Å, b = 12.1753(3) Å, c = 15.8076(5) Å, V = 1781.41(9) Å³, Z = 8] was determined by direct methods and refined to R₁ = 0.0267 on the basis of 3657 unique observed reflections. The structure is composed of isolated anionic uranyl trinitrate units, [(UO₂)(NO₃)₃]^–, that are linked through eleven‐coordinated K⁺ cations. Both known polymorphs of K(UO₂)(NO₃)₃ (α‐ and γ‐phases) can be considered as based upon sheets of isolated complex [(UO₂)(NO₃)₃]^– ions separated by K⁺ cations. The existence of polymorphism in the two K[UO₂(NO₃)₃] polymorphs is due to the different packing modes of uranyl trinitrate clusters that adopt the same two‐dimensional but different three‐dimensional arrangements.     

Effect of chemical structure of polycarbonates on entanglement spacing

The master curves of a series of aliphatic polycarbonates(APCs) with different lengths of methylene segments in the repeat unit were obtained by dynamic rheological measurements.The plateau modulus and entanglement molecular weight were determined and cross-checked by different methods.Though having distinct difference in chemical structure of repeat units,both APCs and bisphenol-A polycarbonates have the similar entanglement weight and entanglement spacing.On the other side,the plateau modulus decreases with increasing the length of the side group of aliphatic polycarbonates with different side-chain lengths in the literature.The packing length model can explain the relationship between chain structure and entanglements.     

Iterated tabu search for the circular open dimension problem

This paper investigates the circular open dimension problem (CODP), which consists of packing a set of circles of known radii into a strip of fixed width and unlimited length without overlapping. The objective is to minimize the length of the strip. In this paper, CODP is solved by a series of sub-problems, each corresponding to a fixed strip length. For each sub-problem, an iterated tabu search approach, named ITS, is proposed. ITS starts from a randomly generated solution and attempts to gain improvements by a tabu search procedure. After that, if the obtained solution is not feasible, a perturbation operator is subsequently employed to reconstruct the incumbent solution and an acceptance criterion is implemented to determine whether or not accept the perturbed solution. As a supplementary method, the length of the strip is determined in monotonously decreasing way, with the aid of some post-processing techniques. The search terminates and returns the best found solution after the allowed computation time has been elapsed. Computational experiments based on numerous well-known benchmark instances show that ITS produces quite competitive results, with respect to the best known results, while the computational time remains reasonable for each instance.