Search

This paper deals with p-location problem solving processes based on a decomposition, which separates the creation of a uniformly deployed set of p-location problems from the solution of the p-location problem for that specific instance. The research presented in this paper is focused on methods of construction of uniformly deployed sets of solutions and the examination of their impact on the efficiency of subsequent optimization algorithms. The approaches to the construction are used for the constitution of predetermined families of uniformly deployed sets of p-location problem solutions, which have standard sizes. We introduce two methods of uniformly deployed set construction: the first one is based on composition, followed by an enlargement process; and the second one makes use of voltage graphs. The construction approaches are completed by an algorithm, which adjusts the set of solutions to the sizes of a solved instance. The influence of a set construction approach on solving process efficiency is studied on real-world benchmarks, which include both the p-median objective function and the generalized disutility function. The solving process is performed alternatively using the swap or path-relinking based methods. Results of the computational study obtained by all combinations of the mentioned approaches are presented and evaluated in the concluding part of the paper to make the studied characteristics visible. [ABSTRACT FROM AUTHOR]

Feature extraction is an important part of perceptual hashing. How to compress the robust features of images into hash codes has become a hot research topic. Converting a two-dimensional image into a one-dimensional descriptor requires a higher computational cost and is not optimal. In order to maintain the internal feature structure of the original two-dimensional image, a new Bilinear Supervised Neighborhood Discrete Discriminant Hashing (BNDDH) algorithm is proposed in this paper. Firstly, the algorithm constructs two new neighborhood graphs to maintain the geometric relationship between samples and reduces the quantization loss by directly constraining the hash codes. Secondly, two small rotation matrices are used to realize the bilinear projection of the two-dimensional descriptor. Finally, the experiment verifies the performance of the BNDDH algorithm under different feature types, such as image original pixels and a Convolutional Neural Network (CNN)-based AlexConv5 feature. The experimental results and discussion clearly show that the proposed BNDDH algorithm is better than the existing traditional hashing algorithm and can represent the image more efficiently in this paper. [ABSTRACT FROM AUTHOR]

The paper solves the problem of constructing an evolutionary tree and the evolution of structures along it. This problem has long been posed and extensively researched; it is formulated and discussed below. As a result, we construct an exact cubic-time algorithm which outputs a tree with the minimum cost of embedding into it and of embedding it into a given network (Theorem 1). We construct an algorithm that outputs a minimum embedding of a tree into a network, taking into account incomplete linear sorting; the algorithm depends linearly on the number of nodes in the network and is exact if the sorting cost is not less than the sum of the duplication cost and the loss cost (Theorem 3). We construct an exact approximately quadratic-time algorithm which, for arbitrary costs of SCJ operations, solves the problem of reconstruction of given structures on any two-star tree (Theorem 4). We construct an exact algorithm which reduced the problem of DCJ reconstruction of given structures on any star to a logarithmic-length sequence of SAT problems, each of them being of approximately quadratic size (Theorem 5). The theorems have rigorous and complete proofs of correctness and complexity of the algorithms, and are accompanied by numerical examples and numerous explanatory illustrations, including flowcharts. [ABSTRACT FROM AUTHOR]

Optimization problems are prevalent in almost all areas and hence optimization algorithms are crucial for a myriad of real-world applications. Deterministic optimization algorithms tend to be computationally costly and time-consuming. Hence, heuristic and metaheuristic algorithms are more favoured as they provide near-optimal solutions in an acceptable amount of time. Swarm intelligence algorithms are being increasingly used for optimization problems owing to their simplicity and good performance. The Dragonfly Algorithm (DA) is one which is inspired by the swarming behaviours of dragonflies, and it has been proven to have a superior performance than other algorithms in multiple applications. Hence, it is worth considering its application to the traveling salesman problem which is a predominant discrete optimization problem. The original DA is only suitable for solving continuous optimization problems and, although there is a binary version of the algorithm, it is not easily adapted for solving discrete optimization problems like TSP. We have previously proposed a discrete adapted DA algorithm suitable for TSP. However, it has low effectiveness, and it has not been used for large TSP problems. In this paper, we propose an optimized discrete adapted DA by using the steepest ascent hill climbing algorithm as a local search. The algorithm is applied to a TSP problem modelling a package delivery system in the Kuala Lumpur area and to benchmark TSP problems, and it is found to have a higher effectiveness than the discrete adapted DA and some other swarm intelligence algorithms. It also has a higher efficiency than the discrete adapted DA. [ABSTRACT FROM AUTHOR]

This paper presents a hybridization of Strategic Oscillation with Path Relinking to provide a set of high-quality nondominated solutions for the Multiobjective k-Balanced Center Location problem. The considered location problem seeks to locate k out of m facilities in order to serve n demand points, minimizing the maximum distance between any demand point and its closest facility while balancing the workload among the facilities. An extensive computational experimentation is carried out to compare the performance of our proposal, including the best method found in the state-of-the-art as well as traditional multiobjective evolutionary algorithms. [ABSTRACT FROM AUTHOR]

With the advent of novel quantum computing technologies and the new possibilities thereby offered, a prime opportunity has presented itself to investigate the practical application of quantum computing. This work investigates the feasibility of using quantum annealing for structural optimization. The target problem is the discrete truss sizing problem—the goal is to select the best size for each truss member so as to minimize a stress-based objective function. To make the problem compatible with quantum annealing devices, the objective function must be translated into a quadratic unconstrained binary optimization (QUBO) form. This work focuses on exploring the feasibility of making this translation. The practicality of using a quantum annealer for such optimization problems is also assessed. A method is eventually established to translate the objective function into a QUBO form and have it solved by a quantum annealer. However, scaling the method to larger problems faces some challenges that would require further research to address. [ABSTRACT FROM AUTHOR]

With many efficient solutions for a multi-objective optimization problem, this paper aims to cluster the Pareto Front in a given number of clusters K and to detect isolated points. K-center problems and variants are investigated with a unified formulation considering the discrete and continuous versions, partial K-center problems, and their min-sum-K-radii variants. In dimension three (or upper), this induces NP-hard complexities. In the planar case, common optimality property is proven: non-nested optimal solutions exist. This induces a common dynamic programming algorithm running in polynomial time. Specific improvements hold for some variants, such as K-center problems and min-sum K-radii on a line. When applied to N points and allowing to uncover M < N points, K-center and min-sum-K-radii variants are, respectively, solvable in O (K (M + 1) N log N) and O (K (M + 1) N 2) time. Such complexity of results allows an efficient straightforward implementation. Parallel implementations can also be designed for a practical speed-up. Their application inside multi-objective heuristics is discussed to archive partial Pareto fronts, with a special interest in partial clustering variants. [ABSTRACT FROM AUTHOR]

We propose introducing fairness constraints to one of the most famous multi-criteria decision-making methods, the analytic hierarchy process (AHP). We offer a solution that guarantees consistency while respecting legally binding fairness constraints in AHP pairwise comparison matrices. Through a synthetic experiment, we generate the comparison matrices of different sizes and ranges/levels of the initial parameters (i.e., consistency ratio and disparate impact). We optimize disparate impact for various combinations of these initial parameters and observed matrix sizes while respecting an acceptable level of consistency and minimizing deviations of pairwise comparison matrices (or their upper triangles) before and after the optimization. We use a metaheuristic genetic algorithm to set the dually motivating problem and operate a discrete optimization procedure (in connection with Saaty's 9-point scale). The results confirm the initial hypothesis (with 99.5% validity concerning 2800 optimization runs) that achieving fair ranking while respecting consistency in AHP pairwise comparison matrices (when comparing alternatives regarding given criterium) is possible, thus meeting two challenging goals simultaneously. This research contributes to the initiatives directed toward unbiased decision-making, either automated or algorithm-assisted (which is the case covered by this research). [ABSTRACT FROM AUTHOR]

For any weighted directed path-cycle graphs, a and b (referred to as structures), and any equal costs of operations (intermergings and duplication), we obtain an algorithm which, by successively applying these operations to a, outputs b if the first structure contains no paralogs (i.e., edges with a repeated name) and the second has no more than two paralogs for each edge. In finding the shortest sequence of operations to be applied to pass from a to b, the algorithm has a multiplicative error of at most 13/9 + ε, where ε is any strictly positive number, and its runtime is of the order of n O (ε − 2.6) , where n is the size of the input pair of graphs. In the case of no paralogs, equal sets of names in the structures, and equal operation costs, we have considered the following conditions on the transformation of a into b: all structures in them are from one cycle; all structures are from one path; all structures are from paths. For each of the conditions, we have obtained an exact (i.e., zero-error) quadratic time algorithm for finding the shortest transformation of a into b. For another list of operations (join and cut of a vertex, and deletion and insertion of an edge) over structures and for arbitrary costs of these operations, we have obtained an algorithm for the extension of structures specified at the leaves of a tree onto its interior vertices. The algorithm is exact if the tree is a star—in this case, structures in the leaves may even have unequal sets of names or paralogs. The runtime of the algorithm is of the order of nΧ + n2log(n), where n is the number of names in the leaves, and Χ is an easily computable characteristic of the structures in the leaves. In the general case, a cubic time algorithm finds a locally minimal solution. [ABSTRACT FROM AUTHOR]

We propose a novel linear time algorithm which, given any directed weighted graphs a and b with vertex degrees 1 or 2, constructs a sequence of operations transforming a into b. The total cost of operations in this sequence is minimal among all possible ones or differs from the minimum by an additive constant that depends only on operation costs but not on the graphs themselves; this difference is small as compared to the operation costs and is explicitly computed. We assume that the double cut and join operations have identical costs, and costs of the deletion and insertion operations are arbitrary strictly positive rational numbers. [ABSTRACT FROM AUTHOR]

The ever-increasing complexity of industrial and engineering problems poses nowadays a number of optimization problems characterized by thousands, if not millions, of variables. For instance, very large-scale problems can be found in chemical and material engineering, networked systems, logistics and scheduling. Recently, Deb and Myburgh proposed an evolutionary algorithm capable of handling a scheduling optimization problem with a staggering number of variables: one billion. However, one important limitation of this algorithm is its memory consumption, which is in the order of 120 GB. Here, we follow up on this research by applying to the same problem a GPU-enabled "compact" Genetic Algorithm, i.e., an Estimation of Distribution Algorithm that instead of using an actual population of candidate solutions only requires and adapts a probabilistic model of their distribution in the search space. We also introduce a smart initialization technique and custom operators to guide the search towards feasible solutions. Leveraging the compact optimization concept, we show how such an algorithm can optimize efficiently very large-scale problems with millions of variables, with limited memory and processing power. To complete our analysis, we report the results of the algorithm on very large-scale instances of the OneMax problem. [ABSTRACT FROM AUTHOR]