应急预案响应程序模块化研究

应急响应程序是应急预案的重要组成部分,通过按照一定逻辑关系构成的行动网络图对响应过程进行可视化与数字化,应急响应程序模块化就是试图将行动间逻辑关系稳定且在多个程序中多次出现的“子网络”提取出来,作为响应程序模块,在以后的应用中,根据实际需要直接调用模块,通过模块之间的重新组合,增加制定新应急响应程序的效率。为此,文章在定义了行动间紧密度和模块代表性的基础上,以模块内行动间紧密度之和与模块代表性之和最大化为目标,满足一个行动仅能存在与一个模块的约束下,建立数学规划模型,以蚁群算法为基础设计启发式算法,最后对航空公司多个应急响应程序进行模块化,说明该方法的有效性。     

Adaptive sample size and importance sampling in estimation-based local search for the probabilistic traveling salesman problem

The probabilistic traveling salesman problem is a paradigmatic example of a stochastic combinatorial optimization problem. For this problem, recently an estimation-based local search algorithm using delta evaluation has been proposed. In this paper, we adopt two well-known variance reduction procedures in the estimation-based local search algorithm: the first is an adaptive sampling procedure that selects the appropriate size of the sample to be used in Monte Carlo evaluation; the second is a procedure that adopts importance sampling to reduce the variance involved in the cost estimation. We investigate several possible strategies for applying these procedures to the given problem and we identify the most effective one. Experimental results show that a particular heuristic customization of the two procedures increases significantly the effectiveness of the estimation-based local search.     

An algorithm for polygon placement using a bottom-left strategy

This paper describes a fast and efficient implementation of a bottom-left (BL) placement algorithm for polygon packing. The algorithm allows pieces to be nested within the partial layout produced by previously placed pieces, and produces an optimal BL layout in the sense that the positions considered are guaranteed to contain the bottom-left position of the infinite set of possibilities. Full details of the way in which these positions are calculated are given. Computational experiments comparing the results of different orderings on a variety of datasets from the literature are reported, and these illustrate that problems having in excess of 100 pieces of several piece types can be solved within one minute on a modern desktop PC. The procedure can easily be incorporated into algorithms that apply more sophisticated piece selection procedures.     

A unified exact method for solving different classes of vehicle routing problems

This paper presents a unified exact method for solving an extended model of the well-known Capacitated Vehicle Routing Problem (CVRP), called the Heterogenous Vehicle Routing Problem (HVRP), where a mixed fleet of vehicles having different capacities, routing and fixed costs is used to supply a set of customers. The HVRP model considered in this paper contains as special cases: the Single Depot CVRP, all variants of the HVRP presented in the literature, the Site-Dependent Vehicle Routing Problem (SDVRP) and the Multi-Depot Vehicle Routing Problem (MDVRP). This paper presents an exact algorithm for the HVRP based on the set partitioning formulation. The exact algorithm uses three types of bounding procedures based on the LP-relaxation and on the Lagrangean relaxation of the mathematical formulation. The bounding procedures allow to reduce the number of variables of the formulation so that the resulting problem can be solved by an integer linear programming solver. Extensive computational results over the main instances from the literature of the different variants of HVRPs, SDVRP and MDVRP show that the proposed lower bound is superior to the ones presented in the literature and that the exact algorithm can solve, for the first time ever, several test instances of all problem types considered.      

A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem

This paper presents a genetic algorithm for solving the resource-constrained project scheduling problem. The innovative component of the algorithm is the use of a magnet-based crossover operator that can preserve up to two contiguous parts from the receiver and one contiguous part from the donator genotype. For this purpose, a number of genes in the receiver genotype absorb one another to have the same order and contiguity they have in the donator genotype. The ability of maintaining up to three contiguous parts from two parents distinguishes this crossover operator from the powerful and famous two-point crossover operator, which can maintain only two contiguous parts, both from the same parent. Comparing the performance of the new procedure with that of other procedures indicates its effectiveness and competence.     

Sparse principal component analysis subject to prespecified cardinality of loadings

Most of the existing procedures for sparse principal component analysis (PCA) use a penalty function to obtain a sparse matrix of weights by which a data matrix is post-multiplied to produce PC scores. In this paper, we propose a new sparse PCA procedure which differs from the existing ones in two ways. First, the new procedure does not sparsify the weight matrix. Instead, the so-called loadings matrix is sparsified by which the score matrix is post-multiplied to approximate the data matrix. Second, the cardinality of the loading matrix i.e., the total number of nonzero loadings, is pre-specified to be an integer without using penalty functions. The procedure is called unpenalized sparse loading PCA (USLPCA). A desirable property of USLPCA is that the indices for the percentages of explained variances can be defined in the same form as in the standard PCA. We develop an alternate least squares algorithm for USLPCA which uses the fact that the PCA loss function can be decomposed as a sum of a term irrelevant to the loadings, and another one being easily minimized under cardinality constraints. A procedure is also presented for selecting the best cardinality using information criteria. The procedures are assessed in a simulation study and illustrated with real data examples.     

A new multi-objective discrete robust optimization algorithm for engineering design

This paper proposes a novel multi-objective discrete robust optimization (MODRO) algorithm for design of engineering structures involving uncertainties. In the present MODRO procedure, grey relational analysis (GRA), coupled with principal component analysis (PCA), was used as a multicriteria decision making model for converting multiple conflicting objectives into one unified cost function. The optimization process was iterated using the successive Taguchi approach to avoid the limitation that the conventional Taguchi method fails to deal with a large number of design variables and design levels. The proposed method was first verified by a mathematical benchmark example and a ten-bar truss design problem; and then it was applied to a more sophisticated design case of full scale vehicle structure for crashworthiness criteria. The results showed that the algorithm is able to achieve an optimal design in a fairly efficient manner attributable to its integration with the multicriteria decision making model. Note that the optimal design can be directly used in practical applications without further design selection. In addition, it was found that the optimum is close to the corresponding Pareto frontier generated from the other approaches, such as the non-dominated sorting genetic algorithm II (NSGA-II), but can be more robust as a result of introduction of the Taguchi method. Due to its independence on metamodeling techniques, the proposed algorithm could be fairly promising for engineering design problems of high dimensionality.     

Approximation Algorithms for MAX 4-SAT and Rounding Procedures for Semidefinite Programs

Karloff and Zwick obtained recently an optimal 7/8-approximation algorithm for MAX 3-SAT. In an attempt to see whether similar methods can be used to obtain a 7/8-approximation algorithm for MAX SAT, we consider the most natural generalization of MAX 3-SAT, namely MAX 4-SAT. We present a semidefinite programming relaxation of MAX 4-SAT and a new family of rounding procedures that try to cope well with clauses of various sizes. We study the potential, and the limitations, of the relaxation and of the proposed family of rounding procedures using a combination of theoretical and experimental means. We select two rounding procedures from the proposed family of rounding procedures. Using the first rounding procedure we seem to obtain an almost optimal 0.8721-approximation algorithm for MAX 4-SAT. Using the second rounding procedure we seem to obtain an optimal 7/8-approximation algorithm for satisfiable instances of MAX 4-SAT. On the other hand, we show that no rounding procedure from the family considered can be shown, using the current techniques, to yield an approximation algorithm for MAX 4-SAT whose performance guarantee for all instances of the problem is greater than 0.8724. We also show that the integrality ratio of the proposed relaxation, as a relaxation of MAX {1, 4}-SAT, is at most 0.8754.The 0.8721-approximation for MAX 4-SAT that we seem to obtain substantially improves the performance guarantees of all previous algorithms suggested for the problem. It is extremely close to being optimal as a (7/8 + ε)-approximation algorithm for MAX 4-SAT, for any fixed ε > 0, would imply that P = NP. Our investigation also indicates, however, that additional ideas are required in order to obtain optimal 7/8-approximation algorithms for MAX 4-SAT and MAX SAT.Although most of this paper deals specifically with the MAX 4-SAT problem, we believe that the new family of rounding procedures introduced and the methodology used in the design and in the analysis of the various rounding procedures considered have a much wider range of applicability.     

On the optimality of the greedy solutions of the general knapsack problems

Summary: In this paper we submit a unified discussion of some closely related results which were achieved independently in number theory and integer programming, and we partially generalize them. In the unified discussion we treat together two problems where the greedy method has different characters, in the first one it is an internal-point algorithm, in the second one it is an outer-point method. We call a knapsack problem "pleasant" if the greedy solution is optimal for every right-hand side. A sufficient and two finite necessary and sufficient conditions for the pleasantness of a problem are discussed. The sufficient condition can be checked very easily. The paper is finished with an error analysis of some nonpleasant problems     

Reconstruction of possibilistic behavior systems

Reconstructability analysis is viewed as a process of investigating the possibilities of reconstructing desirable properties of overall systems from the knowledge of the corresponding properties of their various subsystems. The reconstructability analysis consists of procedures for generating meaningful reconstruction hypotheses, procedures for the evaluation of the reconstruction hypotheses, and procedures for making various decisions regarding the acceptance of evaluated reconstruction hypotheses, generation of additional reconstruction hypotheses, termination of the analysis and the like.The paper discusses the evaluation of reconstruction hypotheses when the systems under consideration are possibilistic behavior systems. It is shown that a principle of maximum ambiguity, similar to the principle of maximum entropy for probabilistic systems, can be used for possibilistic systems. It is also shown that the unbiased (maximum ambiguity) reconstruction can be determined by a simple join procedure, in a similar fashion as for probabilistic systems. The join procedure for possibilistic systems turns out to be computationally simpler than the one for probabilistic systems. The paper also describes a general procedure for determining the reconstruction family.     

A branch-and-cut algorithm for the equicut problem

We describe an algorithm for solving the equicut problem on complete graphs. The core of the algorithm is a cutting-plane procedure that exploits a subset of the linear inequalities defining the convex hull of the incidence vectors of the edge sets that define an equicut. The cuts are generated by several separation procedures that will be described in the paper. Whenever the cutting-plane procedure does not terminate with an optimal solution, the algorithm uses a branch-and-cut strategy. We also describe the implementation of the algorithm and the interface with the LP solver. Finally, we report on computational results on dense instances with sizes up to 100 nodes.     

考虑传输容量的通信网端到端可靠性指标算法

归一化传输容量加权通信网端到端可靠性指标,非常适合评价现代高速宽带通信网络.然而计算全过程易于在计算机上编程实现的算法尚未见到.研究出一整套可靠性指标的计算方法.由于,从路由计算、不交化网络状态集及其对应容量的求取,到最后获得可靠性指标结果等各个环节,均实现了代数化或逻辑代数化运算,因此,整套算法易于编写计算机程序.详细介绍了算法各环节的计算规则与步骤,并对正确性与合理性进行了论证.通过举例详细说明算法的计算过程,并检验算法的正确性.     

Hybrid chaos control of continuous unified chaotic systems using discrete rippling sliding mode control

In this paper, a new systematic design procedure to stabilize continuous unified chaotic systems based on discrete sliding mode control (DSMC) is presented. In contrast to the previous works, the concept of rippling control is newly introduced such that the design of DSMC can be simplified and only a single controller is needed to realize chaos suppression. As expected, under the proposed DSMC law, the unified system can be stabilized in a manner of ripple effect, even when the external uncertainty is present. Last, two examples are included to illustrate the effectiveness of the proposed rippling DSMC developed in this paper.     

A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: Multi-agent scheduling problems

Most classical scheduling research assumes that the objectives sought are common to all jobs to be scheduled. However, many real-life applications can be modeled by considering different sets of jobs, each one with its own objective(s), and an increasing number of papers addressing these problems has appeared over the last few years. Since so far the area lacks a unified view, the studied problems have received different names (such as interfering jobs, multi-agent scheduling, and mixed-criteria), some authors do not seem to be aware of important contributions in related problems, and solution procedures are often developed without taking into account existing ones. Therefore, the topic is in need of a common framework that allows for a systematic recollection of existing contributions, as well as a clear definition of the main research avenues. In this paper we review multicriteria scheduling problems involving two or more sets of jobs and propose an unified framework providing a common definition, name and notation for these problems. Moreover, we systematically review and classify the existing contributions in terms of the complexity of the problems and the proposed solution procedures, discuss the main advances, and point out future research lines in the topic.     

A ROBUST SUPERLINEARLY CONVERGENT ALGORITHM FOR LINEARLY CONSTRAINED OPTIMIZATION PROBLEMS UNDER DEGENERACY

1.IntroductionTheproblemconsideredinthispaperiswhereX={xER"laTx5hi,jEI={l,.'.,m}},ajeR"(jEI)areallcolumn*ThisresearchissupportedbytheNationalNaturalSciencesFoundationofChinaandNaturalSciencesFoundationofHunanProvince.vectors,hiERI(j6I)areallscalars,andf:R"-- Risacontinuouslydifferentiablefunction.Weonlyconsiderinequalityconstraintsheresinceanyequalitycanbeexpressedastwoinequalities.Withoutassumingregularityofthelinearconstraints,thereisnotanydifficultyinextendingtheresultstothegenera…     

A general theory on spectral properties of state-homogeneous finite-state quasi-birth–death processes

In this paper a spectral theory pertaining to Quasi-Birth–Death Processes (QBDs) is presented. The QBD, which is a generalization of the birth–death process, is a powerful tool that can be utilized in modeling many stochastic phenomena. Our theory is based on the application of a matrix polynomial method to obtain the steady-state probabilities in state-homogeneous finite-state QBDs. The method is based on finding the eigenvalue–eigenvector pairs that solve a matrix polynomial equation. Since the computational effort in the solution procedure is independent of the cardinality of the counting set, it has an immediate advantage over other solution procedures. We present and prove different properties relating the quantities that arise in the solution procedure. By also compiling and formalizing the previously known properties, we present a formal unified theory on the spectral properties of QBDs, which furnishes a formal framework to embody much of the previous work. This framework carries the prospect of furthering our understanding of the behavior the modeled systems manifest.     

A boundary only procedure for time-dependent diffusion equations

In the recent literature, the boundary element method (BEM) is extensively used to solve time-dependent partial differential equations. However, most of these formulations yield algorithms where one has to include all interior points in the computation process if finite difference procedures are used to approximate the temporal derivative. This obviously restricts the advantages of the BEM, which is mainly considered to be a boundary only algorithm for time-independent problems. A new algorithm is demonstrated here, which extends the boundary only nature of the method to time-dependent partial differential equations. Using this procedure, one can reduce the finite difference time integration algorithm, generated in a standard manner, to a boundary only process. The proposed method is demonstrated with considerable success for diffusion problems. Results obtained in these applications are presented comparatively with analytical and other boundary element time integration procedures. The algorithm proposed may utilize several coordinate functions in the secondary reduction phase of the formulation. A summary of such functions is described here and performances of these functions are tested and compared in three applications. It is shown that some coordinate functions perform better than others under certain conditions. Using these results, we propose a general coordinate function, which may be used with satisfactory results in all parabolic partial differential equation applications.     

A note on mixed procedures for decomposing linear programming problems

This paper shows how to combine primal and dual decomposition procedures where both a vertical and a horizontal decomposition approach can be applied. The motivation for using a mixed procedure is that it improves the possibility of efficiently initializing the procedure, which has been shown to be crucial for the convergence of the procedures, Additionally mixed procedures have important interpretations as mixed price and budget planning procedures for decentralized organizations.     

Models and a genetic algorithm for static aircraft-gate assignment problem

Assigning aircraft to available gates at an airport can have a major impact on the efficiency of flight schedules and on the level of passenger satisfaction with the service. Unexpected changes, due to air traffic delays, severe weather conditions, or equipment failures, may disrupt the initial assignments and compound the difficulty of maintaining smooth station operations. Recently, mathematical models and procedures (optimal and heuristic) have been proposed to provide solutions with minimum dispersion of idle time periods for static aircraft-gate assignment problems. This paper introduces a unified framework to specifically treat the objective functions of the previous models. It also provides linear representations of these models and identifies the conditions under which the optimal solutions can be obtained in polynomial time. Furthermore, a genetic algorithm utilizing problem specific knowledge is proposed to provide effective alternative solutions.