Search

The relative pose estimation problem is important for multi-robot systems when they execute a variety of tasks cooperatively, such as cooperative sensing, multi-robot search and rescue, formation control. The finding of reliable solutions to this problem is essential, however, algorithms that guarantee to provide globally optimal solutions are still in demand. In this paper, an alternative dimensionality reduced objective function is proposed for the planar ground multi-robot relative pose estimation problem, and a new branch-and-bound (BnB) based method is developed, through which initialization is not required and the globally optimal solution is guaranteed under arbitrary noise levels. We demonstrate that the globally optimal solutions obtained via the algorithm proposed in this paper are superior than that obtained by existing classic methods such as SE-Sync algorithm when noise levels are high. Moreover, the method proposed is simple and easy to implement. [ABSTRACT FROM AUTHOR]

Although the optimal power flow (OPF) problem has been extensively studied, solving realistic OPF models that accurately represent the operating behavior of power system components remains challenging. This paper proposes a novel model for the AC OPF problem, aiming to minimize the fuel costs of thermal units while taking into account valve-point loading effects (VPLE), prohibited operation zones (POZ), multiple fuel options (MFO), and operational rules associated with the discrete tap ratios of on-load tap changer (OLTC) transformers and with the discrete shunt susceptances of capacitor/reactor banks. These rules are represented using complementarity constraints. We propose a solution approach that integrates several strategies to address the non-smooth features of the objective function related to VPLE, the disjoint constraints and functions tied to POZ and MFO, the discrete characteristics of the reactive control variables, and the complementarity constraints governing operational rules linked to voltage control devices such as OLTC transformers and capacitor/reactor banks. The resulting optimization problem is designed to be compatible with commercial solver packages. Numerical tests on the IEEE 30, 118, and 300-bus systems aim to examine the cumulative impact of these operational factors on the optimal solution. The solution strategy proposed has demonstrated its effectiveness in solving the proposed OPF problem within reasonable computation times. • This paper proposes a novel model for the AC OPF problem. • The model proposed represents operational rules governing reactive power controls. • Although used in practical, these rules have not been addressed in the literature. • The novel rules are represented using complementarity constraints. • Proposed solution approach integrates strategies to handle imposed characteristics. [ABSTRACT FROM AUTHOR]

This paper investigates a type of minimax linear fractional program (MLFP) that often occurs in practical problems such as design of electronic circuits, finance and investment. We first transform the MLFP problem into an equivalent problem (EP) by using the Charnes–Cooper transformation and introducing an auxiliary variable. A linear relaxation strategy should simplify the nonconvex parts of the constraints in (EP). For globally solving MLFP, a branch-and-bound algorithm is then developed. It integrates the presented relaxation with the one-dimensional branching. The convergence of the algorithm is demonstrated and the number of worst-case iterations is estimated. Finally, preliminary numerical experiments verify that the proposed algorithm in this article is robust and efficient for solving the tested instances. [ABSTRACT FROM AUTHOR]

This paper examines the coarse-grained approach to parallelization of the branch-and-bound (B&B) algorithm in a distributed computing environment. This approach is based on preliminary decomposition of a feasible domain of mixed-integer programming problem into a set of subproblems. The produced subproblems are solved in parallel by a distributed pool of standalone B&B solvers. The incumbent values found by individual solvers are intercepted and propagated to other solvers to speed up the traversal of B&B search tree. Presented implementation of the approach is based on SCIP, a non-commercial MINLP solver, and Everest, a web-based distributed computing platform. The implementation was tested on several mixed-integer programming problems and a noticeable speedup has been achieved. In the paper, results of a number of experiments with the Traveling Salesman Problem are presented. [ABSTRACT FROM AUTHOR]

Branch-and-Bound (B&B) algorithms are tree-based exploratory methods for solving combinatorial optimization problems exactly to optimality. These problems are often large in size and known to be NP-hard to solve. The construction and exploration of the B&B-tree are performed using four operators: branching, bounding, selection and pruning. Such algorithms are irregular which makes their parallel design and implementation on GPU challenging. Existing GPU-accelerated B&B algorithms perform only a part of the algorithm on the GPU and rely on the transfer of pools of subproblems across the PCI Express bus to the device. To the best of our knowledge, the algorithm presented in this paper is the first GPU-based B&B algorithm that performs all four operators on the device and subsequently avoids the data transfer bottleneck between CPU and GPU. The implementation on GPU is based on the Integer–Vector–Matrix (IVM) data structure which is used instead of a conventional linked-list to store and manage the pool of subproblems. This paper revisits the IVM-based B&B algorithm on the GPU, addressing the irregularity of the algorithm in terms of workload, memory access patterns and control flow. In particular, the focus is put on reducing thread divergence by making a judicious choice for the mapping of threads onto the data. Compared to a GPU-accelerated B&B based on a linked-list, the algorithm presented in this paper solves a set of standard flowshop instances on an average 3.3 times faster. [ABSTRACT FROM AUTHOR]

• The k-nearest neighbors (kNN) classifier is time consuming when the size of the database is large. • We propose a fast k-nearest neighbor algorithm in graph space. • The algorithm extends a Depth-First algorithm dedicated to solving the graph matching problem. • The search spaces whose purpose is to classify a graph G are grouped in one global search tree. • This method outperformed the state-of-the-art algorithms especially when the number of graphs is large. The k-nearest neighbors classifier has been widely used to classify graphs in pattern recognition. An unknown graph is classified by comparing it to all the graphs in the training set and then assigning it the class to which the majority of the nearest neighbors belong. When the size of the database is large, the search of k-nearest neighbors can be very time consuming. On this basis, researchers proposed optimization techniques to speed up the search for the nearest neighbors. However, to the best of our knowledge, all the existing works compared the unknown graph to each train graph separately and thus none of them considered finding the k nearest graphs from a query as a single problem. In this paper, we define a new problem called multi graph edit distance to which k-nearest neighbor belongs. As a first algorithm to solve this problem, we take advantage of a recent exact branch-and-bound graph edit distance approach in order to speed up the classification stage. We extend this algorithm by considering all the search spaces needed for the dissimilarity computation between the unknown and the training graphs as a single search space. Results showed that this approach drastically outperformed the original approach under limited time constraints. Moreover, the proposed approach outperformed fast graph edit distance algorithms in terms of average execution time especially when the number of graphs is tremendous. [ABSTRACT FROM AUTHOR]

Particle breakage of granular materials plays an important role in its microstructure change and macroscopic behavior under external loads. However, measuring the breakage degree of individual particles in a deformed sand specimen still remains a challenge in geomechanics research. This paper presents a novel method that can track and match fragments to the mother particle from which they break off by searching a limited number of candidate particles. Integrating the branch-and-bound search algorithm with the Standard Iterative Closest Point (Standard ICP) algorithm, this method is applied to process and analyze the X-ray tomography data of 9 Leighton Buzzard sand particles, which each was crushed in a single particle crushing test. Firstly, a total of 62 fragments were collected, mixed up and sorted according to its volume (in the descending order). Secondly, the local bending energy algorithm was used to identify the fracture surfaces of each fragment that were resulted from the mechanical crushing of sand particles. Then the branch-and-bound algorithm was employed to determine the lower and upper bounds of cubes and sub-cubes by efficiently searching the 3D translation and rotation spaces. Finally, a trial matching of each fragment to each of the 9 original particles was made to identify the corresponding mother particle and its location in the mother particle. The effectiveness and efficiency of the proposed tracking method was demonstrated by the matching of 62 fragments to their corresponding mother particles. Image 1 • A pioneering investigation on the identifying the fracture surface of fragments. • Child-mother particle matching based on the results of μCT scanning. • The algorithm for child-mother particles matching within an assembly was enhanced. • The effectiveness of the proposed tracking method was demonstrated by 62 fragments. [ABSTRACT FROM AUTHOR]

BORON is a 64-bit lightweight block cipher based on the substitution–permutation network that supports an 80-bit (BORON-80) and 128-bit (BORON-128) secret key. In this paper, we revisit the use of differential cryptanalysis on BORON in the single-key model. Using an SAT/SMT approach, we look for differentials that consist of multiple differential characteristics with the same input and output differences. Each characteristic that conforms to a given differential improves its overall probability. We also implemented the same search using Matsui's algorithm for verification and performance comparison purposes. We identified high-probability differentials which were then used in key recovery attacks against BORON-80/128. We used 8-round differentials with a probability of 2 − 58. 16 and 2 − 62. 42 in key recovery attacks against 9 and 10 rounds of BORON-80 and BORON-128 with time/data/memory complexities of 2 59. 18 / 2 59. 16 / 2 24 and 2 111. 34 / 2 63. 42 / 2 71 respectively. Our key recovery framework provides a more accurate estimate of the attack complexity as compared to previous work. The attacks proposed in this paper are the best differential attacks against BORON-80/128 in the single-key model to date. [ABSTRACT FROM AUTHOR]

In this paper, we deal with the Time-Dependent Asymmetric Traveling Salesman Problem with Time Windows. First, we prove that under special conditions the problem can be solved as an Asymmetric Traveling Salesman Problem with Time Windows, with suitable-defined time windows and (constant) travel times. Second, we show that, if the special conditions do not hold, the time-independent optimal solution provides both a lower bound and (eventually) an upper bound with a worst-case guarantee for the Time-Dependent Asymmetric Traveling Salesman Problem with Time Windows. Finally, a branch-and-bound algorithm is presented and tested on a set of 4800 instances. The results have been compared with those obtained by the only existing exact procedure capable of solving this problem. The new procedure has been able to find a higher number of optimal solutions in this set of instances. [ABSTRACT FROM AUTHOR]

• Consideration of the optimal phasor measurement unit placement problem without radial buses. • Phasor measurement unit is pre-assigned at each bus connected to radial bus. • A two-phase branch-and-bound algorithm is used to determine the strategic locations for placement of phasor measurement unit. • The redundancy measurement is performed for ranking the obtained multiples solutions. This paper proposes a mixed integer nonlinear programming (MINLP) formulation with binary-valued variables for the optimal installation of the phasor measurement units (PMUs) in a power network. The MINLP framework has been solved by a two-phase branch-and-bound algorithm (BBA) for the optimal PMU placement (OPP) problem. The present work deals with the solution of the OPP problem without considering the radial buses including in the optimal solution. PMU is pre-assigned to each bus connected to a radial bus such that the radial buses are excluded from the list of potential PMU locations. The programming technique is used to determine the optimum number of PMUs and their locations to make the interconnected power network completely observable. The proposed BBA may provide multiple solutions at the lowest objective value, each time the optimizer routine restarts. Therefore, the obtained optimal solutions are being ranked regarding the measurement redundancy index. The two-phase branch-and-bound algorithm is applied to IEEE standard test systems as well as to New England 39- bus and a northern regional power grid 246- bus system. The proposed algorithm has been compared with the existing programming techniques in the recent literature. The simulation results obtained by the proposed BBA indicate the effectiveness and the efficiency to detect the desired target. [ABSTRACT FROM AUTHOR]

Abstract Point cloud registration is a fundamental problem in 3D scanning. In this paper, we address the frequent special case of registering terrestrial LiDAR scans (or, more generally, levelled point clouds). Many current solutions still rely on the Iterative Closest Point (ICP) method or other heuristic procedures, which require good initializations to succeed and/or provide no guarantees of success. On the other hand, exact or optimal registration algorithms can compute the best possible solution without requiring initializations; however, they are currently too slow to be practical in realistic applications. Existing optimal approaches ignore the fact that in routine use the relative rotations between scans are constrained to the azimuth, via the built-in level compensation in LiDAR scanners. We propose a novel, optimal and computationally efficient registration method for this 4DOF scenario. Our approach operates on candidate 3D keypoint correspondences, and contains two main steps: (1) a deterministic selection scheme that significantly reduces the candidate correspondence set in a way that is guaranteed to preserve the optimal solution; and (2) a fast branch-and-bound (BnB) algorithm with a novel polynomial-time subroutine for 1D rotation search, that quickly finds the optimal alignment for the reduced set. We demonstrate the practicality of our method on realistic point clouds from multiple LiDAR surveys. [ABSTRACT FROM AUTHOR]

The paper presents a solution to economic dispatch (ED) problems with non-convex, non-smooth fuel cost functions, which characterize practical generating units. A method involving a unified semidefinite programming (SDP) formulation of different ED problems through cost function decomposition was presented. The solution of the resulting rank-relaxed SDP problem was refined to achieve the rank constraint using the method of convex iteration and branch-and-bound technique. The SDP method was investigated on some test problems in the literature. The results showed that the SDP method compared favorably with other methods, and can efficiently solve non-convex and non-smooth ED problems. [ABSTRACT FROM AUTHOR]

Highlights • We study the TWAVRP with both continuous and discrete sets of time windows and general scenario-based models of uncertainty for several routing-specific parameters. • We propose a novel, decomposition algorithm for the TWAVRP that can be easily parallelized, can utilize any available vehicle routing solver as a black box, and can be readily modified as a heuristic. • We propose a new class of path-based disjunctions for the TWAVRP. • We conduct a comprehensive numerical study demonstrating that our algorithm outperforms all state of the art methods. Abstract We study the strategic decision-making problem of assigning time windows to customers in the context of vehicle routing applications that are affected by operational uncertainty. This problem, known as the Time Window Assignment Vehicle Routing Problem, can be viewed as a two-stage stochastic optimization problem, where time window assignments constitute first-stage decisions, vehicle routes adhering to the assigned time windows constitute second-stage decisions, and the objective is to minimize the expected routing costs. To that end, we develop in this paper a new scenario decomposition algorithm to solve the sampled deterministic equivalent of this stochastic model. From a modeling viewpoint, our approach can accommodate both continuous and discrete sets of feasible time window assignments as well as general scenario-based models of uncertainty for several routing-specific parameters, including customer demands and travel times, among others. From an algorithmic viewpoint, our approach can be easily parallelized, can utilize any available vehicle routing solver as a black box, and can be readily modified as a heuristic for large-scale instances. We perform a comprehensive computational study to demonstrate that our algorithm strongly outperforms all existing solution methods, as well as to quantify the trade-off between computational tractability and expected cost savings when considering a larger number of future scenarios during strategic time window assignment. [ABSTRACT FROM AUTHOR]

This paper considers a joint scheduling problem of macro-level yard section allocation and transfer manpower assignment in automobile RO-RO terminals. The joint scheduling problem is formulated as a mixed integer programming model with the objective of minimizing the total necessary driving distance of vehicles. Relaxation cases derived from a series of ingenious problem analyses and dual segmentation techniques based on mathematical derivations are presented. In addition, compressed strategies are applied to reduce the complexity of our problem. Then, we develop an amalgamated algorithm consisting of a rule-based stepwise algorithm, a reinforced column generation, and a multi-root branch-and-bound. Numerical experiments based on random data and a case study based on real operation data are conducted to evaluate the performance of our algorithms. The results show that the proposed algorithms are capable of generating high-quality solutions efficiently and are of great practical value in daily operations. • A joint scheduling problem of RO-RO terminals is studied. • A mixed integer programming model is built. • Relaxation and dual segmentation are applied to develop algorithms. • A column generation based heuristic algorithm is proposed. • A series of experiments with case study are conducted. [ABSTRACT FROM AUTHOR]

Abstract Given a set A ⊆ S n of m permutations of { 1 , 2 , ... , n } and a distance function d , the median problem consists of finding a permutation π ⁎ that is the "closest" of the m given permutations. Here, we study the problem under the Kendall- τ distance which counts the number of order disagreements between pairs of elements of permutations. In this article, which is an extended version of the conference paper [28] , we explore this NP-complete problem using four different approaches: a well parameterized heuristic, an improved search space reduction technique, a refined branch-and-bound solver and an integer linear programming approach using IBM CPLEX. All approaches are tested on synthetic and real life data sets. Combining those approaches, we were able to solve the "ED-00015-00000004.soc" instance from PrefLib which, to our knowledge, was never achieved before. [ABSTRACT FROM AUTHOR]

Abstract Previous publications presented an implementation of coarse-grained parallel Branch-and-Bound (B&B) method. It supports two strategies: decomposition of feasible domain into a set of sub-problems; "multisearch" (or concurrent) solving the same problem with different settings of the BNB-method. In both cases several B&B-solver's processes exchange best values of goal function on feasible solutions they found. Earlier, it was found that this approach gives a noticeable speed-up of solving the original optimization problem. The method has been implemented as an Everest-application called DDBNB (Domain Decomposition B&B). It is based on Everest distributed computing platform, everest.distcomp.org, and open source solvers: CBC, projects.coin-or.org/Cbc; SCIP, scip.zib.de. Originally, DDBNB has been tested on discrete optimization problems (Traveling Salesman and Load Balancing). The paper presents application of DDBNB to global optimization problems with polynomial functions (solver SCIP supports solving of such class of problems). Well known problems concerning optimal placements of points on 3D-sphere are considered: Tammes and Thomson problems. The first problem is to maximize minimal distance between any two of N points. The second - minimize electrostatic Coulomb energy of unit charges put in N points. Both may be represented as mathematical programming problems with polynomial functions. Feasible domains of both problems are direct products of 3D-spheres and different decompositions of this domains by linear inequalities into hundreds of subproblems have been tested. Tests performed gave promising results and crucial acceleration for Tammes problems, N =7,8,9, and Thomson problem, N =5. One should note that Thomson problem got computer aided proof (substantially based on the problem's specifics) less than a decade ago, when proposed approach is rather generic and does not go into details of the problem to be solved. Formulation of original problems and decomposition strategies have been implemented via Pyomo, pyomo.org. All sub-problems have been passed to solvers as AMPL-stubs, (also known as NL-files). Usage of Everest platform enables to involve in experiments HPC resources of NRC Kurchatov Institute. [ABSTRACT FROM AUTHOR]

This paper introduces the problem of backfeed fiber cables network design. It considers cable separation operations and costs as well as a non-linear cable line cost, and the feedback technique. An integer programming based solution is proposed, and some associated valid inequalities are introduced. The problem is proven to be NP-Hard. The formulation is assessed on real-life instances. [ABSTRACT FROM AUTHOR]

Graph Distance Contest (GDC) was organized in the context of ICPR 2016. Its main challenge was to inspect and report performances and effectiveness of exact and approximate graph edit distance methods by comparison with a ground truth. This paper presents the context of this competition, the metrics and datasets used for evaluation, and the results obtained by the eight submitted methods. Results are analyzed and discussed in terms of computation time and accuracy. We also highlight the future challenges in graph edit distance regarding both future methods and evaluation metrics. The contest was supported by the Technical Committee on Graph-Based Representations in Pattern Recognition (TC-15) of the International Association of Pattern Recognition (IAPR). [ABSTRACT FROM AUTHOR]

In this paper, a spatial branch-and-bound algorithm with an adaptive branching rule is proposed for solving linear multiplicative programming (LMP) problem. In the solution algorithm, LMP problem is first transformed into an equivalent problem, and a novel reformulation is then introduced to convert the nonconvex constraints into differences of square terms form, subsequently using a piecewise linear approximation for the concave part. By using the proposed adaptive branching rule for dividing rectangles and iteratively refining the piecewise linear approximations, the process of solving LMP problem can be translated into solving a series of second order cone relaxations (SOCR). Also, we discuss the bound on the optimality gap as a function of the approximation errors at the iterate, and estimate the computational complexity in the order of O (ɛ) to attain an ɛ -optimal solution. Finally, preliminary numerical results demonstrate that the proposed algorithm can efficiently find the global optimal solutions for test instances. [ABSTRACT FROM AUTHOR]

• All the transformation parameters including those of translation are regularized in our CVPR paper, causing the method not able to handle un- known arbitrary translations. To address this issue, we show that under a mild condition, the objective function of RPM is strictly convex quadratic w.r.t. translation. Thus, translation can first be eliminated via minimization. Then, we only need to enforce regularization on the non-translational part of the transformation. This enables our algorithm to handle unknown arbitrary translations and more applicable to practical problems. • Our CVPR paper imposes regularization on transformation which causes the transformation solution close to the predefined value. To address this issue, we propose a new formulation targeted at 2D/3D similarity registration problems, where regularization on transformation is abandoned in favor of constraints on transformation. This results in an algorithm capable of handling unknown arbitrary similarity transformations. • We conducted extensive experiments on 2D/3D synthetic and real data to test the performance ofthe proposed method. The experimental results demonstrate much better robustness of the proposed method over state-of-the-art methods. Matching partially overlapping point sets is a challenging problem in computer vision. To achieve this goal, we model point matching as a mixed linear assignment - least square problem. By eliminating the transformation variable, we reduce the minimization problem to a concave optimization problem with the property that the objective function can be converted into a form with few nonlinear terms. We then use a heuristic variant of the branch-and-bound algorithm for optimization where convergence of the upper bound is used as the stopping criterion. We also propose a new lower bounding scheme which involves solving a k-cardinality linear assignment problem. Two cases of transformations, transformation output being linear with respect to parameters and 2D/3D similarity transformations, are discussed, resulting in ability to handle unknown arbitrary translation and similarity, respectively. Experimental results demonstrate better robustness of the algorithm over state-of-the-art methods. [ABSTRACT FROM AUTHOR]

• This paper is concerned with solving the parameter estimation problem of PV cells. • An interval branch and bound global optimization algorithm is applied for estimating the unknown PV parameters. • Accuracy of the proposed algorithm is proved against other optimization algorithms. • The performance of two fitness functions, Maximal Absolute Error and Root Mean Square Error, is assessed. In this paper, an interval branch and bound algorithm is proposed to estimate the parameters for three models of photovoltaic (PV) cells. These models are a single diode model (SDM), a double diode model (DDM) and a three diode model (TDM). The minimization of Maximal Absolute Error (MAE) based on the infinite norm is evaluated and compared with the common used objective function called the Root Mean Square Error (RMSE). The MAE aims to minimize the average error on a set of experimental data. In this regard, the parameter estimation is reformatted. The performance of the proposed optimization algorithm is analyzed and tested on all three models. It has good convergence and robust statistical analysis at different operating conditions as well as for various models. The estimated performance characteristics for current-voltage (I - V) and power-voltage (P-V) of the tested cells are very close to the experimental data and compete with existing works in the literature. [ABSTRACT FROM AUTHOR]

In this paper, a new variable partitioning strategy in Benders decomposition method is applied that enables us to deal with a wide class of mixed-integer nonlinear programming problems including fixed-charge multicommodity network design (FMND) problems under congestion effects. It is proved that the proposed technique for an FMND problem leads to a simple branch-and-bound algorithm such that each node of the branching tree includes a single conic quadratic representable problem consisting of only continuous (flow) variables. Preliminary numerical results are reported. [ABSTRACT FROM AUTHOR]

The main obstacles to boosting the bicycle as a mode of transport are safety concerns due to interactions with motorized traffic. One option is to separate cyclists from motorists through exclusive bicycle priority lanes. This practice is easily implemented in uncongested traffic. Enforcing bicycle lanes on congested roads may degenerate the network, making the idea very hard to sell both to the public and the traffic authorities. Inspired by Braess Paradox, we take an unorthodox approach to seeking latent misutilized capacity in the congested networks to be dedicated to exclusive bicycle lanes. The aim of this study is to tailor an efficient and practical method to large size urban networks. Hence, this paper appeals to policy makers in their quest to scientifically convince stakeholder that bicycle is not a secondary mode, rather, it can be greatly accommodated along with other modes even in the heart of the congested cities. In conjunction with the bicycle lane priority, other policy measures such as shared bicycle scheme, electric-bike, integration of public transport and bicycle are also discussed in this article. As for the mathematical methodology, we articulated it as a discrete bilevel mathematical programing. In order to handle the real networks, we developed a phased methodology based on Branch-and-Bound (as a solution algorithm), structured in a less intensive RAM manner. The methodology was tested on real size network of city of Winnipeg, Canada, for which the total of 30 road segments – equivalent to 2.77 km bicycle lanes – in the CBD were found. [ABSTRACT FROM AUTHOR]

One of the biggest challenges in the field of computational neuroscience from the perspective of complex network analysis is the measurement of dynamic local and global interactions of the brain regions during cognitive function. Graph theoretic analysis has been extensively applied to study the dynamics of functional brain networks in the recent years. The selection of appropriate thresholding methods to construct weighted/unweighted subnetworks to detect cognitive load induced changes in brain׳s electrical activity remains an open challenge in the functional brain network research. This paper reviews the application of statistical and information theoretic metrics to construct the functional brain networks, proposes a novel Branch-and-Bound based thresholding algorithm that extracts the influential subnetwork, and applies efficient computational techniques and complex network metrics to detect and quantify the cognitive activities. The empirical analyses showcase the efficiency of the proposed thresholding algorithm by highlighting the changing neuronal patterns during cognitive activity when compared to that of baseline activity. Statistical evaluation of the results further validates the efficiency of the proposed method as well. The results demonstrate the ability of the proposed algorithm in detecting subtle cognitive load induced changes in functional brain networks. [ABSTRACT FROM AUTHOR]

Branch-and-bound (B&B) feature selection finds optimal feature subsets without performing an exhaustive search. However, the classification accuracy achievable with optimal B&B feature subsets is often inferior compared to the accuracy achievable with other algorithms that guarantee optimality. We argue this is due to the existing criterion functions that define the optimal feature subset but may not conceive inherent nonlinear data structures. Therefore, we propose B&B feature selection in Reproducing Kernel Hilbert Space (B&B-RKHS). This algorithm employs two existing criterion functions (Bhattacharyya distance, Kullback–Leibler divergence) and one new criterion function (mean class distance), however, all computed in RKHS. This enables B&B-RKHS to conceive inherent nonlinear data structures. The algorithm was experimentally compared to the popular wrapper approach that has to use an exhaustive search to guarantee optimality. The classification accuracy achieved with both methods was comparable. However, runtime of B&B-RKHS was superior using the two existing criterion functions and even completely out of reach using the new criterion function (about 60 times faster on average). Therefore, this paper proposes an efficient algorithm if feature subsets that guarantee optimality have to be selected in data sets with inherent nonlinear structures. [ABSTRACT FROM AUTHOR]

In this paper we propose an improved version of a core based algorithm for the multi-objective extension of one of the most well-known combinatorial optimization problems, the multi-dimensional knapsack problem. The original algorithm was designed only for bi-objective problems combining an extension of the core concept and a branch-and-bound algorithm. It is a deterministic algorithm and the core concept exploits the “divide and conquer” solution strategy which proves very effective in such problems. The new version is not limited to bi-objective problems; it can effectively handle problems with more than two objective functions and it has features that greatly accelerate the solution process. Namely, these features are the use of a heuristic based on the Dantzig bound in the fathoming process and the better housekeeping of the incumbent list through filtering of solutions. The key parameters of the new algorithm are (a) the size of the core and (b) the number of provided cores. Varying these parameters the user can easily tune the size of the obtained Pareto set. A comparison with evolutionary algorithms, like NSGA–II, SPEA2 and MOEA/D, has been made according to run time and the most widely used metrics (set coverage, set convergence etc). Our new version performs better than the most popular evolutionary algorithms and it is comparable to very recent state-of-the-art metaheuristics, like Multi-objective Memetic Algorithm based on Decomposition (MOMAD), for multi-objective programming. [ABSTRACT FROM AUTHOR]

The weighted sum coloring problem (WSCP) is an extension of the weighted vertex coloring problem and sum coloring problem, and has important applications in the batch scheduling of distributed systems. Compared to the weighted vertex coloring problem and sum coloring problem, where extensive methods have been proposed for efficiently solving graphs in the real world, fewer solvers have been developed for WSCP, especially no practical complete algorithm is available for solving WSCP. This paper is devoted to design branch-and-bound strategies for solving WSCP, including a branching heuristic rule, a lower bound based on weighted clique partitioning, and a branching search framework for searching all possible coloring solutions. As a result, a new branch-and-bound algorithm BABWSCP is proposed. We also design a novel combination method for improving the local search using complete algorithm in the restart process for WSCP. Consequently, a new local search algorithm named BABLS is designed. Experimental results show that our branch-and-bound strategies are effective, and BABLS almost always outperforms the state-of-the-art WSCP solvers for the benchmarks studied in previous works. • Novel branching heuristics and lower bound based on weighted clique partitioning for weighted sum coloring problem. • An efficient branch-and-bound algorithm BABWSCP for weighted sum coloring problem. • A paradigm of improving local search using branch-and-bound for weighted sum coloring problem. • An algorithm BABLS by improving the local search algorithm CCLSWSC using the branch-and-bound algorithm BABWSCP. [ABSTRACT FROM AUTHOR]

Block ciphers are prevalent in various security protocols used daily such as TLS, OpenPGP, and SSH. Their primary purpose is the protection of user data, both in transit and at rest. One of the de facto methods to evaluate block cipher security is differential cryptanalysis. Differential cryptanalysis observes the propagation of input patterns (input differences) through the cipher to produce output patterns (output differences). This probabilistic propagation is known as a differential; the identification of which is a measure of a block cipher's security margins. This paper introduces an optimized GPU-based branch-and-bound framework for differential search. We optimize search efficiency by parallelizing all branch-and-bound operations, completing the entire search on the GPU without communicating with the CPU. The meet-in-the-middle (MITM) approach is also adopted for further performance gains. We analyze the financial and computational costs of the proposed framework using Google Cloud VM to showcase its practicality. When optimized for performance, we can attain up to 90x speedup while saving up to 47% of the running cost as compared to a single CPU core. When optimized for cost, the proposed framework can save up to 83% of financial costs while retaining a speedup of up to 40x. As a proof of concept, the proposed framework was then applied on 128-bit TRIFLE-BC, 64-bit PRESENT, and 64-bit GIFT. Notably, we identified the best differentials for PRESENT (16 rounds) and 64-bit GIFT (13 rounds) to date, with estimated probabilities of 2 − 61. 7964 and 2 − 60. 66 respectively. Although the differential results for TRIFLE-BC were incremental, the proposed framework was able to construct differentials for 43 rounds that consisted of approximately 5.8x more individual trails than previous work, making it one of the most efficient approaches for larger block ciphers. • An automated differential search tool for block cipher security evaluation based on the branch and bound strategy optimized for GPU environments. • Able to construct differentials within seconds (for a 64-bit block cipher) and minutes (for a 128-bit block cipher). • Detailed financial and computational cost analysis on Google Cloud VM showcases the framework's practicality. • Source codes of the algorithms for all target three ciphers are made available to readers for future block cipher analysis efforts. • An algorithmic tool that requires minimal cryptographic or mathematical expertise. [ABSTRACT FROM AUTHOR]

• A new problem formulation allowing en-route charges as many times as needed for electric vehicles. • A bi-level integer programming model on the basis of subpath and path-subpath relationship. • Application of the emerging nested partitions algorithm and classic branch-and-bound algorithm. This paper addresses a new electricity-charging station location problem for congested intercity or regional networks, in which electric vehicles with a limited driving range require recharges for their long-distance trips. When the distribution of charging stations does not sufficiently cover all used routes, some drivers may take a detour to find charging opportunities (or switch to another transportation mode). The goal of this station location problem is to find, under a limited construction budget, an optimal set of charging station locations such that all vehicles finish their trips by choosing a self-optimal route with necessary charging opportunities while the overall network congestion caused by possible detours is minimized. The problem is written as a bi-level mixed nonlinear integer programming model, where the upper level of the model is set to regulate the selection of station locations subject to the construction budget while the lower level is used to characterize the equilibrium flow pattern of electric vehicles with the charging requirement. Selected exact and approximate algorithms, namely, the branch-and-bound algorithm and the nested partitions algorithm are adopted to solve this station location problem. While both algorithms imply a divide-and-conquer strategy, the branch-and-bound algorithm poses a deterministic, exact procedure that utilizes the bounding mechanism to prune impossible solution subspaces, whereas the nested partitions algorithm performs a stochastic search and selection process in terms of the optimality probability for near-optimal solutions. To get numerical insights on the algorithmic performance and solution behavior, we test these algorithms through a couple of benchmark network instances. A performance comparison of the algorithms indicates that, the branch-and-bound algorithm can quickly obtain the global optimum when the driving range is relatively low, while the nested partitions algorithm can find optimal solutions or extremely near-optimal solutions in all cases and typically spend on average only one fourth of the computing time of the branch-and-bound algorithm. The network flow solutions clearly show, compared to gasoline vehicle drivers, how an insufficient driving range or number of charging stations may significantly reduce the number of feasible paths and force electric vehicle drivers to choose more costly paths, which thus reshapes flow patterns and possibly increases congestion levels. [ABSTRACT FROM AUTHOR]

Task scheduling with communication delays is a strongly NP-hard problem. Previous attempts at finding optimal solutions to this problem have used branch-and-bound state–space search, with promising results. However, the scheduling model used assumes a target system with fully homogeneous processors, which is unrealistic for many real world systems for which task scheduling might be performed. This paper presents an extension to the Allocation-Ordering (AO) state–space model for task scheduling which allows a system with related heterogeneous processors to be modeled, and optimal schedules on such a system to be found. Of particular note, the distinct allocation phase allows this model to efficiently adapt to partially heterogeneous systems, in which subsets of the processors are identical to each other, which significantly helps to reduce the search space. An extensive experimental evaluation shows that the introduction of heterogeneity certainly increases the difficulty of the problem. However, many problem instances solvable using homogeneous processors remain solvable with a heterogeneous target system, made possible by the significant benefit of this model in considering partial heterogeneity. [ABSTRACT FROM AUTHOR]

In this paper, parallelization techniques are proposed for the branch-and-bound algorithm OTClique for the maximum weight clique problem. OTClique consists of the precomputation phase and the branch-and-bound phase. The proposed algorithm parallelizes both of them. In the precomputation phase, the construction of optimal tables is parallelized. In the branch-and-bound phase, the proposed algorithm generates small subproblems and assigns them to threads. A technique to share lower and upper bounds is also proposed. Experiments using some benchmarks show that the proposed parallelization techniques improve the performance of OTClique. With an 8-core CPU, the computation time of OTClique becomes 6.91 times shorter on random graphs and 5.38 times on DIMACS benchmarks on average. [ABSTRACT FROM AUTHOR]

Railway capacity is a scarce and expensive resource that has to be utilised in the best way possible. Many methods exist for medium- and short-term planning and analysis of railway capacity. Yet, there is a lack of methods for long term (strategic) planning that provides high quality estimates of capacity in complex railway networks. In this paper, we define capacity of a railway network by a maximal set of trains that can be operated in a predefined period. This maximal set distinguish between different train types and the number of each type, and thus the heterogeneity of the operation. We formalise the capacity determination as an optimisation problem with the objective of finding the maximal set of trains that minimises the average waiting time between trains of the same type. We test for feasibility of sets of trains by computing the time a set of trains occupies the infrastructure. A fixed timetable is not needed for the feasibility tests as samples of train sequences are examined. Furthermore, it is possible to determine a span of capacity depending on service constraints by adjusting input parameters. We propose and test two different solution approaches to determine the capacity of railway infrastructure: an exact branch-and-bound algorithm and a tabu search heuristic. The applicability of the capacity determination framework is demonstrated on the railway network of Southwestern Denmark, with and without infrastructure upgrades. We analyse computation time, solution performance and sensitivity. The results illustrate the ability to obtain quality solutions for a real network within the order of minutes. As precise infrastructure characteristics are considered in junctions, the method is able to quantify the effect of the infrastructure upgrades, contrary to other assessment methods used in the long term (strategic) planning phase. • New approach determines the maximal set of trains to be operated on a network. • Heterogeneous train operation is handled without the need of a fixed timetable. • Branch-and-bound & tabu search used to solve defined capacity determination problem. • Ideal for early planning as little input is required while maintaining precision. • Case study on Danish rail network reveals capacity improvements from upgrades. [ABSTRACT FROM AUTHOR]

The maximum edge-weight clique problem is to find a clique whose sum of edge-weight is the maximum for a given edge-weighted undirected graph. The problem is NP-hard and some branch-and-bound algorithms have been proposed. In this paper, we propose a new exact algorithm based on the branch-and-bound method. It assigns edge-weights to vertices and calculates upper bounds using vertex coloring. By some computational experiments, we confirmed our algorithm works fine. [ABSTRACT FROM AUTHOR]