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.

The upwind finite difference fractional steps method for combinatorial system of dynamics of fluids in porous media and its application

For combinatorial system of multilayer dynamics of fluids in porous media, the second order and first order upwind finite difference fractional steps schemes applicable to parallel arithmetic are put forward and two-dimensional and three-dimensional schemes are used to form a complete set. Some techniques, such as implicit-explicit difference scheme, calculus of variations, multiplicative commutation rule of difference operators, decomposition of high order difference operators and prior estimates, are adopted. Optimal order estimates in L 2 norm are derived to determine the error in the second order approximate solution. This method has already been applied to the numerical simulation of migration-accumulation of oil resources. Keywords: combinatorial system, multilayer dynamics of fluids in porous media, two-class upwind finite difference fractional steps method, convergence, numerical simulation of energy sources.

New Public Key Cryptosystems from Combinatorial Group Theory

External direct product of some low layer groups such as braid groups and general Artin groups, with a kind of special group action on it, provides a secure cryptographic computation platform, which can keep secure in the quantum computing epoch. Three hard problems on this new platform, Subgroup Root Problem, Multi-variant Subgroup Root Problem and Subgroup Action Problem are presented and well analyzed, which all have no relations with conjugacy. New secure public key encryption system and key agreement protocol are designed based on these hard problems. The new cryptosystems can be implemented in a general group environment other than in braid or Artin groups.

Linguo-Combinatorial Simulation of Complex Systems

Contemporary world is developing system and we must have the new models. Any complex system interacts with its changing environment and its viability depends on its adaptability. The number of arbitrary coefficients in the structure of equivalent equations of complex system changes in the process of learning. In systems with more than six variables, the number of arbitrary coefficients increases first, and then, passing through the maximum, begins to decrease. This phenomenon makes it possible to explain the processes of system growth, complication and death in biological, economical and physical-engineering systems. The author uses the Linguo-combinatorial method of investigation of complex systems, in taking key words for building equivalent equations. This phenomenon is able to increase the adaptability of different systems.

CRAB—CombinatoRial Auction Body Software System

Auctions are important market mechanisms for the allocation of goods and services. Combinatorial auctions are those auctions in which buyers can place bids on combinations of items. Combinatorial auctions have many applications. The paper presents the CRAB software system. CRAB is a non-commercial software system for generating, solving, and testing of combinatorial auction problems. The system solves problems by Balas’ method or by the primal-dual algo-rithm. CRAB is implemented in Ruby and it is distributed as the file crab.rb. The system is freely available on web pag-es for all interested

Combinatorial Enzyme Approach to Convert Wheat Insoluble Arabinoxylan to Bioactive Oligosaccharides

Combinatorial enzyme technology was applied for the conversion of wheat insoluble arabinoxylan to oligosaccharide structural variants. The digestive products were fractionated by Bio-Gel P4 column and screened for bioactivity. One fraction pool was observed to exhibit antimicrobial property resulting in the suppression of cell growth of the test organism ATCC 8739 E. coli. It has a MIC value of 1.5% (w/v, 35°C, 20 hr) and could be useful as a new source of prebiotics or preservatives. The present results further confirm the science and useful application of combinatorial enzyme approach.

Drug-Treatment Generation Combinatorial Algorithm Based on Machine Learning and Statistical Methodologies

Finding out the desired drug combinations is a challenging task because of the number of different combinations that exist and the adversarial effects that may arise. In this work, we generate drug combinations over multiple stages using distance calculation metrics from supervised learning, clustering, and a statistical similarity calculation metric for deriving the optimal treatment sequences. The combination generation happens for each patient based on the characteristics (features) observed during each stage of treatment. Our approach considers not the drug-to-drug (one-to-one) effect, but rather the effect of group of drugs with another group of drugs. We evaluate the combinations using an FNN model and identify future improvement directions.

Identification of Lubricating Oil Additives Using XGBoost and Ant Colony Optimization Algorithms

To address the problem of identifying multiple types of additives in lubricating oil,a method based on midinfrared spectral band selection using the eXtreme Gradient Boosting(XGBoost)algorithm combined with the ant colony optimization(ACO)algorithm is proposed.The XGBoost algorithm was used to train and test three additives,T534(alkyl diphenylamine),T308(isooctyl acid thiophospholipid octadecylamine),and T306(trimethylphenol phosphate),separately,in order to screen for the optimal combination of spectral bands for each additive.The ACO algorithm was used to optimize the parameters of the XGBoost algorithm to improve the identification accuracy.During this process,the support vector machine(SVM)and hybrid bat algorithms(HBA)were included as a comparison,generating four models:ACO-XGBoost,ACO-SVM,HBA-XGboost,and HBA-SVM.The results showed that all four models could identify the three additives efficiently,with the ACO-XGBoost model achieving 100%recognition of all three additives.In addition,the generalizability of the ACO-XGBoost model was further demonstrated by predicting a lubricating oil containing the three additives prepared in our laboratory and a collected sample of commercial oil currently in use。

Single Tooth Segmentation on Panoramic X-Rays Using End-to-End Deep Neural Networks

In dentistry, panoramic X-ray images are extensively used by dentists for tooth structure analysis and disease diagnosis. However, the manual analysis of these images is time-consuming and prone to misdiagnosis or overlooked. While deep learning techniques have been employed to segment teeth in panoramic X-ray images, accurate segmentation of individual teeth remains an underexplored area. In this study, we propose an end-to-end deep learning method that effectively addresses this challenge by employing an improved combinatorial loss function to separate the boundaries of adjacent teeth, enabling precise segmentation of individual teeth in panoramic X-ray images. We validate the feasibility of our approach using a challenging dataset. By training our segmentation network on 115 panoramic X-ray images, we achieve an intersection over union (IoU) of 86.56% for tooth segmentation and an accuracy of 65.52% in tooth counting on 87 test set images. Experimental results demonstrate the significant improvement of our proposed method in single tooth segmentation compared to existing methods.

A Note on Diophantine Equation Ax^4+ 1 = By^2 and Erds' Conjecture on Combinatorial Number

A necessary and suffcient condition is given for the equation Ax4+ 1 =By2 to have positive integer solution, and an effective method is derived for solving equation a2x4 + 1 = By2 in positive integers x, y for given ho and B completely. Also, using a recently result of Ribet, Darmon and Merel, we proved that Erdos’ conjecture on combinatorial number is right.

Simultaneous detection and differentiates of Brucella abortus and Brucella melitensis by combinatorial PCR

Objective:To evaluate simultaneous detection and differentiates of Brucella abortus(B.abortus) and Brucella melitensis(B.melitensis) through the combinatorial POR method.Methods:This study was designed using three primers that could simultaneously identify and differentiate two major species of pathogenic Brucella in humans and animals.Identification and differentiation of each species using the size of the PCR product were determined.To determine the specifieity of the method,bacteria close to the genus Brucella were used.Finally,to confirm PCR products.In addition to the products sequence,RFLP was performed on PCR products using restriction enzymes.Results:The method of optimized combinatorial PCR in this study could simultaneously detect and differentiate B.abortus and B.melitensis with high specificity and sensitivity in clinical samples.Differentiation of species is based on the resulting bands: therefore,the band 494 bp for B.abortus and 733 bp for B.melitensis were obtained.RFLP and sequencing results confirmed PCR results.Conclusions:The results of this study shows that without routine diagnostic methods such as culture and serology tests,using the molecular method of combinatorial PCR,important species of Brucella can be simultaneously identified and differentiated in clinical samples.

Hopfield neural network based on ant system

Hopfield neural network is a single layer feedforward neural network. Hopfield network requires some control parameters to be carefully selected, else the network is apt to converge to local minimum. An ant system is a nature inspired meta heuristic algorithm. It has been applied to several combinatorial optimization problems such as Traveling Salesman Problem, Scheduling Problems, etc. This paper will show an ant system may be used in tuning the network control parameters by a group of cooperated ants. The major advantage of this network is to adjust the network parameters automatically, avoiding a blind search for the set of control parameters. This network was tested on two TSP problems, 5 cities and 10 cities. The results have shown an obvious improvement.

Individualized Pixel Synthesis and Characterization of Combinatorial Materials Chips

Conventionally, an experimentally determined phase diagram requires studies of phase formation at a range of temperatures for each composition, which takes years of effort from multiple research groups. Combinatorial materials chip technology, featuring high-throughput synthesis and characterization, is able to determine the phase diagram of an entire composition spread of a binary or ternary system at a single temperature on one materials library, which, though significantly increasing efficiency, still requires many libraries processed at a series of temperatures in order to complete a phase diagram. In this paper, we propose a "one-chip method" to construct a complete phase diagram by individually synthesizing each pixel step by step with a progressive pulse of energy to heat at different temperatures while monitoring the phase evolution on the pixel in situ in real time. Repeating this process pixel by pixel throughout the whole chip allows the entire binary or ternary phase diagram to be mapped on one chip in a single experiment. The feasibility of this methodology is demonstrated in a study of a Ge-Sb-Te ternary alloy system, on which the amorphouscrystalline phase boundary is determined.

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.

A COMBINATORIAL APPROACH TO THE OXIDATION RESISTANCE OF (Ti,Al)N AND Ti-Al-Si-N HARD COATINGS

The increasing complexity of modern functional materials leads to the demandof a cost efficient tool for the development of new products. One possible approach to this questionis the adaptation of combinatorial methods to the specific requirements of materials industry.These methods, originally developed for the pharmaceutical industry, have recently been applied tothe screening of superconductive, magnetoresistant and photoluminescent materials. The principle ofthese combinatorial approaches is the deposition of large materials libraries in one processcombined with fast methods for the determination of the resulting properties. In this paper, thedeposition and characterization of laterally graded materials libraries (composition spread) ispresented. The films have been deposited by reactive magnetron sputtering, using two or threemetallic targets at a low angle to the substrate surface as well as a system of apertures. Toillustrate the advantages of combinatorial approaches for the development of advanced materials, themulticomponent metastable hardcoatings (Ti,Al)N and Ti-Al-Si-N are discussed with special emphasison the relations between structure and composition on the one hand and the oxidation resistance ofthese coatings on the other. The results illustrate that the composition spread approach is apowerful and cost efficient tool for the development and optimization of new multicomponentfunctional materials.

Combinatorial design-based quasi-cyclic LDPC codes with girth eight

This paper presents a novel regular Quasi-Cyclic (QC)Low Density Parity Check (LDPC)codes with columnweight three and girth at least eight.These are designed on the basis of combinatorial design in which subsets applied for the construction of circulant matrices are determined by a particular subset.Considering the nonexistence of cycles four and six in the structure of the parity check matrix,a bound for their minimum weight is proposed.The simtdations conducted confirm that without applying a masking technique,the newly implemented codes have a performance similar to or better than other well-known codes.This is evident in the waterfall region, while their error floor at very low Bit Error Rate (BER)is expected.

Fenton metal nanomedicines for imaging-guided combinatorial chemodynamic therapy against cancer

Chemodynamic therapy(CDT)is considered as a promising modality for selective cancer therapy,which is realized via Fenton reaction-mediated decomposition of endogenous H_(2)O_(2) to produce toxic hydroxyl radical(•OH)for tumor ablation.While extensive efforts have been made to develop CDT-based therapeutics,their in vivo efficacy is usually unsatisfactory due to poor catalytic activity limited by tumor microenvironment,such as anti-oxidative systems,insufficient H_(2)O_(2),and mild acidity.To mitigate these issues,we have witnessed a surge in the development of CDT-based combinatorial nanomedicines with complementary or synergistic mechanisms for enhanced tumor therapy.By virtue of their bio-imaging capabilities,Fenton metal nanomedicines(FMNs)are equipped with intrinsic properties of imaging-guided tumor therapies.In this critical review,we summarize recent progress of this field,focusing on FMNs for imaging-guided combinatorial tumor therapy.First,various Fenton metals with inherent catalytic performances and imaging properties,including Fe,Cu and Mn,were introduced to illustrate their possible applications for tumor theranostics.Then,CDT-based combinatorial systems were reviewed by incorporating many other treatment means,including chemotherapy,photodynamic therapy(PDT),sonodynamic therapy(SDT),photothermal therapy(PTT),starvation therapy and immunotherapy.Next,various imaging approaches based on Fenton metals were presented in detail.Finally,challenges are discussed,and future prospects are speculated in the field to pave way for future developments.

The Combinatorial Biosynthesis of＂Unnatural＂ Products with Polyketides

Polyketides have been widely used clinically due to their significant biological activities, but the needed structural and functional diversity cannot be achieved by common chemical synthetic methods. The tool of combinatorial biosynthesis provides the possibility to produce "unnatural" natural drugs, which has achieved initial success. This paper provides an overview for the strategies of combinatorial biosynthesis in producing the structural and functional diversity of polyketides, including the redesign of metabolic flow, polyketide synthase(PKS) engineering, and PKS post-translational modification. Although encouraging progress has been made in the last decade, challenges still exist regarding the rational combinatorial biosynthesis of polyketides. In this review, the perspectives of polyketide combinatorial biosynthesis are also discussed.

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.