Lagrangean heuristics combined with reoptimization for the 0-1 bidimensional knapsack problem

First, this paper deals with lagrangean heuristics for the 0-1 bidimensional knapsack problem. A projected subgradient algorithm is performed for solving a lagrangean dual of the problem, to improve the convergence of the classical subgradient algorithm. Secondly, a local search is introduced to improve the lower bound on the value of the biknapsack produced by lagrangean heuristics. Thirdly, a variable fixing phase is embedded in the process. Finally, the sequence of 0-1 one-dimensional knapsack instances obtained from the algorithm are solved by using reoptimization techniques in order to reduce the total computational time effort. Computational results are presented.     

On a nonlinear multigrid algorithm with primal relaxation for the image total variation minimisation

Digital image restoration has drawn much attention in the recent years and a lot of research has been done on effective variational partial differential equation models and their theoretical studies. However there remains an urgent need to develop fast and robust iterative solvers, as the underlying problem sizes are large. This paper proposes a fast multigrid method using primal relaxations. The basic primal relaxation is known to get stuck at a ‘local’ non-stationary minimum of the solution, which is usually believed to be ‘non-smooth’. Our idea is to utilize coarse level corrections, overcoming the deadlock of a basic primal relaxation scheme. A further refinement is to allow non-regular coarse levels to correct the solution, which helps to improve the multilevel method. Numerical experiments on both 1D and 2D images are presented.     

Spectral Representation Theory for Dielectric Behavior of Nonspherical Cell Suspensions

Recent experiments revealed that the dielectric dispersion spectrum of fission yeast cells in a suspension was mainly composed of two sub-dispersions. The low-frequency sub-dispersion depended on the cell length, while the high-frequency one was independent of it. The cell shape effect was simulated by an ellipsoidal cell model but the comparison between theory and experiment was far from being satisfactory. Prompted by the discrepancy, we proposed the use of spectral representation to analyze more realistic cell models. We adopted a shell-spheroidal model to analyze the effects of the cell membrane. It is found that the dielectric property of the cell membrane has only a minor effect on the dispersion magnitude ratio and the characteristic frequency ratio. We further included the effect of rotation of dipole induced by an external electric field, and solved the dipole-rotation spheroidal model in the spectral representation.Good agreement between theory and experiment has been obtained.     

关于求解常微方程组的离散波形松驰方法的加速收敛

提出一种关于求解常微线性系统的离散波形松驰方法的新的加速收敛技巧。通过对系统矩阵A的分裂，该技巧使迭代矩阵（(zI M)^-1N）具有理想的较小谱半径。在LU分解的基础上给出了一个迭代算法以及用该法与Gauss-Seidel方不垢敛速进行比较的数值例子。     

First-passage times in a critical stochastic model

Average first-passage times for a single-variable stochastic model with a critical fixed point at the origin are computed by exact enumeration. The numerical measurements show excellent agreement with analytical results. The scaling function approaches the predicted asymptotic dependence.     

Chain length effect on dynamical structure of poly (vinyl pyrrolidone)-polar solvent mixtures in dilute solution of dioxane studied by microwave dielectric relaxation measurement

Dielectric relaxation study of the binary mixtures of poly(vinyl pyrrolidone) (PVP) (Mw=24000, 40000 and 360000 g mol⁻¹) with ethyl alcohol (EA) and poly(ethylene glycol)s (PEGs) (Mw=200 and 400 g mol⁻¹) in dilute solutions of dioxane were carried out at 10.1 GHz and 35°C. The relaxation time of PVP-EA mixtures was interpreted by the consideration of a wait-and-switch model in the local structure of self-associated ethyl alcohol molecules and also the PVP chain length as a geometric constraint for the reorientational motion of ethyl alcohol molecules. The formation of complexes and effect of PVP chain length on the molecular dynamics, chain flexibility and stretching of PEG molecules in PVP-PEG mixtures were explored from the comparative values of dielectric relaxation time. Further, relaxation time values in dioxane and benzene solvent confirm the viscosity independent molecular dynamics in PVP-EA mixtures but the values vary significantly with the non-polar solvent environment.     

箱覆盖问题的半定松驰算法

箱覆盖问题是NP困难问题中的经典问题，得到了广泛地研究，九十年代以来，半定松驰策略被用来求解组合优化问题，取得了很好的结果[13]，本文首次给箱覆盖问题的半定松驰算法，算法的理论分析结果表明它适合于求解大规模的箱覆盖问题。     

Solved and unsolved problems in surface structure determination

The range of surface structural problems of interest in understanding the physics and chemistry of solid surfaces is reviewed with reference to the available methods and their strengths and limitations. Key challenges being addressed currently concern the achievable precision of measurements and their physical and chemical significance, and the complexity of the problems which may be solved. Past progress and future problems are illustrated with a series of examples ranging from the relaxation of simple clean metal surfaces through complex semiconductor reconstructions to large molecular adsorption and coadsorption systems and complex adsorbate-induced reconstructions. The strengths and limitations of scanning tunnelling microscopy as a complement to true quantitative structural methods are discussed, as is the role of chemical state specificity and elemental specificity in solving complex molecular adsorbate systems.     

Physical aging of a polyetherimide: Creep and DSC measurements

Creep and differential scanning calorimetry (DSC) measurements have been used to study the physical aging behavior of a polyetherimide. Isothermal aging temperatures ranged from 160°C to T_g with aging times ranging from 10 min to 8 days. The only measurable effect of physical aging on the short-time creep curves is a shift of the creep compliance to longer times. Andrade plots of the compliance versus the cube root of time are linear at short times with the slope β decreasing with increasing aging time to a constant value once equilibrium is reached. Log β³ is related directly to the degree to which the creep curves shift to longer times with physical aging, and is used in this work as a measure of physical aging. A reduced curve of log β³ versus log aging time is obtained for the aging temperatures investigated by appropriate vertical and horizontal shifts. The enthalpy change during aging increases linearly with the logarithm of the aging time, t_a, leveling off at equilibrium at values which increase with decreasing aging temperature. Hence, both nonequilibrium and equilibrium temperature shift factors can be calculated from the DSC data. Good agreement is observed between the equilibrium temperature shift factors obtained from the creep and DSC data. The temperature dependence of the nonequilibrium temperature shift factors is found to be an order of magnitude smaller than that of the equilibrium shift factors. The time scales to reach equilibrium for enthalpy and for mechanical measurements are found to be the same within experimental error. © 1995 John Wiley & Sons, Inc.