超尺寸物品装箱问题及其算法

本文探讨一类新装箱问题-超尺寸物品装箱问题。针对实际解决该问题的两涉法，我们提出了一个评价效率更高的目标函数，证明了在此目标函数下两步法的渐近最坏比不小于2，并给出了渐近量坏比与拆分次数的关系。最后本文提出了一种不同于两步法的新在线算法MA，证明了在新目标函数下其渐近最坏比不超过7/4。     

An efficient numerical scheme for precise time integration of a diffusion-dissolution/precipitation chemical system

A numerical scheme based on an operator splitting method and a dense output event location algorithm is proposed to integrate a diffusion-dissolution/precipitation chemical initial-boundary value problem with jumping nonlinearities. The numerical analysis of the scheme is carried out and it is proved to be of order 2 in time. This global order estimate is illustrated numerically on a test case.

     

Solution of large‐scale weighted least‐squares problems

A sequence of least‐squares problems of the form min_y∥G^1/2(A^T y?h)∥₂, where G is an n×n positive‐definite diagonal weight matrix, and A an m×n (m?n) sparse matrix with some dense columns; has many applications in linear programming, electrical networks, elliptic boundary value problems, and structural analysis. We suggest low‐rank correction preconditioners for such problems, and a mixed solver (a combination of a direct solver and an iterative solver). The numerical results show that our technique for selecting the low‐rank correction matrix is very effective. Copyright © 2002 John Wiley & Sons, Ltd.     

Approximate Inverse Preconditioners for Some Large Dense Random Electrostatic Interaction Matrices

A sparse mesh-neighbour based approximate inverse preconditioner is proposed for a type of dense matrices whose entries come from the evaluation of a slowly decaying free space Green’s function at randomly placed points in a unit cell. By approximating distant potential fields originating at closely spaced sources in a certain way, the preconditioner is given properties similar to, or better than, those of a standard least squares approximate inverse preconditioner while its setup cost is only that of a diagonal block approximate inverse preconditioner. Numerical experiments on iterative solutions of linear systems with up to four million unknowns illustrate how the new preconditioner drastically outperforms standard approximate inverse preconditioners of otherwise similar construction, and especially so when the preconditioners are very sparse. AMS subject classification (2000) 65F10, 65R20, 65F35, 78A30     

Transport of Neutrally Buoyant and Dense Variably Sized Colloids in a Two-Dimensional Fracture with Anisotropic Aperture

The transport of monodisperse as well as polydisperse colloid suspensions in a two-dimensional, water saturated fracture with spatially variable and anisotropic aperture is investigated with a particle tracking model. Both neutrally buoyant and dense colloid suspensions are considered. Although flow and transport in fractured subsurface formations have been studied extensively by numerous investigators, the transport of dense, polydisperse colloid suspensions in a fracture with spatially variable and anisotropic aperture has not been previously explored. Simulated snapshots and breakthrough curves of ensemble averages of several realizations of a log-normally distributed aperture field show that polydisperse colloids exhibit greater spreading than monodisperse colloids, and dense colloids show greater retardation than neutrally buoyant colloids. Moreover, it is demonstrated that aperture anisotropy oriented along the flow direction substantially increases colloid spreading; whereas, aperture anisotropy oriented transverse to the flow direction retards colloid movement.     

可压稠密气固两相流动过程的模拟计算

基于稠密气体分子运动论和颗粒动理学,建立可压稠密气固两相流动模型。采用梯度模拟来考虑气相可压缩性对气相湍流的影响。模拟计算表明气固两相射流速度沿轴向和径向减小,颗粒浓度下降。气固两相射流具有高的颗粒温度,呈现强烈的气固两相湍流流动特性。     

A Hybrid Improvement Heuristic for the One-Dimensional Bin Packing Problem

We propose in this work a hybrid improvement procedure for the bin packing problem. This heuristic has several features: the use of lower bounding strategies; the generation of initial solutions by reference to the dual min-max problem; the use of load redistribution based on dominance, differencing, and unbalancing; and the inclusion of an improvement process utilizing tabu search. Encouraging results have been obtained for a very wide range of benchmark instances, illustrating the robustness of the algorithm. The hybrid improvement procedure compares favourably with all other heuristics in the literature. It improved the best known solutions for many of the benchmark instances and found the largest number of optimal solutions with respect to the other available approximate algorithms.     

PACKING PAIRS BY QUINTUPLES:THE CASE OF ZERO CONGRUENCE MOD 4

ＰＡＣＫＩＮＧＰＡＩＲＳＢＹＱＵＩＮＴＵＰＬＥＳ：ＴＨＥＣＡＳＥＯＦＺＥＲＯＣＯＮＧＲＵＥＮＣＥＭＯＤ４ＹＩＮＪＩＡＮＸＩＮＧＡｂｓｔｒａｃｔ：ＬｅｔＤ（ｖ）ｄｅｎｏｔｅｔｈｅｍａｘｉｍｕｍｎｕｍｂｅｒｏｆｑｕｉｎｔｕｐｌｅｓｏｆａｖ－ｓｅｔｏｆｐｏ...     

A Constraint Programming Approach to Extract the Maximum Number of Non-Overlapping Test Forms

This paper introduces a novel approach for extracting the maximum number of non-overlapping test forms from a large collection of overlapping test sections assembled from a given item bank. The approach involves solving maximum set packing problems (MSPs). A branch-and-bound MSP algorithm is developed along with techniques adapted from constraint programming to estimate lower and upper bounds on the optimal MSP solution. The algorithm is general and can be applied in other applications including combinatorial auctions. The results of computer simulations and experiments with an operational item bank are presented. An erratum to this article is available at .