A Branch-and-Bound Algorithm for the Molecular Ordered Covering Problem.

The Discretizable Molecular Distance Geometry Problem (DMDGP) plays a key role in the construction of three-dimensional molecular structures from interatomic distances acquired through nuclear magnetic resonance (NMR) spectroscopy, with the primary objective of validating a sequence of distance constraints related to NMR data. This article addresses the escalating complexity of the DMDGP encountered with larger and more flexible molecules by introducing a novel strategy via the Molecular Ordered Covering Problem, which optimizes the ordering of distance constraints to improve computational efficiency in DMDGP resolution. This approach utilizes a specialized Branch-and-Bound (BB) algorithm, tested on both synthetic and actual protein structures from the protein data bank. Our analysis demonstrates the efficacy of the previously proposed greedy heuristic in managing complex molecular scenarios, highlighting the BB algorithm's utility as a validation mechanism. This research contributes to ongoing efforts in molecular structure analysis, with possible implications for areas such as protein folding, drug design, and molecular modeling.

Hybrid Classical-Quantum Branch-and-Bound Algorithm for Solving Integer Linear Problems.

Quantum annealers are suited to solve several logistic optimization problems expressed in the QUBO formulation. However, the solutions proposed by the quantum annealers are generally not optimal, as thermal noise and other disturbing effects arise when the number of qubits involved in the calculation is too large. In order to deal with this issue, we propose the use of the classical branch-and-bound algorithm, that divides the problem into sub-problems which are described by a lower number of qubits. We analyze the performance of this method on two problems, the knapsack problem and the traveling salesman problem. Our results show the advantages of this method, that balances the number of steps that the algorithm has to make with the amount of error in the solution found by the quantum hardware that the user is willing to risk. The results are obtained using the commercially available quantum hardware D-Wave Advantage, and they outline the strategy for a practical application of the quantum annealers.

A General Scheme of a Branch-and-Bound Approach for the Sensor Selection Problem in Near-Field Broadband Beamforming.

This paper is devoted to the sensor selection problem. A broadband receiver beamforming working in a near-field is considered. The system response should be as close as possible to the desired one, which is optimized in the sense of L2 norm. The problem considered is at least NP-hard. Therefore, the branch-and-bound algorithm is developed to solve the problem. The proposed approach is universal and can be applied not only to microphone arrays but also to antenna arrays; that is, the methodology for the generation of consecutive solutions can be applied to different types of sensor selection problems. Next, for a larger microphone array, an efficient metaheuristic algorithm is constructed. The algorithm implemented is a hybrid genetic algorithm based on the ITÖ process. Numerical experiments show that the proposed approach can be successfully applied to the sensor selection problem.

A bi-criterion sequence-dependent scheduling problem with order deliveries.

The manufacturing sector faces unprecedented challenges, including intense competition, a surge in product varieties, heightened customization demands, and shorter product life cycles. These challenges underscore the critical need to optimize manufacturing systems. Among the most enduring and complex challenges within this domain is production scheduling. In practical scenarios, setup time is whenever a machine transitions from processing one product to another. Job scheduling with setup times or associated costs has garnered significant attention in both manufacturing and service environments, prompting extensive research efforts. While previous studies on customer order scheduling primarily focused on orders or jobs to be processed across multiple machines, they often overlooked the crucial factor of setup time. This study addresses a sequence-dependent bi-criterion scheduling problem, incorporating order delivery considerations. The primary objective is to minimize the linear combination of the makespan and the sum of weighted completion times of each order. To tackle this intricate challenge, we propose pertinent dominance rules and a lower bound, which are integral components of a branch-and-bound methodology employed to obtain an exact solution. Additionally, we introduce a heuristic approach tailored to the problem's unique characteristics, along with three refined variants designed to yield high-quality approximate solutions. Subsequently, these three refined approaches serve as seeds to generate three distinct populations or chromosomes, each independently employed in a genetic algorithm to yield a robust approximate solution. Ultimately, we meticulously assess the efficacy of each proposed algorithm through comprehensive simulation trials.

MULTIMODAL MICROSCOPY IMAGE ALIGNMENT USING SPATIAL AND SHAPE INFORMATION AND A BRANCH-AND-BOUND ALGORITHM.

Multimodal microscopy experiments that image the same population of cells under different experimental conditions have become a widely used approach in systems and molecular neuroscience. The main obstacle is to align the different imaging modalities to obtain complementary information about the observed cell population (e.g., gene expression and calcium signal). Traditional image registration methods perform poorly when only a small subset of cells are present in both images, as is common in multimodal experiments. We cast multimodal microscopy alignment as a cell subset matching problem. To solve this non-convex problem, we introduce an efficient and globally optimal branch-and-bound algorithm to find subsets of point clouds that are in rotational alignment with each other. In addition, we use complementary information about cell shape and location to compute the matching likelihood of cell pairs in two imaging modalities to further prune the optimization search tree. Finally, we use the maximal set of cells in rigid rotational alignment to seed image deformation fields to obtain a final registration result. Our framework performs better than the state-of-the-art histology alignment approaches regarding matching quality and is faster than manual alignment, providing a viable solution to improve the throughput of multimodal microscopy experiments.

Airline capacity distribution under financial budget and resource consideration.

Capacity distribution is a challenging issue for an airline under financial budget and resource consideration. It is a large-scale optimization problem covering both long-term planning and short-term operating arrangements. This study investigates on the airline capacity distribution problem with financial budget and resource consideration. It contains subproblems of financial budget arrangement, fleet introduction, and fleet assignment. Among them, financial budget is arranged in multiple decision periods, fleet introduction is decided under fixed time points, while fleet assignment is decided under all available time points. To tackle this problem, an integer programming model is formulated for descriptions. Then, an integrated algorithm of modified Variable Neighborhood Search (VNS) and Branch-and-bound (B&B) strategy is developed to find solutions. In detail, a greedy heuristic approach is utilized to generate an initial solution for fleet introduction, the modified B&B strategy is utilized to generate the optimal solution for fleet assignment and the modified VNS is applied to update current solution for a new one with better quality. In addition, budget limit checks are added for financial budget arrangements. Finally, the hybrid algorithm is tested on efficiency and stability. It is also compared to other algorithms which replace the modified VNS by basic VNS, differential evolution and genetic algorithm. Computational results show that performance of our approach is powerful in terms of objective value, convergence speed and stability.

(p,q)-biclique counting and enumeration for large sparse bipartite graphs.

In this paper, we study the problem of (p, q)-biclique counting and enumeration for large sparse bipartite graphs. Given a bipartite graph G=(U,V,E) and two integer parameters p and q, we aim to efficiently count and enumerate all (p, q)-bicliques in G, where a (p, q)-biclique B(L, R) is a complete subgraph of G with L⊆U, R⊆V, |L|=p, and |R|=q. The problem of (p, q)-biclique counting and enumeration has many applications, such as graph neural network information aggregation, densest subgraph detection, and cohesive subgroup analysis. Despite the wide range of applications, to the best of our knowledge, we note that there is no efficient and scalable solution to this problem in the literature . This problem is computationally challenging, due to the worst-case exponential number of (p, q)-bicliques. In this paper, we propose a competitive branch-and-bound baseline method, namely BCList, which explores the search space in a depth-first manner, together with a variety of pruning techniques. Although BCList offers a useful computation framework to our problem, its worst-case time complexity is exponential to p+q. To alleviate this, we propose an advanced approach, called BCList++. Particularly, BCList++ applies a layer-based exploring strategy to enumerate (p, q)-bicliques by anchoring the search on either U or V only, which has a worst-case time complexity exponential to either p or q only. Consequently, a vital task is to choose a layer with the least computation cost. To this end, we develop a cost model, which is built upon an unbiased estimator for the density of 2-hop graph induced by U or V. To improve computation efficiency, BCList++ exploits pre-allocated arrays and vertex labeling techniques such that the frequent subgraph creating operations can be substituted by array element switching operations. We conduct extensive experiments on 16 real-life datasets, and the experimental results demonstrate that BCList++ significantly outperforms the baseline methods by up to 3 orders of magnitude. We show via a case study that (p, q)-bicliques optimizes the efficiency of graph neural networks. In this paper, we extend our techniques to count and enumerate (p, q)-bicliques on uncertain bipartite graphs. An efficient method IUBCList is developed on the top of BCList++, together with a couple of pruning techniques, including common neighbor refinement and search branch early termination, to discard unpromising uncertain (p, q)-bicliques early. The experimental results demonstrate that IUBCList significantly outperforms the baseline method by up to 2 orders of magnitude.

Context-Aware Technology Mapping in Genetic Design Automation.

Genetic design automation (GDA) tools hold promise to speed-up circuit design in synthetic biology. Their widespread adoption is hampered by their limited predictive power, resulting in frequent deviations between the in silico and in vivo performance of a genetic circuit. Context effects, i.e., the change in overall circuit functioning, due to the intracellular environment of the host and due to cross-talk among circuits components are believed to be a major source for the aforementioned deviations. Incorporating these effects in computational models of GDA tools is challenging but is expected to boost their predictive power and hence their deployment. Using fine-grained thermodynamic models of promoter activity, we show in this work how to account for two major components of cellular context effects: (i) crosstalk due to limited specificity of used regulators and (ii) titration of circuit regulators to off-target binding sites on the host genome. We show how we can compensate the incurred increase in computational complexity through dedicated branch-and-bound techniques during the technology mapping process. Using the synthesis of several combinational logic circuits based on Cello's device library as a case study, we analyze the effect of different intensities and distributions of crosstalk on circuit performance and on the usability of a given device library.

An Approach for Autonomous Feeding Robot Path Planning in Poultry Smart Farm.

In order to solve the problems of poor feeding environment, untimely feeding and high labor demand in poultry smart farms, the development of feeding robots is imminent, while the research on path planning algorithms is an important part of developing feeding robots. The energy consumption of the feeding robot is one of the important elements of concern in the process of path planning. In this study, the shortest path does not mean that the feeding robot consumes the least energy, because the total mass of the feeding robot keeps changing during the feeding process. It is necessary to find the most suitable path so that the feeding robot consumes the lowest amount of energy during the feeding process. A branch and bound algorithm to calculate the minimum energy consumption travel path for small-scale buckets lacking feed is proposed. The lower bound of the branch and bound on the energy consumption is obtained by the approach of preferred selection of the set of shortest edges combined with the sequence inequality, and the upper bound could be obtained based on Christofides's Heuristic algorithm. A double-crossover operator genetic algorithm based on an upper bound on energy consumption for large-scale buckets lacking feed is proposed, and different crossover operations are performed according to the relationship between the fitness value and the upper bound of energy consumption in order to find a better path. The experiment results show that the approach proposed in this study is efficient; for small-scale buckets lacking feed, a branch and bound algorithm could calculate the minimum energy consumption path of 17 points in 300 s, and for large-scale buckets lacking feed, a double-crossover operator genetic algorithm based on an upper bound on energy consumption could calculate the minimum energy consumption travel path within 30 points in 60 s. The result is more accurate compared to the genetic algorithm with a single crossover operator.

A fast and efficient path elimination algorithm for large-scale multiple common longest sequence problems.

BACKGROUND: In various fields, searching for the Longest Common Subsequences (LCS) of Multiple (i.e., three or more) sequences (MLCS) is a classic but difficult problem to solve. The primary bottleneck in this problem is that present state-of-the-art algorithms require the construction of a huge graph (called a direct acyclic graph, or DAG), which the computer usually has not enough space to handle. Because of their massive time and space consumption, present algorithms are inapplicable to issues with lengthy and large-scale sequences. RESULTS: A mini Directed Acyclic Graph (mini-DAG) model and a novel Path Elimination Algorithm are proposed to address large-scale MLCS issues efficiently. In mini-DAG, we employ the branch and bound approach to reduce paths during DAG construction, resulting in a very mini DAG (mini-DAG), which saves memory space and search time. CONCLUSION: Empirical experiments have been performed on a standard benchmark set of DNA sequences. The experimental results show that our model outperforms the leading algorithms, especially for large-scale MLCS problems.

Bipartite graph search optimization for type II diabetes mellitus Jamu formulation using branch and bound algorithm.

Jamu is an Indonesian traditional herbal medicine that has been practiced for generations. Jamu is made from various medicinal plants. Each plant has several compounds directly related to the target protein that are directly associated with a disease. A pharmacological graph can form relationships between plants, compounds, and target proteins. Research related to the prediction of Jamu formulas for some diseases has been carried out, but there are problems in finding combinations or compositions of Jamu formulas because of the increase in search space size. Some studies adopted the drug-target interaction (DTI) implemented using machine learning or deep learning to predict the DTI for discovering the Jamu formula. However, this approach raises important issues, such as imbalanced and high-dimensional dataset, overfitting, and the need for more procedures to trace compounds to their plants. This study proposes an alternative approach by implementing bipartite graph search optimization using the branch and bound algorithm to discover the combination or composition of Jamu formulas by optimizing the search on a plant-protein bipartite graph. The branch and bound technique is implemented using the search strategy of breadth first search (BrFS), Depth First Search, and Best First Search. To show the performance of the proposed method, we compared our method with a complete search algorithm, searching all nodes in the tree without pruning. In this study, we specialize in applying the proposed method to search for the Jamu formula for type II diabetes mellitus (T2DM). The result shows that the bipartite graph search with the branch and bound algorithm reduces computation time up to 40 times faster than the complete search strategy to search for a composition of plants. The binary branching strategy is the best choice, whereas the BrFS strategy is the best option in this research. In addition, the the proposed method can suggest the composition of one to four plants for the T2DM Jamu formula. For a combination of four plants, we obtain Angelica Sinensis, Citrus aurantium, Glycyrrhiza uralensis, and Mangifera indica. This approach is expected to be an alternative way to discover the Jamu formula more accurately.

The Trade-Offs between Optimality and Feasibility in Online Routing with Dedicated Path Protection in Elastic Optical Networks.

The article discusses an online problem of routing and spectrum allocation with dedicated path protection in elastic optical networks. We propose three novel algorithms to solve this problem. The first of them is the minimum-cost-maximum-flow heuristic algorithm, which calculates the solution assuming that the spectrum units on the working and dedicated backup path are the same. Such an assumption, on the one hand, increases the bandwidth blocking probability; however, on the other hand, it enables a simple, cheap and fast way to connect customers to the network during the implementation phase of elastic optical networks. The next two algorithms, which determine the exact solutions, are based on the branch and bound method. The first calculates the working and dedicated backup paths with the minimum total occupied bandwidth, called the total cost, while the second calculates the paths with the minimum total length. These algorithms enable the performance evaluation of the proposed heuristic algorithm and provide the answer as to what should be optimized, the total cost or the total length of paths, in order to minimize the bandwidth blocking probability. Extensive simulation research has shown that the proposed heuristic algorithm can be used in elastic optical networks, but with a small network load. Moreover, it is shown that the optimization of the total cost of paths provides a slightly lower blocking probability than the optimization of the total length of paths.

A branch-and-Benders-cut algorithm for a bi-objective stochastic facility location problem.

In many real-world optimization problems, more than one objective plays a role and input parameters are subject to uncertainty. In this paper, motivated by applications in disaster relief and public facility location, we model and solve a bi-objective stochastic facility location problem. The considered objectives are cost and covered demand, where the demand at the different population centers is uncertain but its probability distribution is known. The latter information is used to produce a set of scenarios. In order to solve the underlying optimization problem, we apply a Benders' type decomposition approach which is known as the L-shaped method for stochastic programming and we embed it into a recently developed branch-and-bound framework for bi-objective integer optimization. We analyze and compare different cut generation schemes and we show how they affect lower bound set computations, so as to identify the best performing approach. Finally, we compare the branch-and-Benders-cut approach to a straight-forward branch-and-bound implementation based on the deterministic equivalent formulation.

The Allocation Method for Personal Protective Equipment in the Emerging Infectious Disease Environment.

The COVID-19 pandemic gives humankind a lesson that the outbreak of an emerging infectious disease (EID) is sudden and uncertain. Accurately mastering its dynamics and putting forward an efficient and fair humanitarian logistics plan for personal protective equipment (PPE) remains difficult. This study examines the decision making for humanitarian logistics to answer the question that how to coordinate fairness and efficiency when facing supply-demand imbalance during humanitarian logistics planning in an EID environment. The main contributions include two aspects: (1) The victims' losses in terms of fairness and efficiency in receiving PPE are jointly explored by evaluating their bearing capacity evolution, and then a novel loss function is built to search for a reasonable compromise between fairness and efficiency. (2) A multi-objective optimization model is built, which is solved using the combined use of goal programming approach and improved branch and bound method. Finally, the practicability of the proposed model is tested by an EID case study. The potential advantages of the proposed model and improved approach are discussed.

Algorithms for protein design.

Computational Protein Design has the potential to contribute to major advances in enzyme technology, vaccine design, receptor-ligand engineering, biomaterials, nanosensors, and synthetic biology. Although Protein Design is a challenging problem, proteins can be designed by experts in Protein Design, as well as by non-experts whose primary interests are in the applications of Protein Design. The increased accessibility of Protein Design technology is attributable to the accumulated knowledge and experience with Protein Design as well as to the availability of software and online resources. The objective of this review is to serve as a guide to the relevant literature with a focus on the novel methods and algorithms that have been developed or applied for Protein Design, and to assist in the selection of algorithms for Protein Design. Novel algorithms and models that have been introduced to utilize the enormous amount of experimental data and novel computational hardware have the potential for producing substantial increases in the accuracy, reliability and range of applications of designed proteins.

A branch and bound algorithm for optimal television commercial scheduling.

In the current era of multimedia, television (TV) plays an important role in transmitting advertising messages. In addition, advertising is the primary source of revenue for the TV industry. Thus, a critical issue for TV stations is the scheduling of commercials in suitable advertising breaks on different TV channels to maximize revenue and minimize penalties. This type of TV commercial scheduling problem is similar to the machine scheduling problem, and both have availability constraints. However, the literature on TV commercial scheduling has not considered this perspective. Motivated by this, we consider the problem of scheduling commercials with specific service-level requirements on TV channels while minimizing the maximum lateness. The lateness of a commercial is defined to be its completion time minus its due date, and the maximum lateness is the maximum value of lateness among all commercials. We propose an exact branch and bound algorithm based on the LFJ (least flexible job first)/EDD (earliest due date first) rules and network flow methods, which were developed to solve the machine scheduling problem with availability constraints. Computational analysis shows that the bounding scheme proposed is highly effective, and a very low percentage of nodes is generated by the branch and bound algorithm. The algorithm can obtain an optimal solution for the problem.

An SDP-based approach for computing the stability number of a graph.

Finding the stability number of a graph, i.e., the maximum number of vertices of which no two are adjacent, is a well known NP-hard combinatorial optimization problem. Since this problem has several applications in real life, there is need to find efficient algorithms to solve this problem. Recently, Gaar and Rendl enhanced semidefinite programming approaches to tighten the upper bound given by the Lovász theta function. This is done by carefully selecting some so-called exact subgraph constraints (ESC) and adding them to the semidefinite program of computing the Lovász theta function. First, we provide two new relaxations that allow to compute the bounds faster without substantial loss of the quality of the bounds. One of these two relaxations is based on including violated facets of the polytope representing the ESCs, the other one adds separating hyperplanes for that polytope. Furthermore, we implement a branch and bound (B&B) algorithm using these tightened relaxations in our bounding routine. We compare the efficiency of our B&B algorithm using the different upper bounds. It turns out that already the bounds of Gaar and Rendl drastically reduce the number of nodes to be explored in the B&B tree as compared to the Lovász theta bound. However, this comes with a high computational cost. Our new relaxations improve the run time of the overall B&B algorithm, while keeping the number of nodes in the B&B tree small.

Globally-Optimal Inlier Maximization for Relative Pose Estimation Under Planar Motion.

Planar motion constraint occurs in visual odometry (VO) and SLAM for Automated Guided Vehicles (AGVs) or mobile robots in general. Conventionally, two-point solvers can be nested to RANdom SAmple Consensus to reject outliers in real data, but the performance descends when the ratio of outliers goes high. This study proposes a globally-optimal Branch-and-Bound (BnB) solver for relative pose estimation under general planar motion, which aims to figure out the globally-optimal solution even under a quite noisy environment. Through reasonable modification of the motion equation, we decouple the relative pose into relative rotation and translation so that a simplified bounding strategy can be applied. It enhances the efficiency of the BnB technique. Experimental results support the global optimality and demonstrate that the proposed method performs more robustly than existing approaches. In addition, the proposed algorithm outperforms state-of-art methods in global optimality under the varying level of outliers.

Improving the efficiency of single-cell genome sequencing based on overlapping pooling strategy and CNV analysis.

Single-cell genome sequencing has become a useful tool in medicine and biology studies. However, an independent library is required for each cell in single-cell genome sequencing, so that the cost grows with the number of cells. In this study, we report a study which efficiently analyses single-cell copy number variation (CNV) using overlapping pooling strategy and branch and bound (B&B) algorithm. Single cells were overlapped pooled before sequencing, and later were assorted into specific types by estimating their CNV patterns by B&B algorithm. Instead of constructing libraries for each cell, a library is required only for each pool. As the number of pools is smaller than the cells, fewer libraries are required, which means lower cost. Through computer simulations, we overlapped pooled 80 cells into 40 or 27 pools and classified them into cell types based on CNV pattern. The results showed that 84% cells in 40 pools and 76.5% cells in 27 pools were correctly classified on average, while only half or one-third of the sequencing libraries were required. Combining with traditional approaches, our method is expected to significantly improve the efficiency of single-cell genome sequencing.

Fast and optimal branch-and-bound planner for the grid-based coverage path planning problem based on an admissible heuristic function.

This paper introduces an optimal algorithm for solving the discrete grid-based coverage path planning (CPP) problem. This problem consists in finding a path that covers a given region completely. First, we propose a CPP-solving baseline algorithm based on the iterative deepening depth-first search (ID-DFS) approach. Then, we introduce two branch-and-bound strategies (Loop detection and an Admissible heuristic function) to improve the results of our baseline algorithm. We evaluate the performance of our planner using six types of benchmark grids considered in this study: Coast-like, Random links, Random walk, Simple-shapes, Labyrinth and Wide-Labyrinth grids. We are first to consider these types of grids in the context of CPP. All of them find their practical applications in real-world CPP problems from a variety of fields. The obtained results suggest that the proposed branch-and-bound algorithm solves the problem optimally (i.e., the exact solution is found in each case) orders of magnitude faster than an exhaustive search CPP planner. To the best of our knowledge, no general CPP-solving exact algorithms, apart from an exhaustive search planner, have been proposed in the literature.