为了研究水树老化电缆极化-去极化电流(polarization and depolarization current,PDC)支路参数变化特征及原因,分析了水树微观结构特征,并揭示了水树微观结构对电缆PDC支路参数的影响。对短电缆和长电缆样本进行加速水树老化,利用PDC...为了研究水树老化电缆极化-去极化电流(polarization and depolarization current,PDC)支路参数变化特征及原因,分析了水树微观结构特征,并揭示了水树微观结构对电缆PDC支路参数的影响。对短电缆和长电缆样本进行加速水树老化,利用PDC检测样本极化–去极化电流,并计算老化样本Debye模型三支路参数。利用光学显微镜观测短电缆样本中的水树形态,利用扫描电镜(scanning electron microscopy,SEM)观测水树区域微观形貌。PDC三支路参数辨识结果表明,水树老化样本第3支路时间常数显著高于未老化样本。另外,第3支路电容增加量高于电阻减小量。微观观测结果表明水树区域存在大量孤立微孔,分析认为,水树生长将造成材料分子链断裂及形成大量微孔–XLPE界面,导致材料偶极极化时间及界面极化时间增长,样本第3支路时间常数显著增大。另外,水树区域存在大量孤立微孔,其限制了离子在水树区域的运动,从而导致样本第3支路电容增大量高于电阻减小量。展开更多
针对不同任务之间通常存在偏序关系这种实际情况,提出了基于偏序任务的社会网络合作问题(collaboration problem in social networks based on tasks with partial ordering relations,CSN-TPR).该问题研究如何从社会网络中选择合适的...针对不同任务之间通常存在偏序关系这种实际情况,提出了基于偏序任务的社会网络合作问题(collaboration problem in social networks based on tasks with partial ordering relations,CSN-TPR).该问题研究如何从社会网络中选择合适的团队来合作完成具有偏序关系的任务集,使得由通信代价、时间代价和预算代价构成的总体代价性能最优.首先证明了CSN-TPR是NP-hard问题,然后利用爬山法、分支限界策略和动态规划方法提出了近似算法HillClimbingTF_BBS.HillClimbingTF_BBS算法不仅输出有效的团队,而且能给出团队成员的具体任务分配以及每项任务的开始时间.真实数据上的实验结果表明:HillClimbingTF_BBS算法能有效并高效求解CSN-TPR.展开更多
The optimal solution of the multi-constrained QoS multicast routing problem is a tree-like hierarchical structure in the topology graph. This multicast route contains a feasible path from the source node to each of th...The optimal solution of the multi-constrained QoS multicast routing problem is a tree-like hierarchical structure in the topology graph. This multicast route contains a feasible path from the source node to each of the destinations with respect to a set of QoS constraints while minimizing a cost function. Often, it is a tree. In other cases, the hierarchies can return several times to nodes and links of the topology graph. Similarly to Steiner problem, finding such a structure is an NP-hard problem. The usual tree and topology enumeration algorithms applied for the Steiner problem cannot be used to solve the addressed problem. In this paper, we propose an exact algorithm based on the Branch and Bound principle and improved by the Lookahead technique. We show relevant properties of the optimum hierarchy permitting efficient pruning of the search space. To our knowledge, our paper is the first to propose an exact algorithm for this non-trivial multi-constrained optimal multicast route computation. Simulations illustrate the efficiency of the proposed pruning operations. The analysis of the execution time shows that in simple topologies and with tight QoS constraints the exact algorithm requires relatively little execution time. With loose constraints the computation time cannot be tolerated even for off-line route computation. In these cases, the solution is close to a Steiner tree and heuristics can be applied. These results can serve as basis for the design of efficient, polynomial-time routing algorithms.展开更多
Partial Maximum Boolean Satisfiability （Partial Max-SAT or PMSAT） is an optimization variant of Boolean satisfiability （SAT） problem, in which a variable assignment is required to satisfy all hard clauses and a ma...Partial Maximum Boolean Satisfiability （Partial Max-SAT or PMSAT） is an optimization variant of Boolean satisfiability （SAT） problem, in which a variable assignment is required to satisfy all hard clauses and a maximum number of soft clauses in a Boolean formula. PMSAT is considered as an interesting encoding domain to many reaHife problems for which a solution is acceptable even if some constraints are violated. Amongst the problems that can be formulated as such are planning and scheduling. New insights into the study of PMSAT problem have been gained since the introduction of the Max-SAT evaluations in 2006. Indeed, several PMSAT exact solvers have been developed based mainly on the Davis- Putnam-Logemann-Loveland （DPLL） procedure and Branch and Bound （B^B） algorithms. In this paper, we investigate and analyze a number of exact methods for PMSAT. We propose a taxonomy of the main exact methods within a general framework that integrates their various techniques into a unified perspective. We show its effectiveness by using it to classify PMSAT exact solvers which participated in the 2007~2011 Max-SAT evaluations, emphasizing on the most promising research directions.展开更多
文摘为了研究水树老化电缆极化-去极化电流(polarization and depolarization current,PDC)支路参数变化特征及原因,分析了水树微观结构特征,并揭示了水树微观结构对电缆PDC支路参数的影响。对短电缆和长电缆样本进行加速水树老化,利用PDC检测样本极化–去极化电流,并计算老化样本Debye模型三支路参数。利用光学显微镜观测短电缆样本中的水树形态,利用扫描电镜(scanning electron microscopy,SEM)观测水树区域微观形貌。PDC三支路参数辨识结果表明,水树老化样本第3支路时间常数显著高于未老化样本。另外,第3支路电容增加量高于电阻减小量。微观观测结果表明水树区域存在大量孤立微孔,分析认为,水树生长将造成材料分子链断裂及形成大量微孔–XLPE界面,导致材料偶极极化时间及界面极化时间增长,样本第3支路时间常数显著增大。另外,水树区域存在大量孤立微孔,其限制了离子在水树区域的运动,从而导致样本第3支路电容增大量高于电阻减小量。
文摘针对不同任务之间通常存在偏序关系这种实际情况,提出了基于偏序任务的社会网络合作问题(collaboration problem in social networks based on tasks with partial ordering relations,CSN-TPR).该问题研究如何从社会网络中选择合适的团队来合作完成具有偏序关系的任务集,使得由通信代价、时间代价和预算代价构成的总体代价性能最优.首先证明了CSN-TPR是NP-hard问题,然后利用爬山法、分支限界策略和动态规划方法提出了近似算法HillClimbingTF_BBS.HillClimbingTF_BBS算法不仅输出有效的团队,而且能给出团队成员的具体任务分配以及每项任务的开始时间.真实数据上的实验结果表明:HillClimbingTF_BBS算法能有效并高效求解CSN-TPR.
文摘The optimal solution of the multi-constrained QoS multicast routing problem is a tree-like hierarchical structure in the topology graph. This multicast route contains a feasible path from the source node to each of the destinations with respect to a set of QoS constraints while minimizing a cost function. Often, it is a tree. In other cases, the hierarchies can return several times to nodes and links of the topology graph. Similarly to Steiner problem, finding such a structure is an NP-hard problem. The usual tree and topology enumeration algorithms applied for the Steiner problem cannot be used to solve the addressed problem. In this paper, we propose an exact algorithm based on the Branch and Bound principle and improved by the Lookahead technique. We show relevant properties of the optimum hierarchy permitting efficient pruning of the search space. To our knowledge, our paper is the first to propose an exact algorithm for this non-trivial multi-constrained optimal multicast route computation. Simulations illustrate the efficiency of the proposed pruning operations. The analysis of the execution time shows that in simple topologies and with tight QoS constraints the exact algorithm requires relatively little execution time. With loose constraints the computation time cannot be tolerated even for off-line route computation. In these cases, the solution is close to a Steiner tree and heuristics can be applied. These results can serve as basis for the design of efficient, polynomial-time routing algorithms.
基金supported by the Research Center of College of Computer and Information Sciences at King Saud University, Saudi Arabia
文摘Partial Maximum Boolean Satisfiability （Partial Max-SAT or PMSAT） is an optimization variant of Boolean satisfiability （SAT） problem, in which a variable assignment is required to satisfy all hard clauses and a maximum number of soft clauses in a Boolean formula. PMSAT is considered as an interesting encoding domain to many reaHife problems for which a solution is acceptable even if some constraints are violated. Amongst the problems that can be formulated as such are planning and scheduling. New insights into the study of PMSAT problem have been gained since the introduction of the Max-SAT evaluations in 2006. Indeed, several PMSAT exact solvers have been developed based mainly on the Davis- Putnam-Logemann-Loveland （DPLL） procedure and Branch and Bound （B^B） algorithms. In this paper, we investigate and analyze a number of exact methods for PMSAT. We propose a taxonomy of the main exact methods within a general framework that integrates their various techniques into a unified perspective. We show its effectiveness by using it to classify PMSAT exact solvers which participated in the 2007~2011 Max-SAT evaluations, emphasizing on the most promising research directions.
