A comparative runtime analysis of heuristic algorithms for satisfiability problems

The satisfiability problem is a basic core NP-complete problem. In recent years, a lot of heuristic algorithms have been developed to solve this problem, and many experiments have evaluated and compared the performance of different heuristic algorithms. However, rigorous theoretical analysis and comparison are rare. This paper analyzes and compares the expected runtime of three basic heuristic algorithms: RandomWalk, (1+1) EA, and hybrid algorithm. The runtime analysis of these heuristic algorithms on two 2-SAT instances shows that the expected runtime of these heuristic algorithms can be exponential time or polynomial time. Furthermore, these heuristic algorithms have their own advantages and disadvantages in solving different SAT instances. It also demonstrates that the expected runtime upper bound of RandomWalk on arbitrary k-SAT (k?3) is O(n(k−1)), and presents a k-SAT instance that has Θ(n(k−1)) expected runtime bound.     

Solving Third Order Differential Equations with Maximal Symmetry Group

The largest group of Lie symmetries that a third-order ordinary differential equation (ode) may allow has seven parameters. Equations sharing this property belong to a single equivalence class with a canonical representative v ^′′′(u)=0. Due to this simple canonical form, any equation belonging to this equivalence class may be identified in terms of certain constraints for its coefficients. Furthermore a set of equations for the transformation functions to canonical form may be set up for which large classes of solutions may be determined algorithmically. Based on these steps a solution algorithm is described for any equation with this symmetry type which resembles a similar scheme for second order equations with projective symmetry group. Received March 9, 2000; revised June 8, 2000     

A characterization of span program size and improved lower bounds for monotone span programs

We give a characterization of span program size by a combinatorial-algebraic measure. The measure we consider is a generalization of a measure on covers which has been used to prove lower bounds on formula size and has also been studied with respect to communication complexity.?In the monotone case our new methods yield lower bounds for the monotone span program complexity of explicit Boolean functions in n variables over arbitrary fields, improving the previous lower bounds on monotone span program size. Our characterization of span program size implies that any matrix with superpolynomial separation between its rank and cover number can be used to obtain superpolynomial lower bounds on monotone span program size. We also identify a property of bipartite graphs that is suficient for constructing Boolean functions with large monotone span program complexity. Received: September 30, 2000.     

车门LIN网络通信程序设计

介绍了轿车车门LIN网络基本结构,LIN总线的主/从节点采用MC68HC908GZ60/MC68HC908QL4,阐明了基于ESCI/SLIC模块的LIN主/从节点软件设计流程,编写了主、从节点的LIN通信程序.实践证明,该程序运行正常、可靠,为车门控制系统顺利实现提供可靠的保障.     

A reactive GRASP and path relinking for a combined production–distribution problem

An NP-hard production–distribution problem for one product over a multi-period horizon is investigated. The aim is to minimize total cost taking production setups, inventory levels and distribution into account. An integer linear model is proposed as a compact problem specification but it cannot be solved to optimality for large instances. Instead of using a classical two-phase approach (production planning and then route construction for each day), metaheuristics that simultaneously tackle production and routing decisions are developed: a GRASP (greedy randomized adaptive search procedure) and two improved versions using either a reactive mechanism or a path-relinking process. These algorithms are evaluated on 90 randomly generated instances with 50, 100 and 200 customers and 20 periods. The results confirm the interest of integrating production and distribution decisions, compared to classical two-phase methods. Moreover, reaction and path-relinking give better results than the GRASP alone.     

Limitations of nonlinear discrete periodic control for disturbance attenuation and robust stabilization

This paper presents a performance analysis of nonlinear periodically time-varying discrete controllers acting upon a linear time-invariant discrete plant. Time-invariant controllers are distinguished from strictly periodically time-varying controllers. For a given nonlinear periodic controller, a time-invariant controller is constructed. Necessary and sufficient conditions are given under which the time-invariant controller gives strictly better control performance than the time-invariant controller from which it was obtained, for the attenuation of l_p exogenous disturbances and the robust stabilization of l_p unstructured perturbations, for all p[1,∞].     

Towards optimal simulations of formulas by bounded-width programs

We show that, over an arbitrary ring, for any fixed >0, all balanced algebraic formulas of sizes are computed by algebraic straight-line programs that employ a constant number of registers and have lengthO (s ¹⁺). In particular, in the special case where the ring isGF(2), we obtain a technique for simulating balanced Boolean formulas of sizes by bounded-width branching programs of lengthO(s ¹⁺), for any fixed >0. This is an asymptotic improvement in efficiency over previous simulations in both the Boolean and algebraic settings.     

凝析油自动计量测控系统的设计

从减小生产工况对凝析油计量的影响、提高计量精度出发,提出了一种集凝析油产量和含水率计量为一体的高精度计量方案,介绍了该自动计量系统测控电路及其软件的设计思路,现场运行与测试表明该自动计量系统原理正确、工作稳定、精度较高。     

基于以太网的电能计量采集装置的设计

传统的电能计量计费装置通过本地232中继、484远传、GPRS通信或者电台通信使主站用户得到实时数据,往往这些主站只和电力营销部门相关,作为电力消费结算的依据,而并没有接入到电网的调度自动化系统,这使得大用户的信息不能共享给全局调度系统.本装置通过采用以太网技术实现远动设备及系统的102规约,使其能够接入调度自动化系统,为电网调度的统筹安排提供一线大客户数据.