Learning to Branch in Combinatorial Optimization With Graph Pointer Networks

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.

Quafu-Qcover:Explore combinatorial optimization problems on cloud-based quantum computers

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.

Time Complexity of Evolutionary Algorithms for Combinatorial Optimization:A Decade of Results

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.

SOME COMBINATORIAL OPTIMIZATION PROBLEMS ARISING FROM VLSI CIRCUIT DESIGN

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.

Combinatorial Optimization Based Analog Circuit Fault Diagnosis with Back Propagation Neural Network

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.

A Combinatorial Optimized Knapsack Linear Space for Information Retrieval

Key information extraction can reduce the dimensional effects while evaluating the correct preferences of users during semantic data analysis.Currently,the classifiers are used to maximize the performance of web-page recommendation in terms of precision and satisfaction.The recent method disambiguates contextual sentiment using conceptual prediction with robustness,however the conceptual prediction method is not able to yield the optimal solution.Context-dependent terms are primarily evaluated by constructing linear space of context features,presuming that if the terms come together in certain consumerrelated reviews,they are semantically reliant.Moreover,the more frequently they coexist,the greater the semantic dependency is.However,the influence of the terms that coexist with each other can be part of the frequency of the terms of their semantic dependence,as they are non-integrative and their individual meaning cannot be derived.In this work,we consider the strength of a term and the influence of a term as a combinatorial optimization,called Combinatorial Optimized Linear Space Knapsack for Information Retrieval(COLSK-IR).The COLSK-IR is considered as a knapsack problem with the total weight being the“term influence”or“influence of term”and the total value being the“term frequency”or“frequency of term”for semantic data analysis.The method,by which the term influence and the term frequency are considered to identify the optimal solutions,is called combinatorial optimizations.Thus,we choose the knapsack for performing an integer programming problem and perform multiple experiments using the linear space through combinatorial optimization to identify the possible optimum solutions.It is evident from our experimental results that the COLSK-IR provides better results than previous methods to detect strongly dependent snippets with minimum ambiguity that are related to inter-sentential context during semantic data analysis.

Application of the edge of chaos in combinatorial optimization

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.

Combinatorial Discovery and Optimization of New Materials

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.

Three-Stages Hyperspectral Image Compression Sensing with Band Selection

Compressed sensing(CS),as an efficient data transmission method,has achieved great success in the field of data transmission such as image,video and text.It can robustly recover signals from fewer Measurements,effectively alleviating the bandwidth pressure during data transmission.However,CS has many shortcomings in the transmission of hyperspectral image(HSI)data.This work aims to consider the application of CS in the transmission of hyperspectral image(HSI)data,and provides a feasible research scheme for CS of HSI data.HSI has rich spectral information and spatial information in bands,which can reflect the physical properties of the target.Most of the hyperspectral image compressed sensing(HSICS)algorithms cannot effectively use the inter-band information of HSI,resulting in poor reconstruction effects.In this paper,A three-stage hyperspectral image compression sensing algorithm(Three-stages HSICS)is proposed to obtain intra-band and inter-band characteristics of HSI,which can improve the reconstruction accuracy of HSI.Here,we establish a multi-objective band selection(Mop-BS)model,amulti-hypothesis prediction(MHP)model and a residual sparse(ReWSR)model for HSI,and use a staged reconstruction method to restore the compressed HSI.The simulation results show that the three-stage HSICS successfully improves the reconstruction accuracy of HSICS,and it performs best among all comparison algorithms.

Dendritic Cell Algorithm with Grouping Genetic Algorithm for Input Signal Generation

The artificial immune system,an excellent prototype for developingMachine Learning,is inspired by the function of the powerful natural immune system.As one of the prevalent classifiers,the Dendritic Cell Algorithm(DCA)has been widely used to solve binary problems in the real world.The classification of DCA depends on a data preprocessing procedure to generate input signals,where feature selection and signal categorization are themain work.However,the results of these studies also show that the signal generation of DCA is relatively weak,and all of them utilized a filter strategy to remove unimportant attributes.Ignoring filtered features and applying expertise may not produce an optimal classification result.To overcome these limitations,this study models feature selection and signal categorization into feature grouping problems.This study hybridizes Grouping Genetic Algorithm(GGA)with DCA to propose a novel DCA version,GGA-DCA,for accomplishing feature selection and signal categorization in a search process.The GGA-DCA aims to search for the optimal feature grouping scheme without expertise automatically.In this study,the data coding and operators of GGA are redefined for grouping tasks.The experimental results show that the proposed algorithm has significant advantages over the compared DCA expansion algorithms in terms of signal generation.

Optimization Techniques in University Timetabling Problem:Constraints,Methodologies,Benchmarks,and Open Issues

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.

A unified pre-training and adaptation framework for combinatorial optimization on graphs

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.

Combinatorial Optimization of Physics Parameterization Schemes for Typhoon Simulation Based on a Simple Genetic Algorithm(SGA)

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.

A Gene-Pool Based Genetic Algorithm for TSP

Based on the analysis of previous genetic algorithms (GAs) for TSP, a novel method called Ge- GA is proposed. It combines gene pool and GA so as to direct the evolution of the whole population. The core of Ge- GA is the construction of gene pool and how to apply it to GA. Different from standard GAs, Ge- GA aims to enhance the ability of exploration and exploitation by incorporating global search with local search. On one hand a local search called Ge- Lo-calSearch operator is proposed to improve the solution quality, on the other hand the modified Inver-Over operator called Ge InverOver is considered as a global search mechanism to expand solution space of local minimal. Both of these operators are based on the gene pool. Our algorithm is applied to 11 well-known traveling salesman problems whose numbers of cities are from 70 to 1577 cities. The experiments results indicate that Ge- GA has great robustness for TSP. For each test instance, the average value of solution quality, found in accepted time, stays within 0. 001% from the optimum.

Smart Cities in Europe and the ALMA Logistics Project

In this paper, a brief survey of smart citiy projects in Europe is presented. This survey shows the extent of transport and logistics in smart cities. We concentrate on a smart city project we have been working on that is related to A Logistic Mobile Application （ALMA）. The application is based on Internet of Things and combines a communication infrastructure and a High Performance Computing infrastructure in order to deliver mobile logistic services with high quality of service and adaptation to the dynamic nature of logistic operations.

Task scheduling for multi-electro-magnetic detection satellite with a combined algorithm

Task scheduling for electro-magnetic detection satellite is a typical combinatorial optimization problem. The count of constraints that need to be taken into account is of large scale. An algorithm combined integer programming with constraint programming is presented. This algorithm is deployed in this problem through two steps. The first step is to decompose the original problem into master and sub-problem using the logic-based Benders decomposition; then a circus combines master and sub-problem solving process together, and the connection between them is general Benders cut. This hybrid algorithm is tested by a set of derived experiments. The result is compared with corresponding outcomes generated by the strength Pareto evolutionary algorithm and the pure constraint programming solver GECODE, which is an open source software. These tests and comparisons yield promising effect.

Optimizing combination of aircraft maintenance tasks by adaptive genetic algorithm based on cluster search

It is significant to combine multiple tasks into an optimal work package in decision-making of aircraft maintenance to reduce cost,so a cost rate model of combinatorial maintenance is an urgent need.However,the optimal combination under various constraints not only involves numerical calculations but also is an NP-hard combinatorial problem.To solve the problem,an adaptive genetic algorithm based on cluster search,which is divided into two phases,is put forward.In the first phase,according to the density,all individuals can be homogeneously scattered over the whole solution space through crossover and mutation and better individuals are collected as candidate cluster centres.In the second phase,the search is confined to the neighbourhood of some selected possible solutions to accurately solve with cluster radius decreasing slowly,meanwhile all clusters continuously move to better regions until all the peaks in the question space is searched.This algorithm can efficiently solve the combination problem.Taking the optimization on decision-making of aircraft maintenance by the algorithm for an example,maintenance which combines multiple parts or tasks can significantly enhance economic benefit when the halt cost is rather high.

Binary Fruit Fly Swarm Algorithms for the Set Covering Problem

Currently,the industry is experiencing an exponential increase in dealing with binary-based combinatorial problems.In this sense,metaheuristics have been a common trend in the field in order to design approaches to solve them successfully.Thus,a well-known strategy consists in the use of algorithms based on discrete swarms transformed to perform in binary environments.Following the No Free Lunch theorem,we are interested in testing the performance of the Fruit Fly Algorithm,this is a bio-inspired metaheuristic for deducing global optimization in continuous spaces,based on the foraging behavior of the fruit fly,which usually has much better sensory perception of smell and vision than any other species.On the other hand,the Set Coverage Problem is a well-known NP-hard problem with many practical applications,including production line balancing,utility installation,and crew scheduling in railroad and mass transit companies.In this paper,we propose different binarization methods for the Fruit Fly Algorithm,using Sshaped and V-shaped transfer functions and various discretization methods to make the algorithm work in a binary search space.We are motivated with this approach,because in this way we can deliver to future researchers interested in this area,a way to be able to work with continuous metaheuristics in binary domains.This new approach was tested on benchmark instances of the Set Coverage Problem and the computational results show that the proposed algorithm is robust enough to produce good results with low computational cost.

A DEGREE SEQUENCE METHOD FOR THE CUTWIDTH PROBLEM OF GRAPHS

The cutwidth problem fora graph G is to embed G into a path such thatthe maximum number of overlap edges is minimized.This paperpresents an approach based on the degree se- quence of G for determining the exact value of cutwidth of typical graphs (e.g.,n- cube,cater- pillars) .Relations between the cutwidth and other graph- theoretic parameters are studied as wel

A Compromise Programming to Task Assignment Problem in Software Development Project

The scheduling process that aims to assign tasks to members is a difficult job in project management.It plays a prerequisite role in determining the project’s quality and sometimes winning the bidding process.This study aims to propose an approach based on multi-objective combinatorial optimization to do this automatically.The generated schedule directs the project to be completed with the shortest critical path,at the minimum cost,while maintaining its quality.There are several real-world business constraints related to human resources,the similarity of the tasks added to the optimization model,and the literature’s traditional rules.To support the decision-maker to evaluate different decision strategies,we use compromise programming to transform multiobjective optimization(MOP)into a single-objective problem.We designed a genetic algorithm scheme to solve the transformed problem.The proposed method allows the incorporation of the model as a navigator for search agents in the optimal solution search process by transferring the objective function to the agents’fitness function.The optimizer can effectively find compromise solutions even if the user may or may not assign a priority to particular objectives.These are achieved through a combination of nonpreference and preference approaches.The experimental results show that the proposed method worked well on the tested dataset.