Fast,effective heuristics for the 0–1 multi-dimensional knapsack problem

The objective of the multi-dimensional knapsack problem (MKP) is to find a subset of items with maximum value that satisfies a number of knapsack constraints. Solution methods for MKP, both heuristic and exact, have been researched for several decades. This paper introduces several fast and effective heuristics for MKP that are based on solving the LP relaxation of the problem. Improving procedures are proposed to strengthen the results of these heuristics. Additionally, the heuristics are run with appropriate deterministic or randomly generated constraints imposed on the linear relaxation that allow generating a number of good solutions. All algorithms are tested experimentally on a widely used set of benchmark problem instances to show that they compare favourably with the best-performing heuristics available in the literature.     

Qualitative Scene Interpretation Using Planar Surfaces

Our aim is to provide an autonomous vehicle moving into an indoor environment with a visual system to perform a qualitative 3D structure reconstruction of the surrounding environment by recovering the different planar surfaces present in the observed scene.The method is based on qualitative detection of planar surfaces by using projective invariant constraints without the use of depth estimates. The goal is achieved by analyzing two images acquired by observing the scene from two different points of view. The method can be applied to both stereo images and motion images.Our method recovers planar surfaces by clustering high variance interest points whose cross ratio measurements are preserved in two different perspective projections. Once interest points are extracted from each image, the clustering process requires to grouping corresponding points by preserving the cross ratio measurements.We solve the twofold problem of finding corresponding points and grouping the coplanar ones through a global optimization approach based on matching of high relational graphs and clustering on the corresponding association graph through a relaxation labeling algorithm.Through our experimental tests, we found the method to be very fast to converge to a solution, showing how higher order interactions, instead to giving rise to a more complex problem, help to speed-up the optimization process and to reach at same time good results.     

A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem

This paper addresses the one-machine scheduling problem with earliness-tardiness penalties. We propose a new branch-and-bound algorithm that can solve instances with up to 50 jobs and that can solve problems with even more general non-convex cost functions. The algorithm is based on the combination of a Lagrangean relaxation of resource constraints and new dominance rules.     

基于Euler-Bernoulli方程微悬臂梁弛豫分析

为探讨微机电系统中悬臂梁结构弛豫动力学特性,本文基于Euler-Bernoulli方程,计入空气滑膜阻尼对悬臂梁弛豫过程的影响,采用分离变量法导出悬臂梁挠度弛豫表达式;给出临界阻尼、过阻尼、欠阻尼梁挠度弛豫算例;利用ANSYS中瑞利阻尼模型对微悬臂梁临界阻尼、过阻尼、欠阻尼弛豫进行仿真,挠度弛豫过程在梁固定端附近与理论差异较大,仿真数据与理论偏差随挠度增加.     

Pseudo-transient continuation-based variable relaxation solver in nonlinear magnetohydrodynamic simulations

Efficient and robust Variable Relaxation Solver, based on pseudo-transient continuation, is developed to solve nonlinear anisotropic thermal conduction arising from fusion plasma simulations. By adding first- and/or second-order artificial time derivatives to the system, this type of method advances the resulting time-dependent nonlinear PDEs to steady state, which is the solution to be sought. In this process, only the stiffness matrix itself is involved so that the numerical complexity and errors can be greatly reduced. In fact, this work is an extension of integrating efficient linear elliptic solvers for fusion simulation on Cray X1E. Two schemes are derived in this work, first- and second-order variable relaxations. Four factors are observed to be critical for efficiency and preservation of solution's symmetric structure arising from periodic boundary condition: refining meshes in different coordinate directions, initializing nonlinear process, varying time steps in both temporal and spatial directions, and accurately generating nonlinear stiffness matrix. First finer mesh scale should be taken in strong transport direction; next the system is carefully initialized by the solution with linear conductivity; third, time step and relaxation factor are vertex-based varied and optimized at each time step; finally, the nonlinear stiffness matrix is updated by just scaling corresponding linear one with the vector generated from nonlinear thermal conductivity.     

锆钛酸铅95/5薄膜的介电性能与弛豫特征

采用溶胶-凝胶法制备锆钛酸铅95/5（PZT95/5）薄膜,通过分析介电温度谱、介电频谱研究薄膜的介电性能.研究结果表明：介电常数-温度曲线ε（T）的相变峰随着频率的增加而逐渐变得平坦.同时,介电常数倒数与温度曲线ε-1（T）在高频不符合居里外斯定律;采用普适弛豫定律公式,对不同温度下的介电频谱曲线ε（f）进行拟合,得到弥散系数随着温度的变化曲线,该曲线在铁电-顺电转变以及反铁电-铁电转变这两个特征温度附近出现异常,结合材料反铁电-铁电-顺电相变的微观结构变化规律对此现象进行了讨论.     

行车和温度荷载作用下沥青路面的松弛响应分析

目的研究沥青混凝土路面在行车和温度荷载作用下的松弛特性,更好地做到防裂控制工作．方法确定黏弹性材料参数及能够反应温度、沥青混合料黏弹性本构关系,建立典型的路面结构三维有限元模型,模拟面层材料在不同初始变形的应力状态,分析路表弯沉、沥青面层层底和土基顶面的响应．结果沥青路面在荷栽和温度作用下,面层黏弹性材料会使路面应力减小．面层层底和基层层底应力会发生松弛,最后趋于稳定值;在行车载荷作用下弯沉会随着时间的推移发生回弹,最后逐渐趋于稳定．结论松弛是材料本身属性与其他因素无关;应力松弛模量越小,松弛性能越好,低温抗裂性越好．     

解线性方程组的迭代方法研究

用求解线性方程组的多参数投影法推出Jacobi迭代法和Gauss-Seidel迭代法,并指出了松弛迭代法和Gauss-Seidel迭代法的内在联系.从最优化的观点分析了Jacobi迭代法收敛速度较慢的原因,即其下降矩阵与步长向量两者并非最优组合.并对Jacobi迭代法,Gauss-Seidel迭代法具有相当的收敛速度给出了合理的解释.