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.展开更多
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.展开更多
The Vehicle Routing Problem with Time Windows(VRPTW)presents a significant challenge in combinatorial optimization,especially under real-world uncertainties such as variable travel times,service durations,and dynamic ...The Vehicle Routing Problem with Time Windows(VRPTW)presents a significant challenge in combinatorial optimization,especially under real-world uncertainties such as variable travel times,service durations,and dynamic customer demands.These uncertainties make traditional deterministic models inadequate,often leading to suboptimal or infeasible solutions.To address these challenges,this work proposes an adaptive hybrid metaheuristic that integrates Genetic Algorithms(GA)with Local Search(LS),while incorporating stochastic uncertainty modeling through probabilistic travel times.The proposed algorithm dynamically adjusts parameters—such as mutation rate and local search probability—based on real-time search performance.This adaptivity enhances the algorithm’s ability to balance exploration and exploitation during the optimization process.Travel time uncertainties are modeled using Gaussian noise,and solution robustness is evaluated through scenario-based simulations.We test our method on a set of benchmark problems from Solomon’s instance suite,comparing its performance under deterministic and stochastic conditions.Results show that the proposed hybrid approach achieves up to a 9%reduction in expected total travel time and a 40% reduction in time window violations compared to baseline methods,including classical GA and non-adaptive hybrids.Additionally,the algorithm demonstrates strong robustness,with lower solution variance across uncertainty scenarios,and converges faster than competing approaches.These findings highlight the method’s suitability for practical logistics applications such as last-mile delivery and real-time transportation planning,where uncertainty and service-level constraints are critical.The flexibility and effectiveness of the proposed framework make it a promising candidate for deployment in dynamic,uncertainty-aware supply chain environments.展开更多
The quantum alternating operator ansatz algorithm(QAOA+)is widely used for constrained combinatorial optimization problems(CCOPs)due to its ability to construct feasible solution spaces.In this paper,we propose a prog...The quantum alternating operator ansatz algorithm(QAOA+)is widely used for constrained combinatorial optimization problems(CCOPs)due to its ability to construct feasible solution spaces.In this paper,we propose a progressive quantum algorithm(PQA)to reduce qubit requirements for QAOA+in solving the maximum independent set(MIS)problem.PQA iteratively constructs a subgraph likely to include the MIS solution of the original graph and solves the problem on it to approximate the global solution.Specifically,PQA starts with a small-scale subgraph and progressively expands its graph size utilizing heuristic expansion strategies.After each expansion,PQA solves the MIS problem on the newly generated subgraph using QAOA+.In each run,PQA repeats the expansion and solving process until a predefined stopping condition is reached.Simulation results show that PQA achieves an approximation ratio of 0.95 using only 5.57%(2.17%)of the qubits and 17.59%(6.43%)of the runtime compared with directly solving the original problem with QAOA+on Erd?s-Rényi(3-regular)graphs,highlighting the efficiency and scalability of PQA.展开更多
In the context of reducing its carbon emissions,the Chinese steel industry is currently undergoing an intelligent transformation to enhance its profitability and sustainability.The optimization of production planning ...In the context of reducing its carbon emissions,the Chinese steel industry is currently undergoing an intelligent transformation to enhance its profitability and sustainability.The optimization of production planning and scheduling plays a pivotal role in realizing these objectives such as improving production efficiency,saving energy,reducing carbon emissions,and enhancing quality.However,current practices in steel enterprises are largely dependent on experience-driven manual decision approaches supported by information systems,which are inadequate to meet the complex requirements of the industry.This study explores the current situation in production planning and scheduling,analyzes the characteristics and limitations of existing methods,and emphasizes the necessity and trends of intelligent systems.It surveys the current literature on production planning and scheduling in steel enterprises and analyzes the theoretical advancements and practical challenges associated with combinatorial and sequential optimization in this field.A key focus is on the limitations of current models and algorithms in effectively addressing the multi-objective and multiconstraint characteristics of steel produc-tion.To overcome these challenges,a novel framework for intelligent production planning and scheduling is proposed.This framework leverages data-and knowledge-driven decision-making and scenario adaptability,enabling the system to respond dynamically to real-time production conditions and market fluctuations.By integrating artificial intelligence and advanced optimization methodologies,the proposed framework improves the efficiency,cost-effectiveness,and environmental sustainability of steel manufacturing.展开更多
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.展开更多
The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with...The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with respect to the size of a graph.No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale.However,several algorithms are proposed that solve the problem approximately in a short polynomial time scale.Such algorithms are useful for large size graphs,for which exact solution of MVCP is impossible with current computational resources.The MVCP has a wide range of applications in the fields like bioinformatics,biochemistry,circuit design,electrical engineering,data aggregation,networking,internet traffic monitoring,pattern recognition,marketing and franchising etc.This work aims to solve the MVCP approximately by a novel graph decomposition approach.The decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures.A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or paths.In order to reduce complexity of the algorithm a new strategy is also proposed.The reduction strategy can be used for any algorithm solving MVCP.Based on the graph decomposition and the reduction strategy,two algorithms are formulated to approximately solve the MVCP.These algorithms are tested using well known standard benchmark graphs.The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.展开更多
Much of our daily tasks have been computerized by machines and sensors communicating with each other in real-time.There is a reasonable risk that something could go wrong because there are a lot of sensors producing a...Much of our daily tasks have been computerized by machines and sensors communicating with each other in real-time.There is a reasonable risk that something could go wrong because there are a lot of sensors producing a lot of data.Combinatorial testing(CT)can be used in this case to reduce risks and ensure conformance to specifications.Numerous existing metaheuristic-based solutions aim to assist the test suite generation for combinatorial testing,also known as t-way testing(where t indicates the interaction strength),viewed as an optimization problem.Much previous research,while helpful,only investigated a small number of interaction strengths up to t=6.For lightweight applications,research has demonstrated good fault-finding ability.However,the number of interaction strengths considered must be higher in the case of interactions that generate large amounts of data.Due to resource restrictions and the combinatorial explosion challenge,little work has been done to produce high-order interaction strength.In this context,the Whale Optimization Algorithm(WOA)is proposed to generate high-order interaction strength.To ensure that WOA conquers premature convergence and avoids local optima for large search spaces(owing to high-order interaction),three variants of WOA have been developed,namely Structurally Modified Whale Optimization Algorithm(SWOA),Tolerance Whale Optimization Algorithm(TWOA),and Tolerance Structurally Modified Whale Optimization Algorithm(TSWOA).Our experiments show that the third strategy gives the best performance and is comparable to existing state-of-thearts based strategies.展开更多
University timetabling problems are a yearly challenging task and are faced repeatedly each semester.The problems are considered nonpolynomial time(NP)and combinatorial optimization problems(COP),which means that they...University timetabling problems are a yearly challenging task and are faced repeatedly each semester.The problems are considered nonpolynomial time(NP)and combinatorial optimization problems(COP),which means that they can be solved through optimization algorithms to produce the aspired optimal timetable.Several techniques have been used to solve university timetabling problems,and most of them use optimization techniques.This paper provides a comprehensive review of the most recent studies dealing with concepts,methodologies,optimization,benchmarks,and open issues of university timetabling problems.The comprehensive review starts by presenting the essence of university timetabling as NP-COP,defining and clarifying the two formed classes of university timetabling:University Course Timetabling and University Examination Timetabling,illustrating the adopted algorithms for solving such a problem,elaborating the university timetabling constraints to be considered achieving the optimal timetable,and explaining how to analyze and measure the performance of the optimization algorithms by demonstrating the commonly used benchmark datasets for the evaluation.It is noted that meta-heuristic methodologies are widely used in the literature.Additionally,recently,multi-objective optimization has been increasingly used in solving such a problem that can identify robust university timetabling solutions.Finally,trends and future directions in university timetabling problems are provided.This paper provides good information for students,researchers,and specialists interested in this area of research.The challenges and possibilities for future research prospects are also explored.展开更多
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.展开更多
The definition of local optimum solution of the discrete optimization is first given.and then a comprehensive combinatorial algorithm is proposed in this paper. Two-leveloptimum method is used in the algorithm. In t...The definition of local optimum solution of the discrete optimization is first given.and then a comprehensive combinatorial algorithm is proposed in this paper. Two-leveloptimum method is used in the algorithm. In the first level optimization, anapproximate local optimum solution X is found by using the heuristic algorithm,relative difference quotient algorithm. with high computational efficiency and highperformance demonstrated by the performance test of random samples. In the secondlevel, a mathematical model of (- 1, 0, 1) programming is established first, and then itis changed into (0, 1) programming model. The local optimum solution X will befrom the (0. 1) programming by using the delimitative and combinatorial algorithm orthe relative difference quotient algorithm. By this algorithm, the local optimumsolution can be obtained certainly, and a method is provnded to judge whether or notthe approximate optimum solution obtained by heuristic algorithm is an optimumsolution. The above comprehensive combinatorial algorithm has higher computationalefficiency.展开更多
The problem of social workers visiting their patients at home is a class of combinatorial optimization problems and belongs to the class of problems known as NP-Hard. These problems require heuristic techniques to pro...The problem of social workers visiting their patients at home is a class of combinatorial optimization problems and belongs to the class of problems known as NP-Hard. These problems require heuristic techniques to provide an efficient solution in the best of cases. In this article, in addition to providing a detailed resolution of the social workers’ problem using the Quadratic Unconstrained Binary Optimization Problems (QUBO) formulation, an approach to mapping the inequality constraints in the QUBO form is given. Finally, we map it in the Hamiltonian of the Ising model to solve it with the Quantum Exact Solver and Variational Quantum Eigensolvers (VQE). The quantum feasibility of the algorithm will be tested on IBMQ computers.展开更多
The concept of the combinatorial discovery and optimization of new materials, and its background,importance, and application, as well as its current status in the world, are briefly reviewed in this paper.
Traveling salesman problem(TSP)is a classic non-deterministic polynomial-hard optimization prob-lem.Based on the characteristics of self-organizing mapping(SOM)network,this paper proposes an improved SOM network from ...Traveling salesman problem(TSP)is a classic non-deterministic polynomial-hard optimization prob-lem.Based on the characteristics of self-organizing mapping(SOM)network,this paper proposes an improved SOM network from the perspectives of network update strategy,initialization method,and parameter selection.This paper compares the performance of the proposed algorithms with the performance of existing SOM network algorithms on the TSP and compares them with several heuristic algorithms.Simulations show that compared with existing SOM networks,the improved SOM network proposed in this paper improves the convergence rate and algorithm accuracy.Compared with iterated local search and heuristic algorithms,the improved SOM net-work algorithms proposed in this paper have the advantage of fast calculation speed on medium-scale TSP.展开更多
The All-pairs shortest path problem(ALL-SPP)aims to find the shortest path joining all the vertices in a given graph.This study proposed a new optimal method,Dhouib-matrix-ALL-SPP(DM-ALL-SPP)to solve the ALL-SPP based...The All-pairs shortest path problem(ALL-SPP)aims to find the shortest path joining all the vertices in a given graph.This study proposed a new optimal method,Dhouib-matrix-ALL-SPP(DM-ALL-SPP)to solve the ALL-SPP based on column-row navigation through the adjacency matrix.DM-ALL-SPP is designed to generate in a single execution the shortest path with details among all-pairs of vertices for a graph with positive and negative weighted edges.Even for graphs with a negative cycle,DM-ALL-SPP reported a negative cycle.In addition,DM-ALL-SPP continues to work for directed,undirected and mixed graphs.Furthermore,it is characterized by two phases:the first phase consists of adding by column repeated(n)iterations(where n is the number of vertices),and the second phase resides in adding by row executed in the worst case(n∗log(n))iterations.The first phase,focused on improving the elements of each column by adding their values to each row and modifying them with the smallest value.The second phase is emphasized by rows only for the elements modified in the first phase.Different instances from the literature were used to test the performance of the proposed DM-ALL-SPP method,which was developed using the Python programming language and the results were compared to those obtained by the Floyd-Warshall algorithm.展开更多
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.展开更多
基金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.
基金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.
文摘The Vehicle Routing Problem with Time Windows(VRPTW)presents a significant challenge in combinatorial optimization,especially under real-world uncertainties such as variable travel times,service durations,and dynamic customer demands.These uncertainties make traditional deterministic models inadequate,often leading to suboptimal or infeasible solutions.To address these challenges,this work proposes an adaptive hybrid metaheuristic that integrates Genetic Algorithms(GA)with Local Search(LS),while incorporating stochastic uncertainty modeling through probabilistic travel times.The proposed algorithm dynamically adjusts parameters—such as mutation rate and local search probability—based on real-time search performance.This adaptivity enhances the algorithm’s ability to balance exploration and exploitation during the optimization process.Travel time uncertainties are modeled using Gaussian noise,and solution robustness is evaluated through scenario-based simulations.We test our method on a set of benchmark problems from Solomon’s instance suite,comparing its performance under deterministic and stochastic conditions.Results show that the proposed hybrid approach achieves up to a 9%reduction in expected total travel time and a 40% reduction in time window violations compared to baseline methods,including classical GA and non-adaptive hybrids.Additionally,the algorithm demonstrates strong robustness,with lower solution variance across uncertainty scenarios,and converges faster than competing approaches.These findings highlight the method’s suitability for practical logistics applications such as last-mile delivery and real-time transportation planning,where uncertainty and service-level constraints are critical.The flexibility and effectiveness of the proposed framework make it a promising candidate for deployment in dynamic,uncertainty-aware supply chain environments.
基金supported by the National Natural Science Foundation of China(Grant Nos.62371069,62372048,and 62272056)BUPT Excellent Ph.D.Students Foundation(Grant No.CX2023123)。
文摘The quantum alternating operator ansatz algorithm(QAOA+)is widely used for constrained combinatorial optimization problems(CCOPs)due to its ability to construct feasible solution spaces.In this paper,we propose a progressive quantum algorithm(PQA)to reduce qubit requirements for QAOA+in solving the maximum independent set(MIS)problem.PQA iteratively constructs a subgraph likely to include the MIS solution of the original graph and solves the problem on it to approximate the global solution.Specifically,PQA starts with a small-scale subgraph and progressively expands its graph size utilizing heuristic expansion strategies.After each expansion,PQA solves the MIS problem on the newly generated subgraph using QAOA+.In each run,PQA repeats the expansion and solving process until a predefined stopping condition is reached.Simulation results show that PQA achieves an approximation ratio of 0.95 using only 5.57%(2.17%)of the qubits and 17.59%(6.43%)of the runtime compared with directly solving the original problem with QAOA+on Erd?s-Rényi(3-regular)graphs,highlighting the efficiency and scalability of PQA.
基金supported by the Key Program of the National Natural Science Foundation of China(Nos.52334008 and 51734004).
文摘In the context of reducing its carbon emissions,the Chinese steel industry is currently undergoing an intelligent transformation to enhance its profitability and sustainability.The optimization of production planning and scheduling plays a pivotal role in realizing these objectives such as improving production efficiency,saving energy,reducing carbon emissions,and enhancing quality.However,current practices in steel enterprises are largely dependent on experience-driven manual decision approaches supported by information systems,which are inadequate to meet the complex requirements of the industry.This study explores the current situation in production planning and scheduling,analyzes the characteristics and limitations of existing methods,and emphasizes the necessity and trends of intelligent systems.It surveys the current literature on production planning and scheduling in steel enterprises and analyzes the theoretical advancements and practical challenges associated with combinatorial and sequential optimization in this field.A key focus is on the limitations of current models and algorithms in effectively addressing the multi-objective and multiconstraint characteristics of steel produc-tion.To overcome these challenges,a novel framework for intelligent production planning and scheduling is proposed.This framework leverages data-and knowledge-driven decision-making and scenario adaptability,enabling the system to respond dynamically to real-time production conditions and market fluctuations.By integrating artificial intelligence and advanced optimization methodologies,the proposed framework improves the efficiency,cost-effectiveness,and environmental sustainability of steel manufacturing.
基金supported by National Natural Science Foundation of China(61425008,61333004,61273054)Top-Notch Young Talents Program of China,and Aeronautical Foundation of China(2013585104)
基金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.
文摘The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with respect to the size of a graph.No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale.However,several algorithms are proposed that solve the problem approximately in a short polynomial time scale.Such algorithms are useful for large size graphs,for which exact solution of MVCP is impossible with current computational resources.The MVCP has a wide range of applications in the fields like bioinformatics,biochemistry,circuit design,electrical engineering,data aggregation,networking,internet traffic monitoring,pattern recognition,marketing and franchising etc.This work aims to solve the MVCP approximately by a novel graph decomposition approach.The decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures.A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or paths.In order to reduce complexity of the algorithm a new strategy is also proposed.The reduction strategy can be used for any algorithm solving MVCP.Based on the graph decomposition and the reduction strategy,two algorithms are formulated to approximately solve the MVCP.These algorithms are tested using well known standard benchmark graphs.The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.
基金This work was supported by the Ministry of Education,Malaysia(FRGS/1/2019/ICT02/UKM/01/1)the Universiti Kebangsaan Malaysia(DIP-2016-024).
文摘Much of our daily tasks have been computerized by machines and sensors communicating with each other in real-time.There is a reasonable risk that something could go wrong because there are a lot of sensors producing a lot of data.Combinatorial testing(CT)can be used in this case to reduce risks and ensure conformance to specifications.Numerous existing metaheuristic-based solutions aim to assist the test suite generation for combinatorial testing,also known as t-way testing(where t indicates the interaction strength),viewed as an optimization problem.Much previous research,while helpful,only investigated a small number of interaction strengths up to t=6.For lightweight applications,research has demonstrated good fault-finding ability.However,the number of interaction strengths considered must be higher in the case of interactions that generate large amounts of data.Due to resource restrictions and the combinatorial explosion challenge,little work has been done to produce high-order interaction strength.In this context,the Whale Optimization Algorithm(WOA)is proposed to generate high-order interaction strength.To ensure that WOA conquers premature convergence and avoids local optima for large search spaces(owing to high-order interaction),three variants of WOA have been developed,namely Structurally Modified Whale Optimization Algorithm(SWOA),Tolerance Whale Optimization Algorithm(TWOA),and Tolerance Structurally Modified Whale Optimization Algorithm(TSWOA).Our experiments show that the third strategy gives the best performance and is comparable to existing state-of-thearts based strategies.
基金This research work was supported by the University Malaysia Sabah,Malaysia.
文摘University timetabling problems are a yearly challenging task and are faced repeatedly each semester.The problems are considered nonpolynomial time(NP)and combinatorial optimization problems(COP),which means that they can be solved through optimization algorithms to produce the aspired optimal timetable.Several techniques have been used to solve university timetabling problems,and most of them use optimization techniques.This paper provides a comprehensive review of the most recent studies dealing with concepts,methodologies,optimization,benchmarks,and open issues of university timetabling problems.The comprehensive review starts by presenting the essence of university timetabling as NP-COP,defining and clarifying the two formed classes of university timetabling:University Course Timetabling and University Examination Timetabling,illustrating the adopted algorithms for solving such a problem,elaborating the university timetabling constraints to be considered achieving the optimal timetable,and explaining how to analyze and measure the performance of the optimization algorithms by demonstrating the commonly used benchmark datasets for the evaluation.It is noted that meta-heuristic methodologies are widely used in the literature.Additionally,recently,multi-objective optimization has been increasingly used in solving such a problem that can identify robust university timetabling solutions.Finally,trends and future directions in university timetabling problems are provided.This paper provides good information for students,researchers,and specialists interested in this area of research.The challenges and possibilities for future research prospects are also explored.
基金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.
文摘The definition of local optimum solution of the discrete optimization is first given.and then a comprehensive combinatorial algorithm is proposed in this paper. Two-leveloptimum method is used in the algorithm. In the first level optimization, anapproximate local optimum solution X is found by using the heuristic algorithm,relative difference quotient algorithm. with high computational efficiency and highperformance demonstrated by the performance test of random samples. In the secondlevel, a mathematical model of (- 1, 0, 1) programming is established first, and then itis changed into (0, 1) programming model. The local optimum solution X will befrom the (0. 1) programming by using the delimitative and combinatorial algorithm orthe relative difference quotient algorithm. By this algorithm, the local optimumsolution can be obtained certainly, and a method is provnded to judge whether or notthe approximate optimum solution obtained by heuristic algorithm is an optimumsolution. The above comprehensive combinatorial algorithm has higher computationalefficiency.
文摘The problem of social workers visiting their patients at home is a class of combinatorial optimization problems and belongs to the class of problems known as NP-Hard. These problems require heuristic techniques to provide an efficient solution in the best of cases. In this article, in addition to providing a detailed resolution of the social workers’ problem using the Quadratic Unconstrained Binary Optimization Problems (QUBO) formulation, an approach to mapping the inequality constraints in the QUBO form is given. Finally, we map it in the Hamiltonian of the Ising model to solve it with the Quantum Exact Solver and Variational Quantum Eigensolvers (VQE). The quantum feasibility of the algorithm will be tested on IBMQ computers.
文摘The concept of the combinatorial discovery and optimization of new materials, and its background,importance, and application, as well as its current status in the world, are briefly reviewed in this paper.
基金the National Natural Science Foundation of China (No.61627810)the National Science and Technology Major Program of China (No.2018YFB1305003)the National Defense Science and Technology Outstanding Youth Science Foundation (No.2017-JCJQ-ZQ-031)。
文摘Traveling salesman problem(TSP)is a classic non-deterministic polynomial-hard optimization prob-lem.Based on the characteristics of self-organizing mapping(SOM)network,this paper proposes an improved SOM network from the perspectives of network update strategy,initialization method,and parameter selection.This paper compares the performance of the proposed algorithms with the performance of existing SOM network algorithms on the TSP and compares them with several heuristic algorithms.Simulations show that compared with existing SOM networks,the improved SOM network proposed in this paper improves the convergence rate and algorithm accuracy.Compared with iterated local search and heuristic algorithms,the improved SOM net-work algorithms proposed in this paper have the advantage of fast calculation speed on medium-scale TSP.
文摘The All-pairs shortest path problem(ALL-SPP)aims to find the shortest path joining all the vertices in a given graph.This study proposed a new optimal method,Dhouib-matrix-ALL-SPP(DM-ALL-SPP)to solve the ALL-SPP based on column-row navigation through the adjacency matrix.DM-ALL-SPP is designed to generate in a single execution the shortest path with details among all-pairs of vertices for a graph with positive and negative weighted edges.Even for graphs with a negative cycle,DM-ALL-SPP reported a negative cycle.In addition,DM-ALL-SPP continues to work for directed,undirected and mixed graphs.Furthermore,it is characterized by two phases:the first phase consists of adding by column repeated(n)iterations(where n is the number of vertices),and the second phase resides in adding by row executed in the worst case(n∗log(n))iterations.The first phase,focused on improving the elements of each column by adding their values to each row and modifying them with the smallest value.The second phase is emphasized by rows only for the elements modified in the first phase.Different instances from the literature were used to test the performance of the proposed DM-ALL-SPP method,which was developed using the Python programming language and the results were compared to those obtained by the Floyd-Warshall algorithm.
基金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.
