Parallel branch-and-bound search in Parlog

The concurrent logic languages, of which Parlog is one, have been promoted as a new generation of software languages specifically designed for parallel programming. This paper investigates their application to a search problem commonly used as an illustration of artificial intelligence techniques, the 8-puzzle. It notes that programs written in the concurrent logic languages which do not pay attention to the parallelism can fall into two possible traps: either there is little real parallelism in them due to data dependencies, or there is too much parallelism and any practical architecture will be overwhelmed. A solution which controls the parallelism using user-defined priorities is proposed. This solution has the advantage of being architecture-independent.     

Integrating integer programming and probabilistic deduction graphs for probabilistic reasoning

Optimal solutions of several variants of the probabilistic reasoning problem were found by a new technique that integrates integer programming and probabilistic deduction graphs (PDG). PDGs are extended from deduction graphs of the and-type via normal deduction graphs. The foregoing variants to be solved can involve multiple hypotheses and multiple evidences where the former is given and the latter is unknown and being found or vice versa. The relationship among these hypotheses and evidences with possible intermediaries is represented by a causal graph. The proposed method can handle a large causal graph of any type and find an optimal solution by invoking a linear integer programming package. In addition, formulating the reasoning problem to fit integer programming takes a polynomial time. H.-L. Li was visiting the Department of Computer Sciences, University of North Texas in 1988–1989. He is with the Institute of Information Management, National Chiao Tung University, Hsinchu, Taiwan, R.O.C.     

分布系统中多米诺效应的分析与消除

分布系统中发生故障后,错误信息在进程间的传播,以及由此引起的系统恢复过程中的多米诺效应是分布系统容错恢复技术所面临的最重要与最困难的问题.目前各种研究工作偏重于具体的系统动态恢复技术.本文的研究重点在于首次揭示多米诺效应本身固有的数量特征及其与分布系统技术参数间的联系,给出多米诺效应动态消除技术,引入系统额外开销的下限,并针对动态技术的缺点,探讨多米诺效应的静态消除技术,为解决困难开辟新途径.     

Partitioning multiple objective optimal solutions with applications in radiotherapy design

The optimal partition for linear programming is induced by any strictly complementary solution, and this partition is important because it characterizes the optimal set. However, constructing a strictly complementary solution in the presence of degeneracy was not practical until interior point algorithms became viable alternatives to the simplex algorithm. We develop analogs of the optimal partition for linear programming in the case of multiple objectives and show that these new partitions provide insight into the optimal set (both pareto optimality and lexicographic ordering are considered). Techniques to produce these optimal partitions are provided, and examples from the design of radiotherapy plans show that these new partitions are useful. A. Holder. Research conducted at Trinity University, TX, and The University of Mississippi, MS. This research was partially supported by ONR Grant N00014-01-1-0917.     

New approaches for error estimation and adaptivity for 2D potential boundary element methods

This work presents two new error estimation approaches for the BEM applied to 2D potential problems. The first approach involves a local error estimator based on a gradient recovery procedure in which the error function is generated from differences between smoothed and non‐smoothed rates of change of boundary variables in the local tangential direction. The second approach involves the external problem formulation and gives both local and global measures of error, depending on a choice of the external evaluation point. These approaches are post‐processing procedures. Both estimators show consistency with mesh refinement and give similar qualitative results. The error estimator using the gradient recovery approach is more general, as this formulation does not rely on an ‘optimal’ choice of an external parameter. This work presents also the use of a local error estimator in an adaptive mesh refinement procedure. This r‐refinement approach is based on the minimization of the standard deviation of the local error estimate. A non‐linear programming procedure using a feasible‐point method is employed using Lagrange multipliers and a set of active constraints. The optimization procedure produces finer meshes close to a singularity and results that are consistent with the problem physics. Copyright © 2002 John Wiley & Sons, Ltd.     

Empirical modelling of shear strength of RC deep beams by genetic programming

This paper investigates the feasibility of using genetic programming (GP) to create an empirical model for the complicated non-linear relationship between various input parameters associated with reinforced concrete (RC) deep beams and their ultimate shear strength. GP is a relatively new form of artificial intelligence, and is based on the ideas of Darwinian theory of evolution and genetics. The size and structural complexity of the empirical model are not specified in advance, but these characteristics evolve as part of the prediction. The engineering knowledge on RC deep beams is also included in the search process through the use of appropriate mathematical functions.The model produced by GP is constructed directly from a set of experimental results available in the literature. The validity of the obtained model is examined by comparing its response with the shear strength of the training and other additional datasets. The developed model is then used to study the relationships between the shear strength and different influencing parameters. The predictions obtained from GP agree well with experimental observations.     

点胶机离线编程软件的设计与开发

SMT设备要达到最大的产量，必须要考虑生产线的效率。点胶机是SMT生产线中的重要设备，因此提高点胶机的生产效率具有十分重要的意义。本文以CAMALOT 5000系统为例，介绍了点胶机离线编程软件的设计与开发中的思想、方法和经验，本文着重探讨了坐标数据的处理和转换，同时针对基于点胶系统优化的TSP问题进行了分析和研究，对程序优化进行了系统分析设计，并编程实现了基本方案。最后在CAMALOT 5000系统上使用本解决方案，大幅度提高了生产效率，证明了本解决方案的优越性和高效性，也为其他SMT设备的离线编程软件的设计提供了一种可参考的思路。     

间歇式液相本体聚丙烯装置计算机控制与管理系统

介绍一种间歇式液相本体聚丙烯装置计算机先进控制与管理系统。它是由“基本控制层”和“上位控制层”构成的经济适用型集散控制装置。该装置采用了多屏显示技术、网络通讯技术、PLC程控技术、ActiveX控件技术和面向对象程序设计方法、数据库技术以及闭环辩识、预测控制、反应优化、底层PID控制与上层先进控制无扰动自动切换等多种技术和控制方式，因而可以灵活有效地实现聚合反应的全过程自动化生产和安全保护。     

A globally convergent algorithm for transportation continuous network design problem

The continuous network design problem (CNDP) is characterized by a bilevel programming model, in which the upper level problem is generally to minimize the total system cost under limited expenditure, while at the lower level the network users make choices with regard to route conditions following the user equilibrium principle. In this paper, the bilevel programming model for CNDP is transformed into a single level convex programming problem by virtue of an optimal-value function tool and the relationship between System Optimum (SO) and User Equilibrium (UE). By exploring the inherent nature of the CNDP, the optimal-value function for the lower level user equilibrium problem is proved to be continuously differentiable and its derivative in link capacity enhancement can be obtained efficiently by implementing user equilibrium assignment subroutine. However, the reaction (or response) function between the upper and lower level problem is implicit and its gradient is difficult to obtain. Although, here we approximately express the gradient with the difference concept at each iteration, based on the method of successive averages (MSA), we propose a globally convergent algorithm to solve the single level convex programming problem. Comparing with widely used heuristic algorithms, such as sensitivity analysis based (SAB) method, the proposed algorithm needs not strong hypothesis conditions and complex computation for the inverse matrix. Finally, a numerical example is presented to compare the proposed method with some existing algorithms.     

A branch-and-price algorithm to solve the molten iron allocation problem in iron and steel industry

The molten iron allocation problem (MIAP) is to allocate molten iron from blast furnaces to steel-making furnaces. The allocation needs to observe the release times of the molten iron defined by the draining plan of the blast furnaces and the transport time between the iron-making and steel-making stages. Time window constraints for processing the molten iron must be satisfied to avoid freezing. The objective is to find a schedule with minimum total weighted completion time. This objective reflects the practical consideration of improving steel-making efficiency and reducing operation cost caused by the need for reheating. Such a problem can be viewed as a parallel machine scheduling problem with time windows which is known to be NP-hard. In this paper, we first formulate the molten iron allocation problem as an integer programming model and then reformulate it as a set partitioning model by applying the Dantzig–Wolfe decomposition. We solve the problem using a column generation-based branch-and-price algorithm. Since the subproblem of column generation is still NP-hard, we propose a state-space relaxation-based dynamic programming algorithm for the subproblem. Computational experiments demonstrate that the proposed algorithm is capable of solving problems with up to 100 jobs to optimality within a reasonable computation time.