The seriation of proximity matrices is an important problem in combinatorial data analysis and can be conducted using a variety of objective criteria. Some of the most popular criteria for evaluating an ordering of objects are based on (anti-) Robinson forms, which reflect the pattern of elements within each row and/or column of the reordered matrix when moving away from the main diagonal. This paper presents a branch-and-bound algorithm that can be used to seriate a symmetric dissimilarity matrix by identifying a reordering of rows and columns of the matrix optimizing an anti-Robinson criterion. Computational results are provided for several proximity matrices from the literature using four different anti-Robinson criteria. The results suggest that with respect to computational efficiency, the branch-and-bound algorithm is generally competitive with dynamic programming. Further, because it requires much less storage than dynamic programming, the branch-and-bound algorithm can provide guaranteed optimal solutions for matrices that are too large for dynamic programming implementations.

Although the K-means algorithm for minimizing the within-cluster sums of squared deviations from cluster centroids is perhaps the most common method for applied cluster analyses, a variety of other criteria are available. The p-median model is an especially well-studied clustering problem that requires the selection of p objects to serve as cluster centers. The objective is to choose the cluster centers such that the sum of the Euclidean distances (or some other dissimilarity measure) of objects assigned to each center is minimized. Using 12 data sets from the literature, we demonstrate that a three-stage procedure consisting of a greedy heuristic, Lagrangian relaxation, and a branch-and-bound algorithm can produce globally optimal solutions for p-median problems of nontrivial size (several hundred objects, five or more variables, and up to 10 clusters). We also report the results of an application of the p-median model to an empirical data set from the telecommunications industry.

Minimization of the within-cluster sums of squares (WCSS) is one of the most important optimization criteria in cluster analysis. Although cluster analysis modules in commercial software packages typically use heuristic methods for this criterion, optimal approaches can be computationally feasible for problems of modest size. This paper presents a new branch-and-bound algorithm for minimizing WCSS. Algorithmic enhancements include an effective reordering of objects and a repetitive solution approach that precludes the need for splitting the data set, while maintaining strong bounds throughout the solution process. The new algorithm provided optimal solutions for problems with up to 240 objects and eight well-separated clusters. Poorly separated problems with no inherent cluster structure were optimally solved for up to 60 objects and six clusters. The repetitive branch-and-bound algorithm was also successfully applied to three empirical data sets from the classification literature.

Precise pose estimation is crucial to various robots. In this paper, we present a localization method using correlative scan matching (CSM) technique for indoor mobile robots equipped with 2D-LiDAR to provide precise and fast pose estimation based on the common occupancy map. A pose tracking module and a global localization module are included in our method. On the one hand, the pose tracking module corrects accumulated odometry errors by CSM in the classical Bayesian filtering framework. A low-pass filter associating the predictive pose from odometer with the corrected pose by CSM is applied to improve precision and smoothness of the pose tracking module. On the other hand, our localization method can autonomously detect localization failures with several designed trigger criteria. Once a localization failure occurs, the global localization module can recover correct robot pose quickly by leveraging branch-and-bound method that can minimize the volume of CSM-evaluated candidates. Our localization method has been validated extensively in simulated, public dataset-based, and real environments. The experimental results reveal that the proposed method achieves high-precision, real-time pose estimation, and quick pose retrieve and outperforms other compared methods.

This paper addresses the flight path planning problem for multiple missiles engaging stationary targets in high-risk areas. Targets protected by air defence are preferably engaged by a fleet or swarm of missiles, not individual missiles. The concept of a swarm attack is that a large number of approaching missiles overwhelm air defence. The deployment of missiles is often part of a broader mission including further participants. Flight path planning is then an integral element of mission planning, requiring strict timing coordination of all members involved. The flight times of the missiles are dictated by the master planning. We present algorithms for offline planning and online re-planning of flight paths for a fleet of missiles with flight time constraints. The algorithms are based on an advanced bidirectional RRT* algorithm that generates risk-minimizing flight paths with predefined flight times. Online planning generates the flight paths of the fleet sequentially, maintaining a safety distance between the missiles to prevent mutual collision. Offline planning uses a global optimization approach to determine an optimal selection of flight paths from a large set of potential paths. The selection is performed by a branch and bound algorithm that determines optimal cliques in the path compatibility graph. The optimization is embedded in an iterative algorithm that allows to successively improve the mission success.

In this paper we consider the problem of scheduling, on a two-machine flowshop, a set ofunit-time operations subject to time delays with respect to the makespan. This problem isknown to be \hbox{${\cal NP}$}𝒩𝒫-hard in the strong sense. We propose an algorithm basedon a branch and bound enumeration scheme. This algorithm includes the implementation ofnew lower and upper bound procedures, and dominance rules. A computer simulation tomeasure the performance of the algorithm is provided for a wide range of testproblems.

The purpose of this paper is to demonstrate that, for globally minimize one dimensional nonconvex problems withboth twice differentiable function and constraint, we can propose an efficientalgorithm based on Branch and Bound techniques. The method is firstdisplayed in the simple case with an interval constraint. The extension is displayedafterwards to the general case with an additional nonconvex twicedifferentiable constraint. A quadratic bounding function which is betterthan the well known linear underestimator is proposed while w-subdivision is added to support the branching procedure. Computational results on several andvarious types of functions show the efficiency of our algorithms and theirsuperiority with respect to the existing methods.

We propose a parallel algorithm which uses bothMonte-Carlo and quasi-Monte-Carlo methods. A detailed analysis of thisalgorithm, followed by examples, shows that the estimator's efficiencyis a linear function of the processor number. As a concrete applicationexample, we evaluate performance measures of a multi-class queueingnetwork in steady state.

The aim of this paper is to present a new branch and boundmethod for solving the Multi-Processor Flow-Shop. This method is based on the relaxation of the initial problem to m-machine problems corresponding to centers. Release dates and tails are associated with operations andmachines. The branching scheme consists in fixing the inputs of a critical centerand the lower bounds are those of the m-machine problem. Several techniques for adjusting release dates and tails have also been introduced. As shown byour personal study, the overall method is very efficient.

We address the 3-Machine Assembly-Type Flowshop Scheduling Problem (3MAF). This problem is known to be NP-complete in the strongsense. We propose an exact branch and bound method based on a recursiveenumeration of potential inputs and outputs of the machines. Using this algorithm,several large size instances have been solved to optimality.