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]

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]

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]

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]

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]