一种基于点割的电路划分算法 被引量：1

1

作者 张恩利 高琳 《计算机学报》 EI CSCD 北大核心 2014年第7期1528-1537,共10页

文中提出了一种基于IG图（Intersection Graph）点割的电路划分算法,引入IG图模型,根据电路中信号网络间的交互关系构建IG图,直接对电路信号网络IG图进行最小点割划分,从而实现对电路单元（模块）的划分.该算法既有效地解决了电路超图... 文中提出了一种基于IG图（Intersection Graph）点割的电路划分算法,引入IG图模型,根据电路中信号网络间的交互关系构建IG图,直接对电路信号网络IG图进行最小点割划分,从而实现对电路单元（模块）的划分.该算法既有效地解决了电路超图与图之间转换的一致性问题,又实现了点割目标值与直接电路划分目标值的一致性,IG图点割集的大小即为真实电路划分的目标值.此外,通过给每个电路网络赋权重的方式构建带权重网络交互图,实现对电路网络划分的面积平衡进行近似控制,满足电路划分对面积平衡的特殊要求.采用MCNC提供的标准电路测试数据进行测试,实验结果表明,基于IG图点割的电路划分算法较基于网络超图HDN划分的K DualFM算法平均有3％～7.8％的提高;同时,基于IG图点割的随机优化算法ROP比基于超图划分的FM优化算法具有更强的全局优化能力,划分结果提高18％,比基于二部图匹配的点割优化算法提高36％,对较大规模数据划分优化效果更好. 展开更多

关键词 电路划分 IG图 点割 集成电路

下载PDF 职称材料

基于内点割平面法的混合整数最优潮流算法 被引量：32

2

作者 丁晓莺 王锡凡 +1 位作者 张显 胡泽春 《中国电机工程学报》 EI CSCD 北大核心 2004年第2期1-7,共7页

提出了一种采用内点割平面法求解混合整数最优潮流(OPF)的算法。该算法循环执行3个步骤:①求解OPF的可行解并将其线性化;②从线性内点法的最优解中判断基变量;③根据基变量产生混合整数割平面。与单纯形割平面法相比,内点割平面法不仅... 提出了一种采用内点割平面法求解混合整数最优潮流(OPF)的算法。该算法循环执行3个步骤:①求解OPF的可行解并将其线性化;②从线性内点法的最优解中判断基变量;③根据基变量产生混合整数割平面。与单纯形割平面法相比,内点割平面法不仅简单易实现,计算效率高,而且随着问题规模的增加,更能发挥其多项式时间特性的优点。文中还对退化问题的处理以及稀疏技巧的应用进行了深入的讨论。通过对IEEE典型系统的数值仿真计算显示出所提算法对于大型电力系统最优潮流问题的精确求解是非常有效的。 展开更多

关键词 电力系统 启发式算法 混合整数 最优潮流算法 内点割平面法 确定性算法

下载PDF 职称材料

求解大规模机组组合问题的二阶锥规划方法 被引量：28

3

作者 全然 韦化 简金宝 《中国电机工程学报》 EI CSCD 北大核心 2010年第25期101-107,共7页

基于混合整数二阶锥规划(mixed integer second-order cone programming,MI-SOCP)提出一种求解电力系统计及爬坡约束机组组合问题(unit commitment,UC)的新方法。利用UC问题的混合整数二次规划(mixed integer quadratic programming,MI-... 基于混合整数二阶锥规划(mixed integer second-order cone programming,MI-SOCP)提出一种求解电力系统计及爬坡约束机组组合问题(unit commitment,UC)的新方法。利用UC问题的混合整数二次规划(mixed integer quadratic programming,MI-QP)模型和一个简单混合整数集合的凸包表示,产生UC问题一个更紧的MI-SOCP模型。将最小覆盖不等式作为割平面,应用内点割平面法求解MI-SOCP以获得不计爬坡约束UC问题的机组启停状态。为满足爬坡约束,提出一种简单易行的机组启停状态修正方法。100机组96时段等多个系统的仿真结果表明,利用内点割平面法求解2种模型时,MI-SOCP能比MI-QP获得质量更好的次优解,所提方法能有效处理爬坡约束,适用于大规模的UC问题。 展开更多

关键词 电力系统 爬坡约束 机组组合 凸包 混合整数二阶锥规划 最小覆盖不等式 内点割平面法

下载PDF 职称材料

一种基于独立电价变量的节点电价模型 被引量：10

4

作者 丁晓莺 王锡凡 《电力系统自动化》 EI CSCD 北大核心 2006年第8期16-20,共5页

提出了一种电力市场环境下节点电价的新模型。模型的特点在于:节点电价和阻塞乘子作为独立的变量嵌入模型中,使市场中调度目标与结算目标达到统一;在考虑机组最小出力限制的情况下,模型包含特殊的约束条件以正确确定系统的边际机组。以R... 提出了一种电力市场环境下节点电价的新模型。模型的特点在于:节点电价和阻塞乘子作为独立的变量嵌入模型中,使市场中调度目标与结算目标达到统一;在考虑机组最小出力限制的情况下,模型包含特殊的约束条件以正确确定系统的边际机组。以RTS-24系统为例,通过内点割平面算法求解所提出的模型,结果表明产生的节点电价能有效缓解网络阻塞,并提供正确的市场信号。 展开更多

关键词 电力市场 节点电价 阻塞管理 最优潮流 拉格朗日乘子 内点割平面算法

下载PDF 职称材料

基于特殊有效不等式求解机组组合问题的内点割平面法 被引量：9

5

作者 全然 简金宝 +1 位作者 韦化 杨林峰 《中国电机工程学报》 EI CSCD 北大核心 2011年第19期51-59,共9页

基于特殊的有效不等式(valid inequalities,VIs),提出一种求解计及爬坡约束机组组合(unit commitment,UC)问题的内点割平面法。采用线性化技术将UC问题转化为一个混合整数二次规划(mixed integer quadratic programming,MIQP)。根据UC... 基于特殊的有效不等式(valid inequalities,VIs),提出一种求解计及爬坡约束机组组合(unit commitment,UC)问题的内点割平面法。采用线性化技术将UC问题转化为一个混合整数二次规划(mixed integer quadratic programming,MIQP)。根据UC问题约束的特点,产生3种特殊的VIs,即覆盖不等式(cover inequalities,CIs)、提升覆盖不等式(lifted cover inequalities,LCIs)和广义流覆盖不等式(generalized flow cover inequalities,GFCIs),进而将其作为割平面,建立求解MIQP的内点割平面法。100机组24时段等6个系统的仿真结果表明,产生CIs、LCIs和GFCIs的方法快速有效,所提内点割平面法具有良好的收敛性和稳定性,能有效处理爬坡约束,与其他多种方法相比较,获得了更好的数值结果。 展开更多

关键词 电力系统 机组组合 内点割平面法 有效不等式 覆盖不等式 提升覆盖不等式 广义流覆盖不等式

下载PDF 职称材料

最优潮流内点割平面的鲁棒算法 被引量：5

6

作者 刘林 王锡凡 +1 位作者 丁晓莺 张钦 《电力系统自动化》 EI CSCD 北大核心 2007年第9期1-5,77,共6页

内点割平面算法(IPCPM)集中了割平面法和内点法的优点,非常适于求解大规模系统的离散优化问题,但是研究发现内点法在求解松弛的线性规划问题时,如果问题具有多重解,最优解会收敛到凸多面体的最优面的内部,此时IPCPM会由于无法得到正确... 内点割平面算法(IPCPM)集中了割平面法和内点法的优点,非常适于求解大规模系统的离散优化问题,但是研究发现内点法在求解松弛的线性规划问题时,如果问题具有多重解,最优解会收敛到凸多面体的最优面的内部,此时IPCPM会由于无法得到正确的最优基信息来生成割平面而失效。在此基础上,文中提出了一种通用的最优基判别准则,解决了原算法失效的问题,提高了算法的鲁棒性。通过对IEEE测试系统的数值计算,表明改进后的算法能正确处理最优解的各种情况,显著扩大了IPCPM的应用范围。 展开更多

关键词 最优潮流 电力系统 内点割平面 最优基

下载PDF 职称材料

星图的R¹-限制性点割

7

作者 张璐瑶 胡晓敏 《应用数学进展》 2024年第5期2148-2154,共7页

互联网络的拓扑结构可以用图论模型来描述,因此图论在研究网络问题时扮演着重要角色。连通度是衡量一个网络容错性和可靠性的重要指标。然而,在实际情况中,网络中一个点的所有邻点同时发生故障的概率较小,因此经典连通度在一定程度上低... 互联网络的拓扑结构可以用图论模型来描述,因此图论在研究网络问题时扮演着重要角色。连通度是衡量一个网络容错性和可靠性的重要指标。然而,在实际情况中,网络中一个点的所有邻点同时发生故障的概率较小,因此经典连通度在一定程度上低估了互联网络的容错性。为了更准确地评估网络的连通性,引入了条件连通度的概念,并进一步提出了Rk-连通度的概念,使得连通度问题更具有现实意义。本文主要研究并刻画了星图的全部基数最小的R1-限制性点割。 展开更多

关键词 星图 凯莱图 R¹-限制性点割 R¹-连通度

下载PDF 职称材料

求解网络连通度问题的新算法 被引量：5

8

作者 孙小军 刘三阳 王志强 《计算机工程与应用》 CSCD 北大核心 2009年第34期82-84,共3页

连通度是评价网络系统连通状况及抗毁性的重要指标,也是网络结构的重要特征。针对现有算法在求解网络连通度时需要将原有网络转化为容量网络或进行其他变换的不足,受交通网络瘫痪事例的启发,提出了一种求解网络连通度的新算法。该算法... 连通度是评价网络系统连通状况及抗毁性的重要指标,也是网络结构的重要特征。针对现有算法在求解网络连通度时需要将原有网络转化为容量网络或进行其他变换的不足,受交通网络瘫痪事例的启发,提出了一种求解网络连通度的新算法。该算法通过引入点影响度和网络影响度来刻画各顶点在网络中的重要程度,不仅能求解网络连通度,同时还可以确定网络的最小点割,算法步骤简单、易于实现。最后算法分析和仿真实验表明了新算法的有效性。 展开更多

关键词 网络 可靠性 影响度 最小点割 连通度

下载PDF 职称材料

拟(k+1)-连通图的一些性质 被引量：2

9

作者 蒋红星 苏健基 《广西师范大学学报（自然科学版）》 CAS 2001年第4期26-29,共4页

设 G为 k-连通图且不存在非平凡的 k-点割 ,则称 G为拟 ( k+ 1 ) -连通图 ,给出了拟 ( k+ 1 ) -连通图的一些类似于 ( k+ 1 )

关键词 拟(κ+1)-连通图 圈 性质 κ-连通图 κ-点割 简单无向有限图

下载PDF 职称材料

基于内点割平面算法的电力系统机组优化组合研究

10

作者 丁晓莺 王建学 +1 位作者 高卫恒 陈晨 《陕西电力》 2008年第1期20-24,共5页

合理的开停机方案将为电力系统运行带来很大的经济效益,现代电力系统对机组优化组合算法的收敛速度和解的质量要求越来越高。文章提出了一种改进的内点割平面算法(IPCPM)求解机组组合问题,与原IPCPM相比,在退化解的处理过程中避免了多... 合理的开停机方案将为电力系统运行带来很大的经济效益,现代电力系统对机组优化组合算法的收敛速度和解的质量要求越来越高。文章提出了一种改进的内点割平面算法(IPCPM)求解机组组合问题,与原IPCPM相比,在退化解的处理过程中避免了多次的矩阵列交换和秩计算,同时省略了对偶最优基的判断流程,使算法计算量明显减少,速度更快。通过多个不同规模和特性的系统测算,表明该算法能有效地产生割平面约束,计算结果准确合理,改进后的算法实现更方便,计算更快速,适合求解大型电力系统机组组合问题。 展开更多

关键词 机组组合 内点割平面算法 退化问题 最优基

下载PDF 职称材料

两类网络的2-限制连通度

11

作者 肖旭 阿依古丽·马木提 《数学进展》 CSCD 北大核心 2022年第2期275-282,共8页

给定图G=(V,E)和非负整数h,图G的h-限制点割S是V(G)的一个子集(如果存在)使得G−S不连通且G−S中任一点的度数至少为h.图G的h-限制连通度κ^(h)(G)是G的最小h-限制点割的阶数.本文中,我们证明了κ^(2)(FCQ_(n))=4n−4(n≥8),κ^(2)(SQ_(n))... 给定图G=(V,E)和非负整数h,图G的h-限制点割S是V(G)的一个子集(如果存在)使得G−S不连通且G−S中任一点的度数至少为h.图G的h-限制连通度κ^(h)(G)是G的最小h-限制点割的阶数.本文中,我们证明了κ^(2)(FCQ_(n))=4n−4(n≥8),κ^(2)(SQ_(n))=4n−8(n≥4),其中FCQ_(n)和SQ_(n)分别是n维折叠交叉超立方体和n维spined cube. 展开更多

关键词 折叠交叉超立方体 spined cube 限制点割 限制连通度

原文传递

收缩临界6-连通图中的6度点 被引量：1

12

作者 齐登记 余世群 《湖北民族学院学报（自然科学版）》 CAS 2002年第4期76-77,共2页

每一个收缩临界 6 -连通图都有一个 6度点 .最近袁旭东证明了任何收缩临界 6 -连通图都存在两个相临的 6度点。对于收缩临界 6 -连通图中的每一个点都存在一个 6度点使得这两点相邻或距离为 3,从而对收缩临界中 6度点的分布有了更进一... 每一个收缩临界 6 -连通图都有一个 6度点 .最近袁旭东证明了任何收缩临界 6 -连通图都存在两个相临的 6度点。对于收缩临界 6 -连通图中的每一个点都存在一个 6度点使得这两点相邻或距离为 3,从而对收缩临界中 6度点的分布有了更进一步认识 . 展开更多

关键词 收缩临界k-连通图 断片 最小点割 x-原子

下载PDF 职称材料

收缩临界6连通图的6度顶点 被引量：1

13

作者 卢建立 张志芳 《数学的实践与认识》 CSCD 北大核心 2011年第13期169-173,共5页

利用断片的性质,改进了齐恩凤,齐登记等的研究结果,得到了收缩临界6-连通图中6度点的性质的新结果:设x是G中任意一点,设A是一个x-原子,记N_A=T_A,N(x)∩T_A≠Φ,则A∩T_A中有与x相邻的6度点或两点的距离为2.

关键词 收缩临界6连通图 断片 最小点割 S-原子

原文传递

电力系统最优潮流的内点割平面法分析与改进 被引量：1

14

作者 丁晓莺 王建学 +1 位作者 王锡凡 刘林 《浙江大学学报（工学版）》 EI CAS CSCD 北大核心 2010年第4期771-777,共7页

针对电力系统优化运行控制的最优潮流问题,采用内点割平面法求解多重解的线性规划问题,算法迭代次数多,计算速度低,严重的可能导致算法不收敛.为此提出一种识别最优基的方法,通过对优化问题的解空间进行旋转和映射,将最优解沿可行域的... 针对电力系统优化运行控制的最优潮流问题,采用内点割平面法求解多重解的线性规划问题,算法迭代次数多,计算速度低,严重的可能导致算法不收敛.为此提出一种识别最优基的方法,通过对优化问题的解空间进行旋转和映射,将最优解沿可行域的棱移动至顶点,得到问题的最优基,从而解决原算法失效的问题.进一步采用随机扰动法和阶梯矩阵变化法提高算法的计算效率,平均计算时间缩短了20%左右.对电力系统标准测试系统IEEE14-300节点系统的数值仿真结果表明,改进算法能够正确处理最优解的各种情况,扩大了内点割平面法的应用范围. 展开更多

关键词 电力系统 最优潮流 内点割平面法 最优基

下载PDF 职称材料

4连通图中最长圈上的可去边

15

作者 徐丽琼 《厦门大学学报（自然科学版）》 CAS CSCD 北大核心 2016年第4期550-553,共4页

图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图的一些性质的有力工具.利用边点割断片的性质给出了某类4连通图中在特定子图上可去边的分布情况,证明了若4连通图G的边点割原子的顶点数大于2,则G中的最长圈C上至少有3条... 图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图的一些性质的有力工具.利用边点割断片的性质给出了某类4连通图中在特定子图上可去边的分布情况,证明了若4连通图G的边点割原子的顶点数大于2,则G中的最长圈C上至少有3条可去边. 展开更多

关键词 4连通图 可去边 边点割原子

下载PDF 职称材料

k连通图在边点割原子与点割上的可去边

16

作者 徐丽琼 《厦门大学学报（自然科学版）》 CAS CSCD 北大核心 2011年第1期10-12,共3页

图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图的一些性质的有力工具.利用边点割断片的性质给出某些k连通图中在特定子图上可去边的分布情况,得到了最小度至少为(3(k-1)/2)或围长至少为4的k连通图(k≥4)中由边点割原... 图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图的一些性质的有力工具.利用边点割断片的性质给出某些k连通图中在特定子图上可去边的分布情况,得到了最小度至少为(3(k-1)/2)或围长至少为4的k连通图(k≥4)中由边点割原子与点割所导出的子图的每一条边都是可去边. 展开更多

关键词 k连通图 可去边 边点割原子

下载PDF 职称材料