A problem in enumerating extreme points, and an efficient algorithm for one class of polytopes

We consider the problem of developing an efficient algorithm for enumerating the extreme points of a convex polytope specified by linear constraints. Murty and Chung (Math Program 70:27–45, 1995) introduced the concept of a segment of a polytope, and used it to develop some steps for carrying out the enumeration efficiently until the convex hull of the set of known extreme points becomes a segment. That effort stops with a segment, other steps outlined in Murty and Chung (Math Program 70:27–45, 1995) for carrying out the enumeration after reaching a segment, or for checking whether the segment is equal to the original polytope, do not constitute an efficient algorithm. Here we describe the central problem in carrying out the enumeration efficiently after reaching a segment. We then discuss two procedures for enumerating extreme points, the mukkadvayam checking procedure, and the nearest point procedure. We divide polytopes into two classes: Class 1 polytopes have at least one extreme point satisfying the property that there is a hyperplane H through that extreme point such that every facet of the polytope incident at that extreme point has relative interior point intersections with both sides of H; Class 2 polytopes have the property that every hyperplane through any extreme point has at least one facet incident at that extreme point completely contained on one of its sides. We then prove that the procedures developed solve the problem efficiently when the polytope belongs to Class 2.     

A {(\frac 4 3) -} approximation algorithm for a special case of the two machine flow shop problem with several availability constraints

In this paper, we deal with a special case of the two-machine flow shop scheduling problem with several availability constraints on the second machine, under the resumable scenario. We develop an improved algorithm with a relative worst-case error bound of 4/3.     

多相材料结构拓扑优化: 体积约束还是质量约束?

针对拓扑优化设计中多年沿用的体积约束作为控制材料用量的思路, 研究了采用质量约束开展多相材料结构拓扑优化的新方法, 提出了相应的质量约束结构优化问题模型和材料插值模型. 通过研究广义SIMP模型和对等混合模型两类多相材料属性插值方法, 发现广义SIMP插值模型导致质量约束具有复杂的非线性特征, 给优化问题的全局寻优和数值求解带来困难;采用的线性对等混合材料插值策略保证质量约束函数具有线性和变量可分离特征, 为拓扑设计问题的数值求解, 特别是凸规划寻优提供了极大便利. 算例表明多相材料插值策略和结构优化模型的正确性和有效性; 优化设计结果的比较说明了使用质量约束相对于体积约束的合理性和必要性, 阐述了质量约束在解决结构轻量化布局设计问题的有效性以及所带来的显著收益.      

含非理想空间棱柱铰的多体系统接触分析

传统的接触分析方法通过物体间的相对运动确定接触位置. 将这种方法用于多体系统中铰内的接触分析时, 无论铰内间隙是否十分微小都必须解除铰的运动学约束, 从而导致求解效率和求解精度方面的诸多弊端. 基于铰约束反力与铰内接触力之间的力系等效关系, 以及铰内可能接触点运动之间内在的运动学关系, 以矩形截面的棱柱铰为例, 提出了一种对空间棱柱铰进行摩擦接触分析的方法, 可在不解除铰的运动学约束的前提下得到铰内接触模式和接触力. 数值算例验证了方法的可行性.      

一种基于约束的指针程序路径选择方法

动态符号执行是对程序进行安全性分析的重要技术.在动态符号执行过程中,存在着符号地址,系统调用,路径选择等问题.针对符号地址导致的别名分析问题,本文提出了一种基于约束的指针分析方法,对程序进行过程内的指向分析,并对指针分析过程引入约束条件,产生可以进行路径选择的测试用例,以提高指针分析的精度.在国内首款某型号商用编译器的开发过程中实现了该方法,实验结果表明,该方法可以准确地分析C语言测试用例,缩短用例测试的时间.     

Constraints and Soliton Solutions for KdV Hierarchy and AKNS Hierarchy

It is well-known that the finite-gap solutions of the KdV equationcan be generated by its recursion operator.We generalize the result to a special form of Lax pair,from which a method to constrain the integrable system to alower-dimensional or fewer variable integrable system is proposed.A direct result is that the n-soliton solutions of the KdV hierarchy can be completely depictedby a series of ordinary differential equations (ODEs), which may be gotten by a simple but unfamiliar Lax pair. Furthermore the AKNS hierarchy is constrained to a series of univariate integrable hierarchies. The key is a special form of Lax pair for the AKNS hierarchy. It is proved that under the constraints all equations of the AKNS hierarchy are linearizable.     

Multi-Point Boundary Value Problems for Nonlinear Fourth-Order Differential Equations with All Order Derivatives

By using fixed point theorem, multiple positive solutions for some fourth-order multi-point boundary value problems with nonlinearity depending on all order derivatives are obtained. The associated Green's functions are also given.     

An Adaptive Mesh Rezoning for FSI Problems

In the problems of fluid-structure interaction (FSI) the mesh updating scheme plays a key role. We have developed an adaptive mesh rezoning technique which is applicable to the three-dimensional FSI problems. In order to prevent the inversion of elements in the mesh and to maintain a well-conditioned shape for successive time-step calculations, we introduce constrained conditions of dilatational strain in the least-square form as well as the gradient of displacement vectors, in relatively small elements. By the present mesh rezoning technique, even under the large deformation of boundaries concerned, we can reduce the use of the process of mesh generation and switching of nodal values at the interboundary of time slabs. These steps require rather significant CPU time and induced projection errors of nodal values from the previous mesh to the current one. The case of collapsing tube problems shows the remarkable potential of our method. The present method is entirely general in that it can be applied to structured and unstructured meshes, effectively.     

Solution Space Coupling in the Random K-Satisfiability Problem

The random K-satisfiability (K-SAT) problem is very difficult when the clause density is close to the satisfiability threshold. In this paper we study this problem from the perspective of solution space coupling. We divide a given difficult random K-SAT formula into two easy sub-formulas and let the two corresponding solution spaces to interact with each other through a coupling field x. We investigate the statistical mechanical property of this coupled system by mean field theory and computer simulations. The coupled system has an ergodicity-breaking (clustering) transition at certain critical value x_d of the coupling field. At this transition point, the mean overlap value between the solutions of the two solution spaces is very close to 1. The mean energy density of the coupled system at its clustering transition point is less than the mean energy density of the original K-SAT problem at the temperature-induced clustering transition point. The implications of this work for designing new heuristic K-SAT solvers are discussed.     

频率约束的三维连续体结构动力拓扑优化设计

针对频率约束和结构重量最小的动力拓扑优化问题, 基于(independent continuous mapping, ICM)独立、连续、映射方法,建立了频率约束下的三维连续体拓扑优化模型. 利用瑞利商和一阶泰勒展式对频率约束进行了显式化处理,并采用幂函数与复合指数函数作为过滤函数,将优化模型进行了标准化转换, 利用对偶理论及数学规划法进行了求解. 另外,利用质量矩阵和刚度矩阵过滤函数比值与动态约束处理了局部模态和模态交换等数值问题. 最后,通过应用两类不同过滤函数的数值算例表明了文中模型及方法在处理动力拓扑优化问题上的合理性与有效性.