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.

Coevolutionary Framework for Generalized Multimodal Multi-Objective Optimization

Most multimodal multi-objective evolutionary algorithms(MMEAs)aim to find all global Pareto optimal sets(PSs)for a multimodal multi-objective optimization problem(MMOP).However,in real-world problems,decision makers(DMs)may be also interested in local PSs.Also,searching for both global and local PSs is more general in view of dealing with MMOPs,which can be seen as generalized MMOPs.Moreover,most state-of-theart MMEAs exhibit poor convergence on high-dimension MMOPs and are unable to deal with constrained MMOPs.To address the above issues,we present a novel multimodal multiobjective coevolutionary algorithm(Co MMEA)to better produce both global and local PSs,and simultaneously,to improve the convergence performance in dealing with high-dimension MMOPs.Specifically,the Co MMEA introduces two archives to the search process,and coevolves them simultaneously through effective knowledge transfer.The convergence archive assists the Co MMEA to quickly approach the Pareto optimal front.The knowledge of the converged solutions is then transferred to the diversity archive which utilizes the local convergence indicator and the-dominance-based method to obtain global and local PSs effectively.Experimental results show that Co MMEA is competitive compared to seven state-of-the-art MMEAs on fifty-four complex MMOPs.

Multicommodity Flow Modeling for the Data Transmission Scheduling Problem in Navigation Satellite Systems

Introducing InterSatellite Links(ISLs)is a major trend in new-generation Global Navigation Satellite Systems(GNSSs).Data transmission scheduling is a crucial problem in the study of ISL management.The existing research on intersatellite data transmission has not considered the capacities of ISL bandwidth.Thus,the current study is the first to describe the intersatellite data transmission scheduling problem with capacity restrictions in GNSSs.A model conversion strategy is designed to model the aforementioned problem as a length-bounded single-path multicommodity flow problem.An integer programming model is constructed to minimize the maximal sum of flows on each intersatellite edge;this minimization is equivalent to minimizing the maximal occupied ISL bandwidth.An iterated tree search algorithm is proposed to resolve the problem,and two ranking rules are designed to guide the search.Experiments based on the BeiDou satellite constellation are designed,and results demonstrate the effectiveness of the proposed model and algorithm.

Leveraging Human-AI Collaboration in Crowd-Powered Source Search:A Preliminary Study

Source search is an important problem in our society,relating to finding fire sources,gas sources,or signal sources.Particularly,in an unexplored and potentially dangerous environment,an autonomous source search algorithm that employs robotic searchers is usually applied to address the problem.Such environments could be completely unknown and highly complex.Therefore,novel search algorithms have been designed,combining heuristic methods and intelligent optimization,to tackle search problems in large and complex search spaces.However,these intelligent search algorithms were not designed to address completeness and optimality,and therefore commonly suffer from the problems such as local optimums or endless loops.Recent studies have used crowd-powered systems to address the complex problems that cannot be solved by machines on their own.While leveraging human intelligence in an AI system has been shown to be effective in making the system more reliable,whether using the power of the crowd can improve autonomous source search algorithms remains unanswered.To this end,we propose a crowd-powered source search approach enabling human-AI collaboration,which uses human intelligence as external supports to improve existing search algorithms and meanwhile reduces human efforts using AI predictions.Furthermore,we designed a crowd-powered prototype system and carried out an experiment with both experts and non-experts,to complete 200 source search scenarios(704 crowdsourcing tasks).Quantitative and qualitative analysis showed that the sourcing search algorithm enhanced by crowd could achieve both high effectiveness and efficiency.Our work provides valuable insights in human-AI collaborative system design.