Geometric approach to VLSI layout compaction

We present a new geometric approach to VLSI layout compaction in this paper. In contrast to existing compaction algorithms, we rely on the geometric method and bypass both compaction grids and constraint graphs during the entire compaction process. A systematic and efficient way is introduced to enumerate all possible jogs. For the given layout topology we prove that the geometric algorithm yields the minimum-area layout in one-dimensional compaction with automatic jog insertion. In the final output, only necessary jogs are inserted and the total wire length is minimized as a secondary goal. Furthermore, the integration of local compaction tools into a layout CAD system and the practical extensions of our algorithm are addressed.     

Optimal PMU placement considering topology constraints

A new optimization algorithm for optimal PMU configuration based on combination of graph theory and genetic algorithm is proposed. According to four topology reconstruction rules and three PMU configuration rules based on the graphic relationships between PMUs, constraints of PMU placement are put forward through topology constraint analysis, which dramatically limits the feasible solution space, thereby enhancing the algorithm speed. Meanwhile, an improved genetic algorithm based on serial number coding is presented to avoid infeasible solutions and improve the overall optimization performance. New corresponding crossover and mutation operator is also created. Examples show that the proposed algorithm performs very well and is highly valuable to large-scale networks.     

On-line adaptive optimal load flow

This paper presents a new on-line approach for solving the optimal power flow problem without sacrificing the accuracy and constraints of the system components. A procedure which merges non-linear programming (NLP) and linear programming (LP) techniques is utilized to make use of the merits of both algorithms. The NLP and LP form a closed loop with a decision maker (DM) which directs the solution algorithm either to NLP or LP according to the analysis of the permissible errors during the calculation process. The input to the closed loop is fed either from the telemetered data or the state estimator.

To adapt the LP algorithm, the objective function and the system constraints are linearized, using Taylor expansion series, around the exact solution obtained as a result of employing the NLP technique. A new linearization algorithm is presented.

The proposed approach has been applied to a 19-bus system and the results are judged satisfactory. Its use as an on-line computational tool for power system operation and control seems very promising.     

NEW IMPLEMENTATION OF THE LP ALGORTHM FOR OPTIMAL REAL POWER RESCHEDULING

ABSTRACT

A new implementation of an LP algorithm for security-constrained preventive rescheduling of real power is described. Rescheduling of generation and load (if required) is used to maintain a secure condition by avoiding line overloads. A dual linear programming formulation of the optimal rescheduling is developed. The weighted minimum deviations in real power generations and loads are chosen as the objective function in the LP formulation. Inclusion of inequality constraints on active line flow limits and equality constraint on real power generation-load balance assures a solution representing a secure system. Transmission losses are also taken into account in the constraint function. Change in customer demands can be brought into the objective function. The line losses are also brought into the optimization in the form of an equality constraint. The algorithm has options to choose selected generators or loads to take part in the optimization. The proposed method is tested on four representative power systems. These tests show very encouraging results.     

A hybrid evolutionary analogue module placement algorithm for integrated circuit layout designs

This paper presents an integrated approach of simulated annealing (SA) and genetic algorithm (GA) for the analogue module placement in mixed‐signal integrated circuit layout designs. The proposed algorithm follows the optimization flow of a normal GA controlled by the methodology of SA. The bit‐matrix chromosomal representation is employed to describe the location and the orientation of modules. Compared with the conventional bit‐string representation, the proposed chromosomal representation tends to significantly improve the search efficiency. In addition, a slide‐based flat scheme is developed to transform an absolute co‐ordinate placement of modules to a relative placement. In this way, the symmetry constraints imposed on analogue very large scale integration circuits can be easily fulfilled in the placement run. Use of a radiation‐decoder can also drastically shrink the configuration space without degrading search opportunities. The proposed algorithm has been tested with several example circuits. The experiments show this promising algorithm makes the better performance than the simpler SA or GA approaches working alone, and the quality of the automatically generated layouts is comparable to those done manually. Copyright © 2005 John Wiley & Sons, Ltd.     

Moderate loading in bit-rounding algorithms for multicarrier systems

Bit-rounding algorithms are practically attractive for their computational efficiency and suitability for integer-bit loading. However, because of the concave nature of the rate-energy relationship, these algorithms often tend to load bits aggressively, which leads to the performanceconstraint violation. In addition, for BPSK and 8-QAM cases, the anomalous behaviour of the SNR-gap rate function also contributes to the performance constraint violation of the existing bit-rounding algorithms. This paper presents an efficient moderate algorithm for estimating the optimum biasing parameter for round-off operation, using exact SNR values instead of the SNR-gap rate function in order to ensure that both the performance and total power constraints are satisfied while rate optimality is achieved. Simulation results show that the proposed moderate algorithm can maintain the optimum rate and avoid the performance constraint violation of its aggressive counterparts for 75 tested cases.     

Power system remedial action methodology

The authors address the problem of remedial-action computations for the purpose of alleviating overloads, abnormal voltages, etc. The method is based on a linear programming (LP) approach. Applications for voltage/reactive-power control, discrete capacitor/reactor switching, load transfer, and interchange control are considered. The method is optionally based on a DC or AC network model. It utilizes a number of innovations to yield an efficient computational procedure. The major innovations are: a procedure for determining coherent constraints which results in a fast identification of active constraints, fast linearization procedures for active constraints, procedures to define the region of validity of the linearized model, and a fast sparsity-coded LP algorithm. The performance of the method for large power systems is evaluated     

A fast,single-layer,area router for semi-custom analogue circuits

This paper describes the router developed for ALPS, the analogue layout prototyping system. the ALPS router employs some classic techniques and contributes a new, fast implementation of a maze-running algorithm and a new algorithm for finding two disjoint paths in a graph (the so-called ‘two path problem’). Discussion of these points is coupled with a review of existing routing algorithms and techniques, and comparisons where possible.     

基于滤波与图优化的定位与建图系统

针对室外大场景环境建图精度不高,地图出现重影和漂移等问题,提出一种融合滤波与图优化理论实时定位与建图系统。该系统由点云数据预处理、基于滤波紧耦合惯性里程计和后端位姿图优化等三部分构成。首先,点云数据预处理采用随机采样一致性算法分割地面,并提取地面模型参数构建后端优化中的地面约束因子。然后,前端紧耦合惯性里程计采用迭代误差状态卡尔曼滤波,以激光里程计作为观测值,IMU预积分结果作为预测值,通过构建联合函数,滤波融合得到较为精准的激光惯导里程计。最后,后端结合图优化理论引入闭环因子、地面约束因子以及帧与图匹配的里程计因子作为约束条件,构建因子图并优化地图位姿。其中闭环因子采用改进的扫描文本的闭环检测算法进行位置识别,可以降低环境误识别率。本文提出的算法在室外厂区楼栋,停车场以及室内车间等多个场景完成场景建图,在距离,水平和高程三个方向的累积偏差均控制10厘米左右,能够有效解决地图的重影和漂移问题,具有高鲁棒性和高精度。     

基于遗传算法的区域配电网单线图的自动布局算法

提出了一种基于遗传算法的区域配电系统单线图自动布局算法,以线路节点数目与路径差异度最小化为目标函数,引入厂站相对地理信息约束,并设计了交叉、变异算子,最后经遗传算法对节点布局进行寻优;在布线过程中,通过网格状态的数值化,采用线路路径试探、交叉重叠判定、调整的布局策略进行节点之间布线。仿真结果证明算法能使节点在图中均匀分布,走线美观清晰,计算效率和图形效果都能满足工程实用要求。     

考虑相邻时段投切次数约束的动态无功优化启发式策略

在开关日动作次数约束基础上,考虑分接头挡位的相邻时段动作次数约束,建立了一种更加实用的动态无功优化新模型。按照"先投先切、后投后切"原则,将同一母线的多个电容器组等效为1个集中变量,并根据其中的电容器组个数来确定等效变量的动态约束值。由此,既满足了电容器的实际动态约束,又减小了模型的变量规模。在求解动态无功优化问题时,以混合智能算法为基础,提出处理动态约束的启发式调整策略,采用稀疏技术,有效提高了算法的效率。IEEE14与IEEE30节点系统和一个实际系统的仿真结果验证了所述模型的正确性和算法的有效性。     

A PC based state estimator interfaced with a remote terminal unitplacement algorithm

In this paper a new remote terminal unit (RTU) placement algorithm is presented. The objective of this algorithm is to place a minimum set of RTUs which satisfies three important constraints of the problem-observability, absence of critical measurements, and reliability requirements defined in terms of RTU loss. The problem is solved in a single stage. The results of this algorithm are interfaced with a linear programming (LP) state estimator. This estimator only uses the voltage measurements, and the active and reactive power flows in the lines for the development of the coupled state-estimation Jacobian H-matrix. The injection measurements are not currently included, though in practice they can be easily added to the estimator model. The inclusion of the injection measurements will enlarge the use of the presented algorithm. The RTU placement algorithm and its link with the LP estimator are tested on IEEE standard bus systems. Using the proposed RTU set, the test results presented show that the LP estimator has very good filtering capabilities when operated with or without bad data, and that the loss of any RTU does not have any significant impact on the solution     

基于地理信息的输电网单线图自动生成新算法

提出一种基于地理信息的输电网单线图自动生成新方法,该方法在电网节点布局问题的一般数学模型中引入了关键节点的地理信息,先采用带约束的罚函数法求得单线图节点的初始布局,然后对初始布局进行优化得到最终布局。新方法仅用少量关键节点的地理信息即可实现电网节点的自动排布,不仅改善了单线图自动生成算法的性能,而且节点排布结果美观清晰,更符合调度员的使用习惯。算例测试表明了新方法的有效性。     

含抽水蓄能电网安全约束机组组合问题的混合整数线性规划算法

抽水蓄能机组的投运对电网发电调度计划的制定具有很大影响,建立了含抽水蓄能机组电网的安全约束机组组合模型。以考虑了抽水蓄能机组启停费用的所有机组总运行费用为目标函数,根据抽水蓄能机组的不同运行工况给出旋转备用容量的解析表达式,同时在系统功率平衡约束中考虑了网络损耗的影响,并考虑了抽水蓄能机组的运行调度约束及网络安全约束。为了保证模型求解的可靠性和提高模型求解的计算效率,将目标函数进行分段线性化,并根据抽水蓄能机组的运行特点将其旋转备用容量约束等价转化为线性表达式。同时采用一种动态分段线性化方法近似逼近网络损耗,从而将机组组合模型转化为混合整数线性规划模型,并采用成熟的数学优化求解器CPLEX进行求解。对某实际23机306节点电网算例的计算结果表明,所提出的混合整数线性规划调度模型的网损逼近效果合理正确,算法求解速度快,具有较好的工程实用价值。     

Linear programming in operations research

The use of KORBX, a linear problem solver based on Karmarkar's algorithm, to solve military airlift problems is described. Such problems involve so many variables and constraints that using a simplex-based system is not feasible. Three specific applications are examined: optimal channel routing of cargoes, cargo distribution, and wartime patient evacuation     

利用二维小波变换实现变电站遥视图像处理的研究

“遥视”作为对无人值守变电站四遥功能必要的补充 ,越来越引起人们的重视。如何高效、及时地传送图像信息是遥视技术的关键所在。介绍了无人值守变电站遥视系统的基本组成原理 ,阐明了压缩传输图像的必要性 ,论述了二维小波变换的原理与Mallat算法 ,在此基础上 ,着重分析了利用二维小波变换压缩传递图像的有效区域并传至调度中心与底图重构出现场实况的方法。仿真结果表明 ,该方法具有使图像失真度小、压缩比大等优点     

基于供电环路非连通条件的配电网辐射状约束描述方法

配电网的辐射状拓扑结构是在对配电网问题的分析中需要考虑的重要约束条件,但是目前描述配电网拓扑的数学模型都较为复杂,影响了问题求解的效率。为了能够在对配电网辐射状约束进行等价描述的同时减小其模型的规模和复杂度,提出了一种基于供电环路非连通条件的配电网辐射状约束描述方法。首先利用配电网供电环路的概念,提出配电网满足辐射状拓扑的充分必要条件。同时,提出一种搜索配电网中所有供电环路的算法。然后给出一种路径状态与支路状态相互之间线性转换的方法。最后,将所提方法应用于配电网的故障恢复重构问题中,采用IEEE标准配电系统和某省会城市的实际配电网算例,对比不同辐射状约束描述方法的计算性能,验证所提方法的高效性和实用性。     

On the mathematical formulation of the wiring problem

The wiring problem is usually transformed into a graphtheoretical analysis-synthesis problem. For a practical algorithm it is necessary that certain constraints are taken into account in the construction of the respective graph. These constraints originate from the desire to place terminals—eventually in a previously determined sequence—at the periphery of the board or the wiring layer of an integrated circuit (IC). For printed boards we can also have some demands regarding the sequence of contacts and the side on which the components have to be placed. The purpose of this paper is to show how these requirements, which are indispensible for a proper printed board layout, can be examined. Some of these requirements have not appeared in literature before. The inquiry consists of two separate tests, each eventually combined with modification steps. The details of these modifications are not a subject of this paper. In the last section the content of this paper is compared with other publications in this field.     

Sparse Reactive Power Scheduling by a Penalty Function - Linear Programming Technique

This work presents a linear programming based algorithm to solve reactive power dispatch problems. A mixed set of variables (generated voltages and reactive power injections) and the reactive power model of the fast decoupled load flow algorithm are used to derive linear sensitivities. A suitable criterion is suggested to form a sparse reactive power sensitivity matrix. The sparse sensitivity matrix is in turn modeled as a bipartite graph which is used to define an efficient constraint relaxation strategy to solve linearized reactive power dispatch problems. The penalty function - linear programming technique method is used in a complete reactive power dispatch solution algorithm, the performance of which is discussed by solving a 256-node, 58 control-variable test system.     

变电站规划模型改进研究

在现有变电站规划模型的基础上,结合城市电网规划技术导则,将供电容量约束、容载比要求、最大供电线路距离等约束条件转化为罚函数,与变电站建设总投资费用组成规划模型目标函数。根据改进后的变电站规划模型特点,选择适于求解大型复杂优化问题的自适应粒子群优化算法对目标函数进行求解。通过实际算例验证改进模型的有效与实用性。