We introduce Quafu-Qcover,an open-source cloud-based software package developed for solving combinatorial optimization problems using quantum simulators and hardware backends.Quafu-Qcover provides a standardized and c...We introduce Quafu-Qcover,an open-source cloud-based software package developed for solving combinatorial optimization problems using quantum simulators and hardware backends.Quafu-Qcover provides a standardized and comprehensive workflow that utilizes the quantum approximate optimization algorithm(QAOA).It facilitates the automatic conversion of the original problem into a quadratic unconstrained binary optimization(QUBO)model and its corresponding Ising model,which can be subsequently transformed into a weight graph.The core of Qcover relies on a graph decomposition-based classical algorithm,which efficiently derives the optimal parameters for the shallow QAOA circuit.Quafu-Qcover incorporates a dedicated compiler capable of translating QAOA circuits into physical quantum circuits that can be executed on Quafu cloud quantum computers.Compared to a general-purpose compiler,our compiler demonstrates the ability to generate shorter circuit depths,while also exhibiting superior speed performance.Additionally,the Qcover compiler has the capability to dynamically create a library of qubits coupling substructures in real-time,utilizing the most recent calibration data from the superconducting quantum devices.This ensures that computational tasks can be assigned to connected physical qubits with the highest fidelity.The Quafu-Qcover allows us to retrieve quantum computing sampling results using a task ID at any time,enabling asynchronous processing.Moreover,it incorporates modules for results preprocessing and visualization,facilitating an intuitive display of solutions for combinatorial optimization problems.We hope that Quafu-Qcover can serve as an instructive illustration for how to explore application problems on the Quafu cloud quantum computers.展开更多
Traditional expert-designed branching rules in branch-and-bound(B&B) are static, often failing to adapt to diverse and evolving problem instances. Crafting these rules is labor-intensive, and may not scale well wi...Traditional expert-designed branching rules in branch-and-bound(B&B) are static, often failing to adapt to diverse and evolving problem instances. Crafting these rules is labor-intensive, and may not scale well with complex problems.Given the frequent need to solve varied combinatorial optimization problems, leveraging statistical learning to auto-tune B&B algorithms for specific problem classes becomes attractive. This paper proposes a graph pointer network model to learn the branch rules. Graph features, global features and historical features are designated to represent the solver state. The graph neural network processes graph features, while the pointer mechanism assimilates the global and historical features to finally determine the variable on which to branch. The model is trained to imitate the expert strong branching rule by a tailored top-k Kullback-Leibler divergence loss function. Experiments on a series of benchmark problems demonstrate that the proposed approach significantly outperforms the widely used expert-designed branching rules. It also outperforms state-of-the-art machine-learning-based branch-and-bound methods in terms of solving speed and search tree size on all the test instances. In addition, the model can generalize to unseen instances and scale to larger instances.展开更多
Computational time complexity analyzes of evolutionary algorithms （EAs） have been performed since the mid-nineties. The first results were related to very simple algorithms, such as the （1＋1）-EA, on toy problems....Computational time complexity analyzes of evolutionary algorithms （EAs） have been performed since the mid-nineties. The first results were related to very simple algorithms, such as the （1＋1）-EA, on toy problems. These efforts produced a deeper understanding of how EAs perform on different kinds of fitness landscapes and general mathematical tools that may be extended to the analysis of more complicated EAs on more realistic problems. In fact, in recent years, it has been possible to analyze the （1＋1）-EA on combinatorial optimization problems with practical applications and more realistic population-based EAs on structured toy problems. This paper presents a survey of the results obtained in the last decade along these two research lines. The most common mathematical techniques are introduced, the basic ideas behind them are discussed and their elective applications are highlighted. Solved problems that were still open are enumerated as are those still awaiting for a solution. New questions and problems arisen in the meantime are also considered.展开更多
This paper is basically a survey to show a number of combinatorial optimization problems arising from VLSI circuit design. Some of them including the existence problem, minimax problem, net representation, bend minimi...This paper is basically a survey to show a number of combinatorial optimization problems arising from VLSI circuit design. Some of them including the existence problem, minimax problem, net representation, bend minimization, area minimization, placement problem, routing problem, etc. are especially discussed with new results and theoretical ideas for treating them. Finally, a number of problems for further research are mentioned.展开更多
Electronic components' reliability has become the key of the complex system mission execution. Analog circuit is an important part of electronic components. Its fault diagnosis is far more challenging than that of...Electronic components' reliability has become the key of the complex system mission execution. Analog circuit is an important part of electronic components. Its fault diagnosis is far more challenging than that of digital circuit. Simulations and applications have shown that the methods based on BP neural network are effective in analog circuit fault diagnosis. Aiming at the tolerance of analog circuit,a combinatorial optimization diagnosis scheme was proposed with back propagation( BP) neural network( BPNN).The main contributions of this scheme included two parts:( 1) the random tolerance samples were added into the nominal training samples to establish new training samples,which were used to train the BP neural network based diagnosis model;( 2) the initial weights of the BP neural network were optimized by genetic algorithm( GA) to avoid local minima,and the BP neural network was tuned with Levenberg-Marquardt algorithm( LMA) in the local solution space to look for the optimum solution or approximate optimal solutions. The experimental results show preliminarily that the scheme substantially improves the whole learning process approximation and generalization ability,and effectively promotes analog circuit fault diagnosis performance based on BPNN.展开更多
Many problems in science,engineering and real life are related to the combinatorial optimization.However,many combinatorial optimization problems belong to a class of the NP-hard problems,and their globally optimal so...Many problems in science,engineering and real life are related to the combinatorial optimization.However,many combinatorial optimization problems belong to a class of the NP-hard problems,and their globally optimal solutions are usually difficult to solve.Therefore,great attention has been attracted to the algorithms of searching the globally optimal solution or near-optimal solution for the combinatorial optimization problems.As a typical combinatorial optimization problem,the traveling salesman problem(TSP)often serves as a touchstone for novel approaches.It has been found that natural systems,particularly brain nervous systems,work at the critical region between order and disorder,namely,on the edge of chaos.In this work,an algorithm for the combinatorial optimization problems is proposed based on the neural networks on the edge of chaos(ECNN).The algorithm is then applied to TSPs of 10 cities,21 cities,48 cities and 70 cities.The results show that ECNN algorithm has strong ability to drive the networks away from local minimums.Compared with the transiently chaotic neural network(TCNN),the stochastic chaotic neural network(SCNN)algorithms and other optimization algorithms,much higher rates of globally optimal solutions and near-optimal solutions are obtained with ECNN algorithm.To conclude,our algorithm provides an effective way for solving the combinatorial optimization problems.展开更多
Traditional operational research methods have been the primary means of solving combinatorial optimization problems(COPs)for the past few decades.However,with the rapid increase in the scale of problems in real-world ...Traditional operational research methods have been the primary means of solving combinatorial optimization problems(COPs)for the past few decades.However,with the rapid increase in the scale of problems in real-world scenarios and the demand for online optimization,these methods face persistent challenges including computational complexity and optimality.In recent years,combinatorial optimization methods based on deep learning have rapidly evolved,progressing from tackling solely small-scale problems(e.g.,the traveling salesman problem(TSP)with fewer than 100 cities)to swiftly delivering high-quality solutions for graphs containing up to a million nodes.Particularly,in the last two years,a multitude of studies has surfaced,demonstrating the ability to generalize learned models to large-scale problems with diverse distributions.This capability empowers deep learning-based methods to demonstrate robust competitiveness,even when challenged by professional solvers.Consequently,this review summarizes the methods employed in recent years for solving COPs through deep learning(including prompt learning),scrutinizes the strengths and weaknesses of these methods,and concludes by highlighting potential directions for mitigating these weaknesses.展开更多
Multiobjective combinatorial optimization(MOCO)problems have a wide range of applications in the real world.Recently,learning-based methods have achieved good results in solving MOCO problems.However,most of these met...Multiobjective combinatorial optimization(MOCO)problems have a wide range of applications in the real world.Recently,learning-based methods have achieved good results in solving MOCO problems.However,most of these methods use attention mechanisms and their variants,which have room for further improvement in the speed of solving MOCO problems.In this paper,following the idea of decomposition strategy and neural combinatorial optimization,a novel fast-solving model for MOCO based on retention is proposed.A brand new calculation of retention is proposed,causal masking and exponential decay are deprecated in retention,so that our model could better solve MOCO problems.During model training,a parallel computation of retention is applied,allowing for fast parallel training.When using the model to solve MOCO problems,a recurrent computation of retention is applied,enabling quicker problem-solving.In order to make our model more practical and flexible,a preference-based retention decoder is proposed,which allows generating approximate Pareto solutions for any trade-off preferences directly.An industry-standard deep reinforcement learning algorithm is used to train RM-MOCO.Experimental results show that,while ensuring the quality of problem solving,the proposed method significantly outperforms some other methods in terms of the speed of solving MOCO problems.展开更多
Combinatorial Optimization Problems(COPs)are a class of optimization problems that are commonly encountered in industrial production and everyday life.Over the last few decades,traditional algorithms,such as exact alg...Combinatorial Optimization Problems(COPs)are a class of optimization problems that are commonly encountered in industrial production and everyday life.Over the last few decades,traditional algorithms,such as exact algorithms,approximate algorithms,and heuristic algorithms,have been proposed to solve COPs.However,as COPs in the real world become more complex,traditional algorithms struggle to generate optimal solutions in a limited amount of time.Since Deep Neural Networks(DNNs)are not heavily dependent on expert knowledge and are adequately flexible for generalization to various COPs,several DNN-based algorithms have been proposed in the last ten years for solving COPs.Herein,we categorize these algorithms into four classes and provide a brief overview of their applications in real-world problems.展开更多
Combinatorial optimization(CO)on graphs is a classic topic that has been extensively studied across many scientific and industrial fields.Recently,solving CO problems on graphs through learning methods has attracted g...Combinatorial optimization(CO)on graphs is a classic topic that has been extensively studied across many scientific and industrial fields.Recently,solving CO problems on graphs through learning methods has attracted great attention.Advanced deep learning methods,e.g.,graph neural networks(GNNs),have been used to effectively assist the process of solving COs.However,current frameworks based on GNNs are mainly designed for certain CO problems,thereby failing to consider their transferable and generalizable abilities among different COs on graphs.Moreover,simply using original graphs to model COs only captures the direct correlations among objects,which does not consider the mathematical logicality and properties of COs.In this paper,we propose a unified pre-training and adaptation framework for COs on graphs with the help of the maximum satisfiability(Max-SAT)problem.We first use Max-SAT to bridge different COs on graphs since they can be converted to Max-SAT problems represented by standard formulas and clauses with logical information.Then we further design a pre-training and domain adaptation framework to extract the transferable and generalizable features so that different COs can benefit from them.In the pre-training stage,Max-SAT instances are generated to initialize the parameters of the model.In the fine-tuning stage,instances from CO and Max-SAT problems are used for adaptation so that the transferable ability can be further improved.Numerical experiments on several datasets show that features extracted by our framework exhibit superior transferability and Max-SAT can boost the ability to solve COs on graphs.展开更多
Each physical process in a numerical weather prediction(NWP)system may have many different parameterization schemes.Early studies have shown that the performance of different physical parameterization schemes varies w...Each physical process in a numerical weather prediction(NWP)system may have many different parameterization schemes.Early studies have shown that the performance of different physical parameterization schemes varies with the weather situation to be simulated.Thus,it is necessary to select a suitable combination of physical parameterization schemes according to the variation of weather systems.However,it is rather difficult to identify an optimal combination among millions of possible parameterization scheme combinations.This study applied a simple genetic algorithm(SGA)to optimizing the combination of parameterization schemes in NWP models for typhoon forecasting.The feasibility of SGA was verified with the simulation of Typhoon Mujigae(2015)by using the Weather Research and Forecasting(WRF)model and Typhoon Higos(2020)by using the Coupled Ocean–Atmosphere–Wave–Sediment Transport(COAWST)modeling system.The results show that SGA can efficiently obtain the optimal combination of schemes.For Typhoon Mujigae(2015),the optimal combination can be found from the 1,304,576 possible combinations by running only 488 trials.Similar results can be obtained for Typhoon Higos(2020).Compared to the default combination proposed by the COAWST model system,the optimal combination scheme significantly improves the simulation of typhoon track and intensity.This study provides a feasible way to search for the optimal combinations of physical parameterization schemes in WRF and COAWST for more accurate typhoon simulation.This can help provide references for future development of NWP models,and for analyzing the coordination and adaptability of different physical process parameterization schemes under specific weather backgrounds.展开更多
The optimization of polymer structures aims to determine an optimal sequence or topology that achieves a given target property or structural performance.This inverse design problem involves searching within a vast com...The optimization of polymer structures aims to determine an optimal sequence or topology that achieves a given target property or structural performance.This inverse design problem involves searching within a vast combinatorial phase space defined by components,se-quences,and topologies,and is often computationally intractable due to its NP-hard nature.At the core of this challenge lies the need to evalu-ate complex correlations among structural variables,a classical problem in both statistical physics and combinatorial optimization.To address this,we adopt a mean-field approach that decouples direct variable-variable interactions into effective interactions between each variable and an auxiliary field.The simulated bifurcation(SB)algorithm is employed as a mean-field-based optimization framework.It constructs a Hamiltonian dynamical system by introducing generalized momentum fields,enabling efficient decoupling and dynamic evolution of strongly coupled struc-tural variables.Using the sequence optimization of a linear copolymer adsorbing on a solid surface as a case study,we demonstrate the applica-bility of the SB algorithm to high-dimensional,non-differentiable combinatorial optimization problems.Our results show that SB can efficiently discover polymer sequences with excellent adsorption performance within a reasonable computational time.Furthermore,it exhibits robust con-vergence and high parallel scalability across large design spaces.The approach developed in this work offers a new computational pathway for polymer structure optimization.It also lays a theoretical foundation for future extensions to topological design problems,such as optimizing the number and placement of side chains,as well as the co-optimization of sequence and topology.展开更多
Combinatorial optimization problems are found in many application fields such as computer science, engineering and economy. In this paper, a new efficient meta-heuristic, Intersection-Based Scaling (IBS for abbreviati...Combinatorial optimization problems are found in many application fields such as computer science, engineering and economy. In this paper, a new efficient meta-heuristic, Intersection-Based Scaling (IBS for abbreviation), is proposed and it can be applied to the combinatorial optimization problems. The main idea of IBS is to scale the size of the instance based on the intersection of some local optima, and to simplify the search space by extracting the intersection from the instance, which makes the search more efficient. The combination of IBS with some local search heuristics of different combinatorial optimization problems such as Traveling Salesman Problem (TSP) and Graph Partitioning Problem (GPP) is studied, and comparisons are made with some of the best heuristic algorithms and meta-heuristic algorithms. It is found that it has significantly improved the performance of existing local search heuristics and significantly outperforms the known best algorithms. Keywords combinatorial optimization - TSP (Traveling Salesman Problem) - GPP (Graph Partitioning Problem) - IBS (Intersection-Based Scaling) - meta heuristic Regular PaperThis work is supported by the National Basic Research 973 Program of China (Grant No.TG1998030401).Peng Zou was born in 1979. He received the B.S. degree in computer software from University of Science and Technology of China (USTC) in 2000. Now he is a Ph.D. candidate in computer science of USTC. His current research interests include algorithms for NP-hard problems and parallel computing.Zhi Zhou was born in 1976. He received the B.S. degree in computer software from USTC in 1995. Now he is a Ph.D. candidate in computer science of USTC. His current research interests include combinatorial problem and parallel computing.Ying-Yu Wan was born in 1976. He received the B.S. degree in computer software from USTC in 1997, and the Ph.D. degree from USTC in 2002. His current research interests include parallel computing and combinatorial problem.Guo-Liang Chen was born in 1938. Now he is an Academician of CAS and Ph.D. supervisor in Department of Computer Science at USTC, director of the National High Performance Computing Center at Hefei. His current research interests include parallel computing, computer architecture and combinatorial optimization.Jun Gu was born in 1956. He received the B.S. degree in electronic engineering from USTC in 1982, and the Ph.D. degree in computer science from University of Utah. Now he is a professor and Ph.D. supervisor in computer science at USTC and Hong Kong University of Science and Technology. His main research interrests include algorithms for NP-hard problems.展开更多
Stochastic optimization has established itself as a major method to handle uncertainty in various optimization problems by modeling the uncertainty by a probability distribution over possible realizations.Traditional...Stochastic optimization has established itself as a major method to handle uncertainty in various optimization problems by modeling the uncertainty by a probability distribution over possible realizations.Traditionally,the main focus in stochastic optimization has been various stochastic mathematical programming(such as linear programming,convex programming).In recent years,there has been a surge of interest in stochastic combinatorial optimization problems from the theoretical computer science community.In this article,we survey some of the recent results on various stochastic versions of classical combinatorial optimization problems.Since most problems in this domain are NP-hard(or#P-hard,or even PSPACE-hard),we focus on the results which provide polynomial time approximation algorithms with provable approximation guarantees.Our discussions are centered around a few representative problems,such as stochastic knapsack,stochastic matching,multi-armed bandit etc.We use these examples to introduce several popular stochastic models,such as the fixed-set model,2-stage stochastic optimization model,stochastic adaptive probing model etc,as well as some useful techniques for designing approximation algorithms for stochastic combinatorial optimization problems,including the linear programming relaxation approach,boosted sampling,content resolution schemes,Poisson approximation etc.We also provide some open research questions along the way.Our purpose is to provide readers a quick glimpse to the models,problems,and techniques in this area,and hopefully inspire new contributions.展开更多
Selecting the best type of equipment among available switches with different prices and reliability levels is a significant challenge in distribution system planning.In this paper,the optimal type of switches in a rad...Selecting the best type of equipment among available switches with different prices and reliability levels is a significant challenge in distribution system planning.In this paper,the optimal type of switches in a radial distribution system is selected by considering the total cost and reliability criterion and using the weighted augmented epsilon constraint method and combinatorial optimization.A new index is calculated to assess the robustness of each Pareto solution.Moreover,for each failure,repair time is considered based on historical data.Monte Carlo simulations are used to consider the switch failure uncertainty and fault repair time uncertainty in the model.The proposed framework is applied to an RTBS Bus-2 test system.Furthermore,the model is also applied to an industrial system to verify the proposed method’s excellent performance in larger practical engineering problems.展开更多
Combinatorial optimization in the face of uncertainty is a challenge in both operational research and machine learning.In this paper,we consider a special and important class called the adversarial online combinatoria...Combinatorial optimization in the face of uncertainty is a challenge in both operational research and machine learning.In this paper,we consider a special and important class called the adversarial online combinatorial optimization with semi-bandit feedback,in which a player makes combinatorial decisions and gets the corresponding feedback repeatedly.While existing algorithms focus on the regret guarantee or assume there exists an efficient offline oracle,it is still a challenge to solve this problem efficiently if the offline counterpart is NP-hard.In this paper,we propose a variant of the Follow-the-Perturbed-Leader(FPL)algorithm to solve this problem.Unlike the existing FPL approach,our method employs an approximation algorithm as an offline oracle and perturbs the collected data by adding nonnegative random variables.Our ap-proach is simple and computationally efficient.Moreover,it can guarantee a sublinear(1+ε)-scaled regret of order O(T^(2/3))for any smallε>0 for an important class of combinatorial optimization problems that admit an FPTAS(fully polynomial time approximation scheme),in which T is the number of rounds of the learning process.In addition to the theoretical analysis,we also conduct a series of experiments to demonstrate the performance of our algorithm.展开更多
To improve the evolutionary algorithm performance,especially in convergence speed and global optimization ability,a self-adaptive mechanism is designed both for the conventional genetic algorithm(CGA)and the quantum i...To improve the evolutionary algorithm performance,especially in convergence speed and global optimization ability,a self-adaptive mechanism is designed both for the conventional genetic algorithm(CGA)and the quantum inspired genetic algorithm(QIGA).For the self-adaptive mechanism,each individual was assigned with suitable evolutionary parameter according to its current evolutionary state.Therefore,each individual can evolve toward to the currently best solution.Moreover,to reduce the running time of the proposed self-adaptive mechanism-based QIGA(SAM-QIGA),a multi-universe parallel structure was employed in the paper.Simulation results show that the proposed SAM-QIGA have better performances both in convergence and global optimization ability.展开更多
The combinatorial optimization problem(COP),which aims to find the optimal solution in discrete space,is fundamental in various fields.Unfortunately,many COPs are NP-complete,and require much more time to solve as the...The combinatorial optimization problem(COP),which aims to find the optimal solution in discrete space,is fundamental in various fields.Unfortunately,many COPs are NP-complete,and require much more time to solve as the problem scale increases.Troubled by this,researchers may prefer fast methods even if they are not exact,so approximation algorithms,heuristic algorithms,and machine learning have been proposed.Some works proposed chaotic simulated annealing(CSA)based on the Hopfield neural network and did a good job.However,CSA is not something that current general-purpose processors can handle easily,and there is no special hardware for it.To efficiently perform CSA,we propose a software and hardware co-design.In software,we quantize the weight and output using appropriate bit widths,and then modify the calculations that are not suitable for hardware implementation.In hardware,we design a specialized processing-in-memory hardware architecture named COPPER based on the memristor.COPPER is capable of efficiently running the modified quantized CSA algorithm and supporting the pipeline further acceleration.The results show that COPPER can perform CSA remarkably well in both speed and energy.展开更多
Assume there are several states, and the objective function f\+s(x) is linked with each state s. Robust optimization is to solve the following problem: min x∈X max s∈Sf\+s(x)where X is the feasible s...Assume there are several states, and the objective function f\+s(x) is linked with each state s. Robust optimization is to solve the following problem: min x∈X max s∈Sf\+s(x)where X is the feasible solution set, and S is the collection of states.\;It has been showed that most of robust combinatorial optimization problems are NP\|hard in strong sense. In this paper, we will discuss the borderline between the ′easy′ and the ′hard′ cases of robust combinatorial optimization problems, and further present a heuristic frame work to solve the ′hard′ problems and discuss their concrete implementation of the heuristic method.展开更多
This paper provides an overview on the current status of the researches in the field of neural algorithms for combinatorial optimization and makes some comments on the recent development. Meanwhile,we point out that s...This paper provides an overview on the current status of the researches in the field of neural algorithms for combinatorial optimization and makes some comments on the recent development. Meanwhile,we point out that such optimization networks suffer from some serious problems. At the end of this paper, we present the readers some aspects which need more researches in the future.展开更多
基金supported by the National Natural Science Foundation of China(Grant No.92365206)the support of the China Postdoctoral Science Foundation(Certificate Number:2023M740272)+1 种基金supported by the National Natural Science Foundation of China(Grant No.12247168)China Postdoctoral Science Foundation(Certificate Number:2022TQ0036)。
文摘We introduce Quafu-Qcover,an open-source cloud-based software package developed for solving combinatorial optimization problems using quantum simulators and hardware backends.Quafu-Qcover provides a standardized and comprehensive workflow that utilizes the quantum approximate optimization algorithm(QAOA).It facilitates the automatic conversion of the original problem into a quadratic unconstrained binary optimization(QUBO)model and its corresponding Ising model,which can be subsequently transformed into a weight graph.The core of Qcover relies on a graph decomposition-based classical algorithm,which efficiently derives the optimal parameters for the shallow QAOA circuit.Quafu-Qcover incorporates a dedicated compiler capable of translating QAOA circuits into physical quantum circuits that can be executed on Quafu cloud quantum computers.Compared to a general-purpose compiler,our compiler demonstrates the ability to generate shorter circuit depths,while also exhibiting superior speed performance.Additionally,the Qcover compiler has the capability to dynamically create a library of qubits coupling substructures in real-time,utilizing the most recent calibration data from the superconducting quantum devices.This ensures that computational tasks can be assigned to connected physical qubits with the highest fidelity.The Quafu-Qcover allows us to retrieve quantum computing sampling results using a task ID at any time,enabling asynchronous processing.Moreover,it incorporates modules for results preprocessing and visualization,facilitating an intuitive display of solutions for combinatorial optimization problems.We hope that Quafu-Qcover can serve as an instructive illustration for how to explore application problems on the Quafu cloud quantum computers.
基金supported by the Open Project of Xiangjiang Laboratory (22XJ02003)Scientific Project of the National University of Defense Technology (NUDT)(ZK21-07, 23-ZZCX-JDZ-28)+1 种基金the National Science Fund for Outstanding Young Scholars (62122093)the National Natural Science Foundation of China (72071205)。
文摘Traditional expert-designed branching rules in branch-and-bound(B&B) are static, often failing to adapt to diverse and evolving problem instances. Crafting these rules is labor-intensive, and may not scale well with complex problems.Given the frequent need to solve varied combinatorial optimization problems, leveraging statistical learning to auto-tune B&B algorithms for specific problem classes becomes attractive. This paper proposes a graph pointer network model to learn the branch rules. Graph features, global features and historical features are designated to represent the solver state. The graph neural network processes graph features, while the pointer mechanism assimilates the global and historical features to finally determine the variable on which to branch. The model is trained to imitate the expert strong branching rule by a tailored top-k Kullback-Leibler divergence loss function. Experiments on a series of benchmark problems demonstrate that the proposed approach significantly outperforms the widely used expert-designed branching rules. It also outperforms state-of-the-art machine-learning-based branch-and-bound methods in terms of solving speed and search tree size on all the test instances. In addition, the model can generalize to unseen instances and scale to larger instances.
基金This work was supported by an EPSRC grant (No.EP/C520696/1).
文摘Computational time complexity analyzes of evolutionary algorithms （EAs） have been performed since the mid-nineties. The first results were related to very simple algorithms, such as the （1＋1）-EA, on toy problems. These efforts produced a deeper understanding of how EAs perform on different kinds of fitness landscapes and general mathematical tools that may be extended to the analysis of more complicated EAs on more realistic problems. In fact, in recent years, it has been possible to analyze the （1＋1）-EA on combinatorial optimization problems with practical applications and more realistic population-based EAs on structured toy problems. This paper presents a survey of the results obtained in the last decade along these two research lines. The most common mathematical techniques are introduced, the basic ideas behind them are discussed and their elective applications are highlighted. Solved problems that were still open are enumerated as are those still awaiting for a solution. New questions and problems arisen in the meantime are also considered.
文摘This paper is basically a survey to show a number of combinatorial optimization problems arising from VLSI circuit design. Some of them including the existence problem, minimax problem, net representation, bend minimization, area minimization, placement problem, routing problem, etc. are especially discussed with new results and theoretical ideas for treating them. Finally, a number of problems for further research are mentioned.
基金National Natural Science Foundation of China(No.61371024)Aviation Science Fund of China(No.2013ZD53051)+2 种基金Aerospace Technology Support Fund of Chinathe Industry-Academy-Research Project of AVIC,China(No.cxy2013XGD14)the Open Research Project of Guangdong Key Laboratory of Popular High Performance Computers/Shenzhen Key Laboratory of Service Computing and Applications,China
文摘Electronic components' reliability has become the key of the complex system mission execution. Analog circuit is an important part of electronic components. Its fault diagnosis is far more challenging than that of digital circuit. Simulations and applications have shown that the methods based on BP neural network are effective in analog circuit fault diagnosis. Aiming at the tolerance of analog circuit,a combinatorial optimization diagnosis scheme was proposed with back propagation( BP) neural network( BPNN).The main contributions of this scheme included two parts:( 1) the random tolerance samples were added into the nominal training samples to establish new training samples,which were used to train the BP neural network based diagnosis model;( 2) the initial weights of the BP neural network were optimized by genetic algorithm( GA) to avoid local minima,and the BP neural network was tuned with Levenberg-Marquardt algorithm( LMA) in the local solution space to look for the optimum solution or approximate optimal solutions. The experimental results show preliminarily that the scheme substantially improves the whole learning process approximation and generalization ability,and effectively promotes analog circuit fault diagnosis performance based on BPNN.
基金supported by the National Natural Science Foundation of China(Grant No.12074335)the National Science and Technology Major Project of the Ministry of Science and Technology of China(Grant No.2016YFA0300402).
文摘Many problems in science,engineering and real life are related to the combinatorial optimization.However,many combinatorial optimization problems belong to a class of the NP-hard problems,and their globally optimal solutions are usually difficult to solve.Therefore,great attention has been attracted to the algorithms of searching the globally optimal solution or near-optimal solution for the combinatorial optimization problems.As a typical combinatorial optimization problem,the traveling salesman problem(TSP)often serves as a touchstone for novel approaches.It has been found that natural systems,particularly brain nervous systems,work at the critical region between order and disorder,namely,on the edge of chaos.In this work,an algorithm for the combinatorial optimization problems is proposed based on the neural networks on the edge of chaos(ECNN).The algorithm is then applied to TSPs of 10 cities,21 cities,48 cities and 70 cities.The results show that ECNN algorithm has strong ability to drive the networks away from local minimums.Compared with the transiently chaotic neural network(TCNN),the stochastic chaotic neural network(SCNN)algorithms and other optimization algorithms,much higher rates of globally optimal solutions and near-optimal solutions are obtained with ECNN algorithm.To conclude,our algorithm provides an effective way for solving the combinatorial optimization problems.
基金supported by National Natural Science Foundation of China(Grant Nos.T2350003,31930022,12131020 and T2341007)the National Basic Research Program of China(Grant No.2022YFA1004800)Strategic Priority Research Program of the Chinese Academy of Sciences(Grant No.XDB38040400)。
文摘Traditional operational research methods have been the primary means of solving combinatorial optimization problems(COPs)for the past few decades.However,with the rapid increase in the scale of problems in real-world scenarios and the demand for online optimization,these methods face persistent challenges including computational complexity and optimality.In recent years,combinatorial optimization methods based on deep learning have rapidly evolved,progressing from tackling solely small-scale problems(e.g.,the traveling salesman problem(TSP)with fewer than 100 cities)to swiftly delivering high-quality solutions for graphs containing up to a million nodes.Particularly,in the last two years,a multitude of studies has surfaced,demonstrating the ability to generalize learned models to large-scale problems with diverse distributions.This capability empowers deep learning-based methods to demonstrate robust competitiveness,even when challenged by professional solvers.Consequently,this review summarizes the methods employed in recent years for solving COPs through deep learning(including prompt learning),scrutinizes the strengths and weaknesses of these methods,and concludes by highlighting potential directions for mitigating these weaknesses.
基金supported by the National Natural Science Foundation of China(No.62102002).
文摘Multiobjective combinatorial optimization(MOCO)problems have a wide range of applications in the real world.Recently,learning-based methods have achieved good results in solving MOCO problems.However,most of these methods use attention mechanisms and their variants,which have room for further improvement in the speed of solving MOCO problems.In this paper,following the idea of decomposition strategy and neural combinatorial optimization,a novel fast-solving model for MOCO based on retention is proposed.A brand new calculation of retention is proposed,causal masking and exponential decay are deprecated in retention,so that our model could better solve MOCO problems.During model training,a parallel computation of retention is applied,allowing for fast parallel training.When using the model to solve MOCO problems,a recurrent computation of retention is applied,enabling quicker problem-solving.In order to make our model more practical and flexible,a preference-based retention decoder is proposed,which allows generating approximate Pareto solutions for any trade-off preferences directly.An industry-standard deep reinforcement learning algorithm is used to train RM-MOCO.Experimental results show that,while ensuring the quality of problem solving,the proposed method significantly outperforms some other methods in terms of the speed of solving MOCO problems.
基金supported by the National Natural Science Foundation of China(Nos.62173258 and 61773296).
文摘Combinatorial Optimization Problems(COPs)are a class of optimization problems that are commonly encountered in industrial production and everyday life.Over the last few decades,traditional algorithms,such as exact algorithms,approximate algorithms,and heuristic algorithms,have been proposed to solve COPs.However,as COPs in the real world become more complex,traditional algorithms struggle to generate optimal solutions in a limited amount of time.Since Deep Neural Networks(DNNs)are not heavily dependent on expert knowledge and are adequately flexible for generalization to various COPs,several DNN-based algorithms have been proposed in the last ten years for solving COPs.Herein,we categorize these algorithms into four classes and provide a brief overview of their applications in real-world problems.
基金supported by National Natural Science Foundation of China(Grant Nos.11991021,11991020 and 12271503)。
文摘Combinatorial optimization(CO)on graphs is a classic topic that has been extensively studied across many scientific and industrial fields.Recently,solving CO problems on graphs through learning methods has attracted great attention.Advanced deep learning methods,e.g.,graph neural networks(GNNs),have been used to effectively assist the process of solving COs.However,current frameworks based on GNNs are mainly designed for certain CO problems,thereby failing to consider their transferable and generalizable abilities among different COs on graphs.Moreover,simply using original graphs to model COs only captures the direct correlations among objects,which does not consider the mathematical logicality and properties of COs.In this paper,we propose a unified pre-training and adaptation framework for COs on graphs with the help of the maximum satisfiability(Max-SAT)problem.We first use Max-SAT to bridge different COs on graphs since they can be converted to Max-SAT problems represented by standard formulas and clauses with logical information.Then we further design a pre-training and domain adaptation framework to extract the transferable and generalizable features so that different COs can benefit from them.In the pre-training stage,Max-SAT instances are generated to initialize the parameters of the model.In the fine-tuning stage,instances from CO and Max-SAT problems are used for adaptation so that the transferable ability can be further improved.Numerical experiments on several datasets show that features extracted by our framework exhibit superior transferability and Max-SAT can boost the ability to solve COs on graphs.
基金Supported by the National Natural Science Foundation of China(42130605)Shenzhen Science and Technology Program(JCYJ20210324131810029)Guangdong Province Introduction of Innovative Research and Development Team Project China(2019ZT08G669)。
文摘Each physical process in a numerical weather prediction(NWP)system may have many different parameterization schemes.Early studies have shown that the performance of different physical parameterization schemes varies with the weather situation to be simulated.Thus,it is necessary to select a suitable combination of physical parameterization schemes according to the variation of weather systems.However,it is rather difficult to identify an optimal combination among millions of possible parameterization scheme combinations.This study applied a simple genetic algorithm(SGA)to optimizing the combination of parameterization schemes in NWP models for typhoon forecasting.The feasibility of SGA was verified with the simulation of Typhoon Mujigae(2015)by using the Weather Research and Forecasting(WRF)model and Typhoon Higos(2020)by using the Coupled Ocean–Atmosphere–Wave–Sediment Transport(COAWST)modeling system.The results show that SGA can efficiently obtain the optimal combination of schemes.For Typhoon Mujigae(2015),the optimal combination can be found from the 1,304,576 possible combinations by running only 488 trials.Similar results can be obtained for Typhoon Higos(2020).Compared to the default combination proposed by the COAWST model system,the optimal combination scheme significantly improves the simulation of typhoon track and intensity.This study provides a feasible way to search for the optimal combinations of physical parameterization schemes in WRF and COAWST for more accurate typhoon simulation.This can help provide references for future development of NWP models,and for analyzing the coordination and adaptability of different physical process parameterization schemes under specific weather backgrounds.
基金supported by the Fundamental Research Funds for the Central Universities(No.2024JBZX029)Shijiazhuang High Level Science and Technology Innovation and Entrepreneurship Talent Project(No.08202307)the National Natural Science Foundation of China(NSFC)(No.22173004).
文摘The optimization of polymer structures aims to determine an optimal sequence or topology that achieves a given target property or structural performance.This inverse design problem involves searching within a vast combinatorial phase space defined by components,se-quences,and topologies,and is often computationally intractable due to its NP-hard nature.At the core of this challenge lies the need to evalu-ate complex correlations among structural variables,a classical problem in both statistical physics and combinatorial optimization.To address this,we adopt a mean-field approach that decouples direct variable-variable interactions into effective interactions between each variable and an auxiliary field.The simulated bifurcation(SB)algorithm is employed as a mean-field-based optimization framework.It constructs a Hamiltonian dynamical system by introducing generalized momentum fields,enabling efficient decoupling and dynamic evolution of strongly coupled struc-tural variables.Using the sequence optimization of a linear copolymer adsorbing on a solid surface as a case study,we demonstrate the applica-bility of the SB algorithm to high-dimensional,non-differentiable combinatorial optimization problems.Our results show that SB can efficiently discover polymer sequences with excellent adsorption performance within a reasonable computational time.Furthermore,it exhibits robust con-vergence and high parallel scalability across large design spaces.The approach developed in this work offers a new computational pathway for polymer structure optimization.It also lays a theoretical foundation for future extensions to topological design problems,such as optimizing the number and placement of side chains,as well as the co-optimization of sequence and topology.
文摘Combinatorial optimization problems are found in many application fields such as computer science, engineering and economy. In this paper, a new efficient meta-heuristic, Intersection-Based Scaling (IBS for abbreviation), is proposed and it can be applied to the combinatorial optimization problems. The main idea of IBS is to scale the size of the instance based on the intersection of some local optima, and to simplify the search space by extracting the intersection from the instance, which makes the search more efficient. The combination of IBS with some local search heuristics of different combinatorial optimization problems such as Traveling Salesman Problem (TSP) and Graph Partitioning Problem (GPP) is studied, and comparisons are made with some of the best heuristic algorithms and meta-heuristic algorithms. It is found that it has significantly improved the performance of existing local search heuristics and significantly outperforms the known best algorithms. Keywords combinatorial optimization - TSP (Traveling Salesman Problem) - GPP (Graph Partitioning Problem) - IBS (Intersection-Based Scaling) - meta heuristic Regular PaperThis work is supported by the National Basic Research 973 Program of China (Grant No.TG1998030401).Peng Zou was born in 1979. He received the B.S. degree in computer software from University of Science and Technology of China (USTC) in 2000. Now he is a Ph.D. candidate in computer science of USTC. His current research interests include algorithms for NP-hard problems and parallel computing.Zhi Zhou was born in 1976. He received the B.S. degree in computer software from USTC in 1995. Now he is a Ph.D. candidate in computer science of USTC. His current research interests include combinatorial problem and parallel computing.Ying-Yu Wan was born in 1976. He received the B.S. degree in computer software from USTC in 1997, and the Ph.D. degree from USTC in 2002. His current research interests include parallel computing and combinatorial problem.Guo-Liang Chen was born in 1938. Now he is an Academician of CAS and Ph.D. supervisor in Department of Computer Science at USTC, director of the National High Performance Computing Center at Hefei. His current research interests include parallel computing, computer architecture and combinatorial optimization.Jun Gu was born in 1956. He received the B.S. degree in electronic engineering from USTC in 1982, and the Ph.D. degree in computer science from University of Utah. Now he is a professor and Ph.D. supervisor in computer science at USTC and Hong Kong University of Science and Technology. His main research interrests include algorithms for NP-hard problems.
基金the National Basic Research Program of China(Nos.2015CB358700,2011CBA00300 and 2011CBA00301)the National Natural Science Foundation of China(Nos.61202009,61033001 and 61361136003).
文摘Stochastic optimization has established itself as a major method to handle uncertainty in various optimization problems by modeling the uncertainty by a probability distribution over possible realizations.Traditionally,the main focus in stochastic optimization has been various stochastic mathematical programming(such as linear programming,convex programming).In recent years,there has been a surge of interest in stochastic combinatorial optimization problems from the theoretical computer science community.In this article,we survey some of the recent results on various stochastic versions of classical combinatorial optimization problems.Since most problems in this domain are NP-hard(or#P-hard,or even PSPACE-hard),we focus on the results which provide polynomial time approximation algorithms with provable approximation guarantees.Our discussions are centered around a few representative problems,such as stochastic knapsack,stochastic matching,multi-armed bandit etc.We use these examples to introduce several popular stochastic models,such as the fixed-set model,2-stage stochastic optimization model,stochastic adaptive probing model etc,as well as some useful techniques for designing approximation algorithms for stochastic combinatorial optimization problems,including the linear programming relaxation approach,boosted sampling,content resolution schemes,Poisson approximation etc.We also provide some open research questions along the way.Our purpose is to provide readers a quick glimpse to the models,problems,and techniques in this area,and hopefully inspire new contributions.
文摘Selecting the best type of equipment among available switches with different prices and reliability levels is a significant challenge in distribution system planning.In this paper,the optimal type of switches in a radial distribution system is selected by considering the total cost and reliability criterion and using the weighted augmented epsilon constraint method and combinatorial optimization.A new index is calculated to assess the robustness of each Pareto solution.Moreover,for each failure,repair time is considered based on historical data.Monte Carlo simulations are used to consider the switch failure uncertainty and fault repair time uncertainty in the model.The proposed framework is applied to an RTBS Bus-2 test system.Furthermore,the model is also applied to an industrial system to verify the proposed method’s excellent performance in larger practical engineering problems.
基金the National Natural Science Foundation of China(Grant Nos.61832003,61761136014,61872334)the 973 Program of China(2016YFB1000201)K.C.Wong Education Foundation.
文摘Combinatorial optimization in the face of uncertainty is a challenge in both operational research and machine learning.In this paper,we consider a special and important class called the adversarial online combinatorial optimization with semi-bandit feedback,in which a player makes combinatorial decisions and gets the corresponding feedback repeatedly.While existing algorithms focus on the regret guarantee or assume there exists an efficient offline oracle,it is still a challenge to solve this problem efficiently if the offline counterpart is NP-hard.In this paper,we propose a variant of the Follow-the-Perturbed-Leader(FPL)algorithm to solve this problem.Unlike the existing FPL approach,our method employs an approximation algorithm as an offline oracle and perturbs the collected data by adding nonnegative random variables.Our ap-proach is simple and computationally efficient.Moreover,it can guarantee a sublinear(1+ε)-scaled regret of order O(T^(2/3))for any smallε>0 for an important class of combinatorial optimization problems that admit an FPTAS(fully polynomial time approximation scheme),in which T is the number of rounds of the learning process.In addition to the theoretical analysis,we also conduct a series of experiments to demonstrate the performance of our algorithm.
基金supported by the National Natural Science Foundation of China (61473179)the Natural Science Foundation of Shandong Province (ZR2016FM18 ZR2017LF004)+2 种基金the Project of Shandong Province Higher Education Science and Technology Program (J16LN20)the Youth Innovation Team Development Plan of Shandong Province Higher Enducation (2019KJN048)the International Cooperation Training Project of Shandong Province (2016)
文摘To improve the evolutionary algorithm performance,especially in convergence speed and global optimization ability,a self-adaptive mechanism is designed both for the conventional genetic algorithm(CGA)and the quantum inspired genetic algorithm(QIGA).For the self-adaptive mechanism,each individual was assigned with suitable evolutionary parameter according to its current evolutionary state.Therefore,each individual can evolve toward to the currently best solution.Moreover,to reduce the running time of the proposed self-adaptive mechanism-based QIGA(SAM-QIGA),a multi-universe parallel structure was employed in the paper.Simulation results show that the proposed SAM-QIGA have better performances both in convergence and global optimization ability.
基金Project supported by the National Natural Science Foundation of China(Nos.61832020,62032001,92064006,and 62274036)the Beijing Academy of Artificial Intelligence(BAAI)of Chinathe 111 Project of China(No.B18001)。
文摘The combinatorial optimization problem(COP),which aims to find the optimal solution in discrete space,is fundamental in various fields.Unfortunately,many COPs are NP-complete,and require much more time to solve as the problem scale increases.Troubled by this,researchers may prefer fast methods even if they are not exact,so approximation algorithms,heuristic algorithms,and machine learning have been proposed.Some works proposed chaotic simulated annealing(CSA)based on the Hopfield neural network and did a good job.However,CSA is not something that current general-purpose processors can handle easily,and there is no special hardware for it.To efficiently perform CSA,we propose a software and hardware co-design.In software,we quantize the weight and output using appropriate bit widths,and then modify the calculations that are not suitable for hardware implementation.In hardware,we design a specialized processing-in-memory hardware architecture named COPPER based on the memristor.COPPER is capable of efficiently running the modified quantized CSA algorithm and supporting the pipeline further acceleration.The results show that COPPER can perform CSA remarkably well in both speed and energy.
基金Research is supported by the National 863 Program ( No.863- 306- Z T
文摘Assume there are several states, and the objective function f\+s(x) is linked with each state s. Robust optimization is to solve the following problem: min x∈X max s∈Sf\+s(x)where X is the feasible solution set, and S is the collection of states.\;It has been showed that most of robust combinatorial optimization problems are NP\|hard in strong sense. In this paper, we will discuss the borderline between the ′easy′ and the ′hard′ cases of robust combinatorial optimization problems, and further present a heuristic frame work to solve the ′hard′ problems and discuss their concrete implementation of the heuristic method.
文摘This paper provides an overview on the current status of the researches in the field of neural algorithms for combinatorial optimization and makes some comments on the recent development. Meanwhile,we point out that such optimization networks suffer from some serious problems. At the end of this paper, we present the readers some aspects which need more researches in the future.
