After cumulative discharge of gas discharge tube(GDT),it is easy to form a short circuit pathway between the two electrodes,which increases the failure risk and causes severe influences on the protected object.To redu...After cumulative discharge of gas discharge tube(GDT),it is easy to form a short circuit pathway between the two electrodes,which increases the failure risk and causes severe influences on the protected object.To reduce the failure risk of GDT and improve cumulative discharge times before failure,this work aims to suppress the formation of two short-circuit pathways by optimizing the tube wall structure,the electrode materials and the electrode structure.A total of five improved GDT samples are designed by focusing on the insulation resistance change that occurs after the improvement;then,by combining these designs with the microscopic morphology changes inside the cavity and the differences in deposition composition,the reasons for the differences in the GDT failure risk are also analyzed.The experimental results show that compared with GDT of traditional structure and material,the method of adding grooves at both ends of the tube wall can effectively block the deposition pathway of the tube wall,and the cumulative discharge time before device failure is increased by 149%.On this basis,when the iron-nickel electrode is replaced with a tungsten-copper electrode,the difference in the electrode’s surface splash characteristics further extends the discharge time before failure by 183%.In addition,when compared with the traditional electrode structure,the method of adding an annular structure at the electrode edge to block the splashing pathway for the particles on the electrode surface shows no positive effect,and the cumulative discharge time before the failure of the two structures is reduced by 22.8%and 49.7%,respectively.Among these improved structures,the samples with grooves at both ends of the tube wall and tungsten-copper as their electrode material have the lowest failure risk.展开更多
We present an energy-based method to estimate centrality in electrical networks. Here the energy between a pair of vertices denotes by the effective resistance between them. If there is only one generation and one loa...We present an energy-based method to estimate centrality in electrical networks. Here the energy between a pair of vertices denotes by the effective resistance between them. If there is only one generation and one load, then the centrality of an edge in our method is the difference between the energy of network after deleting the edge and that of the original network. Compared with the local current-flow betweenness on the IEEE 14-bus system, we have an interesting discovery that our proposed centrality is closely related to it in the sense of that the significance of edges under the two measures are very similar.展开更多
Spanning tree problems with specialized constraints can be difficult to solve in real-world scenarios,often requiring intricate algorithmic design and exponential time.Recently,there has been growing interest in end-t...Spanning tree problems with specialized constraints can be difficult to solve in real-world scenarios,often requiring intricate algorithmic design and exponential time.Recently,there has been growing interest in end-to-end deep neural networks for solving routing problems.However,such methods typically produce sequences of vertices,which make it difficult to apply them to general combinatorial optimization problems where the solution set consists of edges,as in various spanning tree problems.In this paper,we propose NeuroPrim,a novel framework for solving various spanning tree problems by defining a Markov decision process for general combinatorial optimization problems on graphs.Our approach reduces the action and state space using Prim's algorithm and trains the resulting model using REINFORCE.We apply our framework to three difficult problems on the Euclidean space:the degree-constrained minimum spanning tree problem,the minimum routing cost spanning tree problem and the Steiner tree problem in graphs.Experimental results on literature instances demonstrate that our model outperforms strong heuristics and achieves small optimality gaps of up to 250 vertices.Additionally,we find that our model has strong generalization ability with no significant degradation observed on problem instances as large as 1,000.Our results suggest that our framework can be effective for solving a wide range of combinatorial optimization problems beyond spanning tree problems.展开更多
Based on the existing pivot rules,the simplex method for linear programming is not polynomial in the worst case.Therefore,the optimal pivot of the simplex method is crucial.In this paper,we propose the optimal rule to...Based on the existing pivot rules,the simplex method for linear programming is not polynomial in the worst case.Therefore,the optimal pivot of the simplex method is crucial.In this paper,we propose the optimal rule to find all the shortest pivot paths of the simplex method for linear programming problems based on Monte Carlo tree search.Specifically,we first propose the SimplexPseudoTree to transfer the simplex method into tree search mode while avoiding repeated basis variables.Secondly,we propose four reinforcement learning models with two actions and two rewards to make the Monte Carlo tree search suitable for the simplex method.Thirdly,we set a new action selection criterion to ameliorate the inaccurate evaluation in the initial exploration.It is proved that when the number of vertices in the feasible region is C_(n)^(m),our method can generate all the shortest pivot paths,which is the polynomial of the number of variables.In addition,we experimentally validate that the proposed schedule can avoid unnecessary search and provide the optimal pivot path.Furthermore,this method can provide the best pivot labels for all kinds of supervised learning methods to solve linear programming problems.展开更多
基金supported by National Natural Science Foundation of China(No.U1834204)。
文摘After cumulative discharge of gas discharge tube(GDT),it is easy to form a short circuit pathway between the two electrodes,which increases the failure risk and causes severe influences on the protected object.To reduce the failure risk of GDT and improve cumulative discharge times before failure,this work aims to suppress the formation of two short-circuit pathways by optimizing the tube wall structure,the electrode materials and the electrode structure.A total of five improved GDT samples are designed by focusing on the insulation resistance change that occurs after the improvement;then,by combining these designs with the microscopic morphology changes inside the cavity and the differences in deposition composition,the reasons for the differences in the GDT failure risk are also analyzed.The experimental results show that compared with GDT of traditional structure and material,the method of adding grooves at both ends of the tube wall can effectively block the deposition pathway of the tube wall,and the cumulative discharge time before device failure is increased by 149%.On this basis,when the iron-nickel electrode is replaced with a tungsten-copper electrode,the difference in the electrode’s surface splash characteristics further extends the discharge time before failure by 183%.In addition,when compared with the traditional electrode structure,the method of adding an annular structure at the electrode edge to block the splashing pathway for the particles on the electrode surface shows no positive effect,and the cumulative discharge time before the failure of the two structures is reduced by 22.8%and 49.7%,respectively.Among these improved structures,the samples with grooves at both ends of the tube wall and tungsten-copper as their electrode material have the lowest failure risk.
文摘We present an energy-based method to estimate centrality in electrical networks. Here the energy between a pair of vertices denotes by the effective resistance between them. If there is only one generation and one load, then the centrality of an edge in our method is the difference between the energy of network after deleting the edge and that of the original network. Compared with the local current-flow betweenness on the IEEE 14-bus system, we have an interesting discovery that our proposed centrality is closely related to it in the sense of that the significance of edges under the two measures are very similar.
基金supported by National Key R&D Program of China(Grant No.2021YFA1000403)National Natural Science Foundation of China(Grant No.11991022)+1 种基金the Strategic Priority Research Program of Chinese Academy of Sciences(Grant No.XDA27000000)the Fundamental Research Funds for the Central Universities。
文摘Spanning tree problems with specialized constraints can be difficult to solve in real-world scenarios,often requiring intricate algorithmic design and exponential time.Recently,there has been growing interest in end-to-end deep neural networks for solving routing problems.However,such methods typically produce sequences of vertices,which make it difficult to apply them to general combinatorial optimization problems where the solution set consists of edges,as in various spanning tree problems.In this paper,we propose NeuroPrim,a novel framework for solving various spanning tree problems by defining a Markov decision process for general combinatorial optimization problems on graphs.Our approach reduces the action and state space using Prim's algorithm and trains the resulting model using REINFORCE.We apply our framework to three difficult problems on the Euclidean space:the degree-constrained minimum spanning tree problem,the minimum routing cost spanning tree problem and the Steiner tree problem in graphs.Experimental results on literature instances demonstrate that our model outperforms strong heuristics and achieves small optimality gaps of up to 250 vertices.Additionally,we find that our model has strong generalization ability with no significant degradation observed on problem instances as large as 1,000.Our results suggest that our framework can be effective for solving a wide range of combinatorial optimization problems beyond spanning tree problems.
基金supported by National Key R&D Program of China(Grant No.2021YFA1000403)National Natural Science Foundation of China(Grant No.11991022)+1 种基金the Strategic Priority Research Program of Chinese Academy of Sciences(Grant No.XDA27000000)the Fundamental Research Funds for the Central Universities。
文摘Based on the existing pivot rules,the simplex method for linear programming is not polynomial in the worst case.Therefore,the optimal pivot of the simplex method is crucial.In this paper,we propose the optimal rule to find all the shortest pivot paths of the simplex method for linear programming problems based on Monte Carlo tree search.Specifically,we first propose the SimplexPseudoTree to transfer the simplex method into tree search mode while avoiding repeated basis variables.Secondly,we propose four reinforcement learning models with two actions and two rewards to make the Monte Carlo tree search suitable for the simplex method.Thirdly,we set a new action selection criterion to ameliorate the inaccurate evaluation in the initial exploration.It is proved that when the number of vertices in the feasible region is C_(n)^(m),our method can generate all the shortest pivot paths,which is the polynomial of the number of variables.In addition,we experimentally validate that the proposed schedule can avoid unnecessary search and provide the optimal pivot path.Furthermore,this method can provide the best pivot labels for all kinds of supervised learning methods to solve linear programming problems.