基于隐枚举法的快速分级切负荷优化方法

目前稳控装置广泛采用的穷举法已经很难满足快速、精准切负荷的要求。为了高效地求解切负荷优化问题,为紧急决策争取更多时间,提出了基于隐枚举法的快速分级切负荷优化方法。该方法协调低频和低压切负荷动作轮次,建立切负荷优化模型,通过制定合适的搜索策略和剪枝策略,仅在可行解范围内进行寻优,大大提高了计算最优解的效率。切负荷算例结果表明同等条件下该方法可以节约至少50%以上的计算时间,实现了稳控装置的快速切负荷,保证了紧急情况下电网的安全稳定运行。     

Enumerating maximal bicliques in bipartite graphs with favorable degree sequences

We propose an output-sensitive algorithm for the enumeration of all maximal bicliques in a bipartite graph, tailored to the case when the degree distribution in one partite set is very skewed. We accomplish a worst-case bound better than previously known general bounds if, e.g., the degree sequence follows a power law.     

大规模水电系统优化调度降维方法研究I:理论分析

中国水电系统规模持续扩张,使得已有方法在求解大规模水电调度问题时,存在严重维数灾及早熟收敛等不同程度局限,亟需分析已有方法以便发现其瓶颈所在,为探寻能均衡求解效率与计算精度的实用化方法提供有益参考。为此,首先深入研究了线性规划、二次规划和动态规划等多种方法的计算复杂度,然后定量对比分析了各方法在不同情景下的适用性,最后提出“四维一体可拓降维”总体思想,并给出具体的降维方法与策略,建议从空间维、时间维、状态维和组合维等4个方面开展综合研究,以切实服务于大规模水电系统优化调度的高效优质求解。     

基于 Spin/Promela 的 Woo-Lam 协议安全性质高效验证磁

形式化方法是分析验证安全协议的重要技术之一。模型检测是用在形式化方法中实现形式化自动验证的重要手段。基于 Promela 语言,将 P ．Maggi 和 R ．Sisto 提出的建模方法扩展到建立包含三个合法主体和一个攻击者的复杂模型,枚举法和打表法同时被运用在求解攻击者模型需要表示的知识项过程中,提高了协议建模效率,保证了建模准确性。以Woo-Lam 协议为例,运用 Spin 工具成功发现一个已知著名攻击。此通用方法适用于类似复杂协议形式化分析与验证。     

A deterministic sequential maximin Latin hypercube design method using successive local enumeration for metamodel-based optimization

Space-filling and projective properties of design of computer experiments methods are desired features for metamodelling. To enable the production of high-quality sequential samples, this article presents a novel deterministic sequential maximin Latin hypercube design (LHD) method using successive local enumeration, notated as sequential-successive local enumeration (S-SLE). First, a mesh-mapping algorithm is proposed to map the positions of existing points into the new hyper-chessboard to ensure the projective property. According to the maximin distance criterion, new sequential samples are generated through successive local enumeration iterations to improve the space-filling uniformity. Through a number of comparative studies, several appealing merits of S-SLE are demonstrated: (1) S-SLE outperforms several existing LHD methods in terms of sequential sampling quality; (2) it is flexible and robust enough to produce high-quality multiple-stage sequential samples; and (3) the proposed method can improve the overall performance of sequential metamodel-based optimization algorithms. Thus, S-SLE is a promising sequential LHD method for metamodel-based optimization.     

A mildly exponential approximation algorithm for the permanent

A new approximation algorithm for the permanent of ann ×n 0,1-matrix is presented. The algorithm is shown to have worst-case time complexity exp(O(n ^1/2 log² n)). Asymptotically, this represents a considerable improvement over the best existing algorithm, which has worst-case time complexity exp((n)).Supported by SERC Grant GR/F 90363; work done in part while visiting DIMACS (Center for Discrete Mathematics and Computer Science).Supported by an NSF PYI grant, with matching equipment grant from the AT&T Foundation; work done in part while visiting DIMACS.     

数独基于规则的逐步枚举算法设计

给出了数独(Sudoku)的6条性质,并在此基础上提出了6条推理规则,然后结合空格填写的一个一组,两个一组及更多个一组的枚举算法,在枚举中进行推理.使推理和枚举结合起来,对有唯一解的数独问题,其求解速度比回溯法快得多,同时也能完成许多数独软件无法进行推理计算的数独难题.用两个数独难题进行验证,表明该方法十分有效.     

An enumeration algorithm for integer‐valued data envelopment analysis

Data envelopment analysis (DEA) models assume real‐valued inputs and outputs, but on many occasions, some inputs and/or outputs can only take integer values. In these cases, using DEA models can result in misleading efficiency assessments and inaccurate performance targets. In this paper, we propose an enumeration algorithm for computing efficiency scores and performance targets of decision‐making units with integer value inputs/outputs. In the presented algorithm, we do not use any of the mixed integer linear programming (MILP) models that are used in previous studies. We show that the result of our algorithm and that of the MILP model presented in this context is the same. We also generalize our algorithm for different types of returns to scale as well as for the hybrid setting with real‐valued data.     

Improved methods for extracting frequent itemsets from interim‐support trees

Mining association rules in relational databases is a significant computational task with lots of applications. A fundamental ingredient of this task is the discovery of sets of attributes (itemsets) whose frequency in the data exceeds some threshold value. In this paper we describe two algorithms for completing the calculation of frequent sets using a tree structure for storing partial supports, called interim‐support (IS) tree. The first of our algorithms (T‐Tree‐First (TTF)) uses a novel tree pruning technique, based on the notion of (fixed‐prefix) potential inclusion, which is specially designed for trees that are implemented using only two pointers per node. This allows to implement the IS tree in a space‐efficient manner. The second algorithm (P‐Tree‐First (PTF)) explores the idea of storing the frequent itemsets in a second tree structure, called the total support tree (T‐tree); the main innovation lies in the use of multiple pointers per node, which provides rapid access to the nodes of the T‐tree and makes it possible to design a new, usually faster, method for updating them. Experimental comparison shows that these techniques result in considerable speedup for both algorithms compared with earlier approaches that also use IS trees (Principles of Data Mining and Knowledge Discovery, Proceedings of the 5th European Conference, PKDD, 2001, Freiburg, September 2001 (Lecture Notes in Artificial Intelligence, vol. 2168). Springer: Berlin, Heidelberg, 54–66; Journal of Knowledge‐Based Syst. 2000; 13 :141–149). Further comparison between the two new algorithms, shows that the PTF is generally faster on instances with a large number of frequent itemsets, provided that they are relatively short, whereas TTF is more appropriate whenever there exist few or quite long frequent itemsets; in addition, TTF behaves well on instances in which the densities of the items of the database have a high variance. Copyright © 2008 John Wiley & Sons, Ltd.     

Reachability determination in acyclic Petri nets by cell enumeration approach

Reachability is one of the most important behavioral properties of Petri nets. We propose in this paper a novel approach for solving the fundamental equation in the reachability analysis of acyclic Petri nets, which has been known to be NP-complete. More specifically, by adopting a revised version of the cell enumeration method for an arrangement of hyperplanes in discrete geometry, we develop an efficient solution scheme to identify firing count vector solution(s) to the fundamental equation on a bounded integer set, with a complexity bound of O((nu)^n−m), where n is the number of transitions, m is the number of places and u is the upper bound of the number of firings for all individual transitions.