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.

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.

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.

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.

Effects of combinatorial water atomization on microstructures and properties of Cu-Sn powder

A couple of additional cooling nozzles were assembled under traditionalatomization nozzles in order to improve the process and produce the powder with fine microstructureand low oxygen. The influence of the process parameters on the properties of the powder wasinvestigated. The results show that finer powders with lower oxygen content and more irregular shapecan be achieved by combinatorial atomizing process comparing with normal one under the sameatomizing pressure.

Combinatorial synthesis and high-throughput characterization of copper-oxide superconductors

Fast synthesis and screening of materials are vital to the advance of materials science and are an essential component of the Materials Genome Initiative. Here we use copper-oxide superconductors as an example to demonstrate the power of integrating combinatorial molecular beam epitaxy synthesis with high-throughput electric transport measurements. Leveraging this method, we have generated a phase diagram with more than 800 compositions in order to unravel the doping dependence of interface superconductivity. In another application of the same method, we have studied the superconductorto-insulator quantum phase transition with unprecedented accuracy in tuning the chemical doping level.

Combinatorial Optimization of Ba/Fe-cordierite Solid Solution （Ba0.05Fe0.1Mg）2Al4Si5O18 for High Infrared Radiance Materials

A combinatorial chemistry method was employed to screen the Ba2＋ and Fe3＋ incorporated into cordierite structure （Ba0.05Fe0.1Mg）2A14Si5018 for exploring of high infrared radiance materials. A series of square-type sample array that consists of 7×7 compositions was syn- thesized by ink-jetting nitrate solutions into micro-reactor wells in a ceramic plate and then heat-treated at high temperatures. X-ray diffraction and infrared thermograph were used to analyze the effects of Ba2＋/Fe3＋ incorporating on the lattice distortion of cordierite and resultant changes in infrared radiance properties. Based on the results of X-ray phase analy- sis and radiance measurement of the scale-up prepared samples, the optimal Ba2＋ and Fe3＋ co-adding amount was determined to be 5%Ba2＋ plus 10%Fe3＋. Moreover, the infrared emissivity of the optimal composition at 100 ℃ was found to be higher than 0.8 in a wide wavelength range of 5-24μm. The research work demonstrates a promising application of Ba2＋/Fe3＋ cordierite solid solution as a kind of infrared heating materials for energy saving.

Genetic Algorithm Based Combinatorial Auction Method for Multi-Robot Task Allocation

An improved genetic algorithm is proposed to solve the problem of bad real-time performance or inability to get a global optimal/better solution when applying single-item auction （SIA） method or combinatorial auction method to multi-robot task allocation. The genetic algorithm based combinatorial auction （GACA） method which combines the basic-genetic algorithm with a new concept of ringed chromosome is used to solve the winner determination problem （WDP） of combinatorial auction. The simulation experiments are conducted in OpenSim, a multi-robot simulator. The results show that GACA can get a satisfying solution in a reasonable shot time, and compared with SIA or parthenogenesis algorithm combinatorial auction （PGACA） method, it is the simplest and has higher search efficiency, also, GACA can get a global better/optimal solution and satisfy the high real-time requirement of multi-robot task allocation.

Combinatorial Synthesis and High-Throughput Characterization of Microstructure and Phase Transformation in Ni-Ti-Cu-V Quaternary Thin-Film Library

Ni-Ti-based shape memory alloys(SMAs)have found widespread use in the last 70 years,but improving their functional stability remains a key quest for more robust and advanced applications.Named for their ability to retain their processed shape as a result of a reversible martensitic transformation,SMAs are highly sensitive to compositional variations.Alloying with ternary and quaternary elements to finetune the lattice parameters and the thermal hysteresis of an SMA,therefore,becomes a challenge in materials exploration.Combinatorial materials science allows streamlining of the synthesis process and data management from multiple characterization techniques.In this study,a composition spread of Ni-Ti-Cu-V thin-film library was synthesized by magnetron co-sputtering on a thermally oxidized Si wafer.Composition-dependent phase transformation temperature and microstructure were investigated and determined using high-throughput wavelength dispersive spectroscopy,synchrotron X-ray diffraction,and temperature-dependent resistance measurements.Of the 177 compositions in the materials library,32 were observed to have shape memory effect,of which five had zero or near-zero thermal hysteresis.These compositions provide flexibility in the operating temperature regimes that they can be used in.A phase map for the quaternary system and correlations of functional properties are discussed w让h respect to the local microstructure and composition of the thin-film library.

Negotiation Based Combinatorial Double Auction Mechanism in Cloud Computing

Cloud computing is a demanding business platform for services related to the field of IT.The goal of cloud customers is to access resources at a sustainable price,while the goal of cloud suppliers is to maximize their services utilization.Previously,the customers would bid for every single resource type,which was a limitation of cloud resources allocation.To solve these issues,researchers have focused on a combinatorial auction in which the resources are offered by the providers in bundles so that the user bids for their required bundle.Still,in this allocation mechanism,some drawbacks need to be tackled,such as due to the lower average bid price the users are dropped from the auction process.To solve this problem,we proposed a“Negotiation based Combinatorial Double Auction Mechanism for Resource Allocation(N-CDARA)in cloud computing”.The proposed method negotiates with dropped users.Lower average bid price users are asked by our proposed mechanism to increase their bids,as by the quoted bids they will be dropped by the auctioneer.Most of the users that are close to winning accept the proposal and increase their bid prices.The proposed mechanism is implemented in a CloudSim simulation toolkit.Results are compared with the latest model and performance study shows that in our proposed scheme more users win and get their requested services and the utilization of offered services is increased up to 18.4%than the existing schemes.

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.