Search

Identifying the rank of species in a complex ecosystem is a difficult task, since the rank of each species invariably depends on the interactions stipulated with other species through the adjacency matrix of the network. A common ranking method in economic and ecological networks is to sort the nodes such that the layout of the reordered adjacency matrix looks maximally nested with all nonzero entries packed in the upper left corner, called Nestedness Maximization Problem (NMP). Here we solve this problem by defining a suitable cost-energy function for the NMP which reveals the equivalence between the NMP and the Quadratic Assignment Problem, one of the most important combinatorial optimization problems, and use statistical physics techniques to derive a set of self-consistent equations whose fixed point represents the optimal nodes' rankings in an arbitrary bipartite mutualistic network. Concurrently, we present an efficient algorithm to solve the NMP that outperforms state-of-the-art network-based metrics and genetic algorithms. Eventually, our theoretical framework may be easily generalized to study the relationship between ranking and network structure beyond pairwise interactions, e.g. in higher-order networks. Species forming complex ecological or economic ecosystems are organized in hierarchies and the ranks of such species are determined by the adjacency matrix of their interaction network. We introduce a framework to calculate the ranks of species by finding the optimal permutation of rows and columns that makes the adjacency matrix maximally nested. [ABSTRACT FROM AUTHOR]

This document is a special issue of the journal Algorithms, featuring selected papers from the journal's editorial board members from 2022 and 2023. The issue includes 16 research papers covering a range of topics such as game theory, fault detection in cellular networks, optimization algorithms, machine learning, cryptocurrency trading, and more. Each paper presents its own unique research findings and methodologies. The issue aims to showcase the diverse research interests and expertise of the journal's editorial board members. [Extracted from the article]

We analyze a new spectral graph matching algorithm, GRAph Matching by Pairwise eigen-Alignments (GRAMPA), for recovering the latent vertex correspondence between two unlabeled, edge-correlated weighted graphs. Extending the exact recovery guarantees established in a companion paper for Gaussian weights, in this work, we prove the universality of these guarantees for a general correlated Wigner model. In particular, for two Erdős-Rényi graphs with edge correlation coefficient 1 - σ 2 and average degree at least polylog (n) , we show that GRAMPA exactly recovers the latent vertex correspondence with high probability when σ ≲ 1 / polylog (n) . Moreover, we establish a similar guarantee for a variant of GRAMPA, corresponding to a tighter quadratic programming relaxation of the quadratic assignment problem. Our analysis exploits a resolvent representation of the GRAMPA similarity matrix and local laws for the resolvents of sparse Wigner matrices. [ABSTRACT FROM AUTHOR]

Graph matching aims at finding the vertex correspondence between two unlabeled graphs that maximizes the total edge weight correlation. This amounts to solving a computationally intractable quadratic assignment problem. In this paper, we propose a new spectral method, graph matching by pairwise eigen-alignments (GRAMPA). Departing from prior spectral approaches that only compare top eigenvectors, or eigenvectors of the same order, GRAMPA first constructs a similarity matrix as a weighted sum of outer products between all pairs of eigenvectors of the two graphs, with weights given by a Cauchy kernel applied to the separation of the corresponding eigenvalues, then outputs a matching by a simple rounding procedure. The similarity matrix can also be interpreted as the solution to a regularized quadratic programming relaxation of the quadratic assignment problem. For the Gaussian Wigner model in which two complete graphs on n vertices have Gaussian edge weights with correlation coefficient 1 - σ 2 , we show that GRAMPA exactly recovers the correct vertex correspondence with high probability when σ = O (1 log n) . This matches the state of the art of polynomial-time algorithms and significantly improves over existing spectral methods which require σ to be polynomially small in n. The superiority of GRAMPA is also demonstrated on a variety of synthetic and real datasets, in terms of both statistical accuracy and computational efficiency. Universality results, including similar guarantees for dense and sparse Erdős–Rényi graphs, are deferred to a companion paper. [ABSTRACT FROM AUTHOR]

The quadratic assignment problem (QAP) is an NP-hard problem with a wide range of applications in many real-world applications. This study introduces a discrete rat swarm optimizer (DRSO)algorithm for the first time as a solution to the QAP and demonstrates its effectiveness in terms of solution quality and computational efficiency. To address the combinatorial nature of the QAP, a mapping strategy is introduced to convert real values into discrete values, and mathematical operators are redefined to make then suitable for combinatorial problems. Additionally, a solution quality improvement strategy based on local search heuristics such as 2-opt and 3-opt is proposed. Simulations with test instances from the QAPLIB test library validate the effectiveness of the DRSO algorithm, and statistical analysis using the Wilcoxon parametric test confirms its performance. Comparative analysis with other algorithms demonstrates the superior performance of DRSO in terms of solution quality, convergence speed, and deviation from the best-known values, making it a promising approach for solving the QAP. [ABSTRACT FROM AUTHOR]

The performance of optimization algorithms, and consequently of AI/machine learning solutions, is strongly influenced by the setting of their hyperparameters. Over the last decades, a rich literature has developed proposing methods to automatically determine the parameter setting for a problem of interest, aiming at either robust or instance-specific settings. Robust setting optimization is already a mature area of research, while instance-level setting is still in its infancy, with contributions mainly dealing with algorithm selection. The work reported in this paper belongs to the latter category, exploiting the learning and generalization capabilities of artificial neural networks to adapt a general setting generated by state-of-the-art automatic configurators. Our approach differs significantly from analogous ones in the literature, both because we rely on neural systems to suggest the settings, and because we propose a novel learning scheme in which different outputs are proposed for each input, in order to support generalization from examples. The approach was validated on two different algorithms that optimized instances of two different problems. We used an algorithm that is very sensitive to parameter settings, applied to generalized assignment problem instances, and a robust tabu search that is purportedly little sensitive to its settings, applied to quadratic assignment problem instances. The computational results in both cases attest to the effectiveness of the approach, especially when applied to instances that are structurally very different from those previously encountered. [ABSTRACT FROM AUTHOR]

Focusing on the dynamic improvement of the underlying service network configuration, this paper aims to address a specific challenge of redesigning a multi-echelon city logistics distribution network. By considering the intra-echelon connection of facilities within the same layer of echelon, we propose a new distribution network design model by reformulating the classical quadratic assignment problem (QAP). To minimize the overall transportation costs, the proposed model jointly optimizes two types of decisions to enable agile distribution with dynamic "shortcuts": (i) the allocation of warehouses to supply the corresponding distribution centers (DCs), and (ii) the demand coverage decision from distribution centers to delivery stations. Furthermore, a customized branch-and-bound algorithm is developed, where the lower bound is obtained by adopting Gilmore and Lawler lower Bound (GLB) for QAP. We conduct extensive computational experiments, highlighting the significant contribution of GLB-oriented lower bound, to obtain practical solutions; this type of efficient mathematical lower bounds offers a powerful tool for balancing theoretical research ideas with practical and industrial applicability. [ABSTRACT FROM AUTHOR]

Identifying cause-effect relations among variables is a key step in the decision-making process. Whereas causal inference requires randomized experiments, researchers and policy makers are increasingly using observational studies to test causal hypotheses due to the wide availability of data and the infeasibility of experiments. The matching method is the most used technique to make causal inference from observational data. However, the pair assignment process in one-to-one matching creates uncertainty in the inference because of different choices made by the experimenter. Recently, discrete optimization models have been proposed to tackle such uncertainty; however, they produce 0-1 nonlinear problems and lack scalability. In this work, we investigate this emerging data science problem and develop a unique computational framework to solve the robust causal inference test instances from observational data with continuous outcomes. In the proposed framework, we first reformulate the nonlinear binary optimization problems as feasibility problems. By leveraging the structure of the feasibility formulation, we develop greedy schemes that are efficient in solving robust test problems. In many cases, the proposed algorithms achieve a globally optimal solution. We perform experiments on real-world data sets to demonstrate the effectiveness of the proposed algorithms and compare our results with the state-of-the-art solver. Our experiments show that the proposed algorithms significantly outperform the exact method in terms of computation time while achieving the same conclusion for causal tests. Both numerical experiments and complexity analysis demonstrate that the proposed algorithms ensure the scalability required for harnessing the power of big data in the decision-making process. Finally, the proposed framework not only facilitates robust decision making through big-data causal inference, but it can also be utilized in developing efficient algorithms for other nonlinear optimization problems such as quadratic assignment problems. History: Accepted by Ram Ramesh, Area Editor for Data Science and Machine Learning. Funding: This work was supported by the Division of Civil, Mechanical and Manufacturing Innovation of the National Science Foundation [Grant 2047094]. Supplemental Material: The online supplements are available at https://doi.org/10.1287/ijoc.2022.1226. [ABSTRACT FROM AUTHOR]

Graph matching involves combinatorial optimization based on edge-to-edge affinity matrix, which can be generally formulated as Lawler's quadratic assignment problem (QAP). This paper presents a QAP network directly learning with the affinity matrix (equivalently the association graph) whereby the matching problem is translated into a constrained vertex classification task. The association graph is learned by an embedding network for vertex classification, followed by Sinkhorn normalization and a cross-entropy loss for end-to-end learning. We further improve the embedding model on association graph by introducing Sinkhorn based matching-aware constraint, as well as dummy nodes to deal with unequal sizes of graphs. To our best knowledge, this is one of the first network to directly learn with the general Lawler's QAP. In contrast, recent deep matching methods focus on the learning of node/edge features in two graphs respectively. We also show how to extend our network to hypergraph matching, and matching of multiple graphs. Experimental results on both synthetic graphs and real-world images show its effectiveness. For pure QAP tasks on synthetic data and QAPLIB benchmark, our method can perform competitively and even surpass state-of-the-art graph matching and QAP solvers with notable less time cost. We provide a project homepage at http://thinklab.sjtu.edu.cn/project/NGM/index.html. [ABSTRACT FROM AUTHOR]

Ant Colony Optimization is a population metaheuristic inspired by the behavior of natural ants, specifically their ability to find the shortest path between their nest and the food source. This search mechanism has been tested in discrete problems, establishing itself as a good option for this field of application. In previous works, it was shown that dividing the exploration process of these algorithms into 2 stages considerably improves their performance in terms of time and the quality of the results. In this context, we present, in this work, a generalization of the exploitation process by stages for instances of the Medium and High-Dimension of the Traveling Salesman Problem. For the tests, 5 instances of different sizes were selected and 4 variants of the algorithm were analyzed. The results corroborated that the process of division into stages is good for the performance of the algorithm, reaching the best results with 4 stages. [ABSTRACT FROM AUTHOR]

Splitting methods in optimization arise when one can divide an optimization problem into two or more simpler subproblems. They have proven particularly successful for relaxations of problems involving discrete variables. We revisit and strengthen splitting methods for solving doubly nonnegative relaxations of the particularly difficult, NP-hard quadratic assignment problem. We use a modified restricted contractive splitting method approach. In particular, we show how to exploit redundant constraints in the subproblems. Our strengthened bounds exploit these new subproblems and new dual multiplier estimates to improve on the bounds and convergence results in the literature. Summary of Contribution: In our paper, we consider the quadratic assignment problem (QAP). It is one of the fundamental combinatorial optimization problems in the fields of optimization and operations research and includes many fundamental applications. We revisit and strengthen splitting methods for solving doubly nonnegative (DNN) relaxation of the QAP. We use a modified restricted contractive splitting method. We obtain strengthened bounds from improved lower and upper bounding techniques, and in fact, we solve many of these NP-hard problems to (provable) optimality, thus illustrating both the strength of the DNN relaxation and our new bounding techniques. [ABSTRACT FROM AUTHOR]

Migrating birds optimization algorithm is a promising metaheuristic algorithm recently introduced to the optimization community. In this study, we propose a superior version of the migrating birds optimization algorithm by hybridizing it with the simulated annealing algorithm which is one of the most popular metaheuristics. The new algorithm, called MBOx, is compared with the original migrating birds optimization and four well-known metaheuristics, including the simulated annealing, differential evolution, genetic algorithm and recently proposed harris hawks optimization algorithm. The extensive experiments are conducted on problem instances from both discrete and continuous domains; feature selection problem, obstacle neutralization problem, quadratic assignment problem and continuous functions. On problems from discrete domain, MBOx outperforms the original MBO and others by up to 20.99%. On the continuous functions, it is observed that MBOx does not lead the competition but takes the second position. As a result, MBOx provides a significant performance improvement and therefore, it is a promising solver for computational optimization problems. [ABSTRACT FROM AUTHOR]

Our study provides an experimental benchmark for state-of-the-art solution algorithms with hub location problems. Such problems are fundamental optimization problems in location science with widespread application areas, such as transportation, telecommunications, economics, and geography. Given they combine aspects of facility location and quadratic assignment problems, the majority of hub location problems are NP-hard and, accordingly, several solution techniques have been proposed for solving these problems. In this study, we report on the results of a large benchmark and reproduction effort to investigate 12 fundamental hub location problems that combine single or multiple allocation, a p-hub median objective or fixed hub set-up costs, capacitated or uncapacitated hubs, and complete or incomplete networks. We implemented four standard exact algorithms on these 12 problems as proposed in the literature. Algorithms are evaluated on subsets of three standard data sets in the field (CAB, TR, and AP); we computed more than 5,000 optimal solutions for these data sets. We report comparisons of solution techniques regarding wall clock time, convergence speed, memory use, and the impact of data features. In addition, we identify patterns in optimal solutions across these 12 problems, extracting insights regarding solution similarity, hub set candidates, and economies of scale. All results and programs are being made available to the public for free academic use. [ABSTRACT FROM AUTHOR]

Facility layout planning is an indispensable part of the manufacturing and service operations. In the literature, there are two main different approaches for the solution of facility layout problem: While the first one aims to minimize both total transportation and assignment costs in a quantitative way, the second one aims to maximize the closeness relationship in a more qualitative way. In this study, we use both of these approaches to model a multi-objective facility layout optimization problem depending on a Quadratic Assignment Problem (QAP) formulation. We consider three objective which are minimizing the total walking distance, and the maximization of area satisfaction level and closeness relationships. Since these objectives have different scales, we normalize them to prevent a potential domination effect. The n, we solve the problem using Quadratic Assignment Problem (QAP) formulation and a genetic algorithm approach and compare the results. These approaches provide non-dominated solutions to multi-objective problem being considered. In this way, we assign the departments of a healthcare facility to predetermined areas. In addition, our formulation enables the planners to prevent patient losses and increase the patient satisfaction. [ABSTRACT FROM AUTHOR]

We present frequent pattern-based search (FPBS) that combines data mining and optimization. FPBS is a general-purpose method that unifies data mining and optimization within the population-based search framework. The method emphasizes the relevance of a modular- and component-based approach, making it applicable to optimization problems by instantiating the underlying components. To illustrate its potential for solving difficult combinatorial optimization problems, we apply the method to the well-known and challenging quadratic assignment problem. We show the computational results and comparisons on the hardest QAPLIB benchmark instances. This work reinforces the recent trend toward closer cooperations between the optimization methods and machine learning or data mining techniques. [ABSTRACT FROM AUTHOR]

This paper studies the cross-correlation of two real-valued functions whose common domain is a set on which a finite group acts transitively. Such a group action generalizes, e.g., circular time shifts for discrete periodic time signals or spatial translations in the context of image processing. Cross-correlations can be reformulated as convolutions in group algebras and are thus transformable into the spectral domain via Fast Fourier Transforms. The resulting general discrete cross-correlation theorem will serve as the basis for a unified FFT-based approach to maximum assignment problems related to transitive finite group actions. Our main focus is on those assignment problems arising from the actions of symmetric groups on the cosets of Young subgroups. The "simplest" nontrivial representatives of the latter class of problems are the NP-hard symmetric and asymmetric maximum quadratic assignment problem. We present a systematic spectral approach in terms of the representation theory of symmetric groups to solve such assignment problems. This generalizes and algorithmically improves Kondor's spectral branch-and-bound approach (SODA, 2010) to the exact solution of the asymmetric maximum quadratic assignment problem. [ABSTRACT FROM AUTHOR]

This paper deals with the facility layout problem (FLP) in manufacturing systems, the main purpose of the paper is to solve the static facility layout problem as a quadratic assignment problem QAP using approximated approaches. We present Bio-geography Based Optimization meta-heuristic BBO and a parallel hybrid BBO with tabu search PBBO-TS algorithm to solve the facility layout problem. Parallel computing is implemented to diversify the search, to increase the performance of BBO algorithm, and to accelerate the speed of the running time. The proposed approaches were tested on QAPLIB benchmark instances and compared with some of the best performing sequential and parallel algorithms in the literature. The comparisons prove that the proposed algorithm PBBO-TS produce satisfactory results. In addition, the performance of the parallel implementation of the program is studied in terms of speedup and efficiency; the obtained results show that the parallel implemented system is scalable. [ABSTRACT FROM AUTHOR]

We provide several applications of the linearization problem of a binary quadratic problem. We propose a new lower bounding strategy, called the linearization-based scheme, that is based on a simple certificate for a quadratic function to be non-negative on the feasible set. Each linearization-based bound requires a set of linearizable matrices as an input. We prove that the Generalized Gilmore–Lawler bounding scheme for binary quadratic problems provides linearization-based bounds. Moreover, we show that the bound obtained from the first level reformulation linearization technique is also a type of linearization-based bound, which enables us to provide a comparison among mentioned bounds. However, the strongest linearization-based bound is the one that uses the full characterization of the set of linearizable matrices. We also present a polynomial-time algorithm for the linearization problem of the quadratic shortest path problem on directed acyclic graphs. Our algorithm gives a complete characterization of the set of linearizable matrices for the quadratic shortest path problem. [ABSTRACT FROM AUTHOR]

The purpose of this paper is twofold. First, it introduces a new hybrid computational intelligence algorithm to the optimization community. This novel hybrid algorithm has hyperheuristic (HH) neighborhood search movements embedded into a recently introduced migrating birds optimization (MBO) algorithm. Therefore, it is called HHMBO. Second, it gives the necessary mathematical model for a shift scheduling problem of a manufacturing company defined by including the fairness perspective, which is typically ignored especially in manufacturing industry. Therefore, we call this complex optimization problem fairness oriented integrated shift scheduling problem (FOSSP). HHMBO is applied on FOSSP and is compared with the well-known simulated annealing, hyperheuristics, and classical MBO algorithms through extended computational experiments on several synthetic datasets. Experiments demonstrate that the new hybrid computational intelligence algorithm is promising especially for large sized instances of the specific problem defined here. HHMBO has a high exploration capability and is a promising technique for all optimization problems. To justify this assertion, we applied HHMBO to the well-known quadratic assignment problem (QAP) instances from the QAPLIB. HHMBO was up to 14.6% better than MBO on converging to the best known solutions for QAP benchmark instances with different densities. We believe that the novel hybrid method and the fairness oriented model presented in this study will give new insights to the decision-makers in the industry as well as to the researchers from several disciplines. [ABSTRACT FROM AUTHOR]

In this paper, we study the quadratic assignment problem with a rank-one cost matrix (QAP-R1). Four integer-programming formulations are introduced of which three are assumed to have partial integer data. Unlike the standard quadratic assignment problem, some of our formulations can solve reasonably large instances of QAP-R1 with impressive running times and are faster than some metaheuristics. Pairwise relative strength of the LP relaxations of these formulations are also analyzed from theoretical and experimental points of view. Finally, we present a new metaheuristic algorithm to solve QAP-R1 along with its computational analysis. Our study offers the first systematic experimental analysis of integer-programming models and heuristics for QAP-R1. The benchmark instances with various characteristics generated for our study are made available to the public for future research work. Some new polynomially solvable special cases are also introduced. Summary of Contribution: This paper aims to advance our knowledge and ability in solving an important special case of the quadratic assignment problem. It shows how to exploit inherent properties of an optimization problem to achieve computational advantages, a strategy that was followed by researchers in model building and algorithm developments for decades. Our computational results attest to this time-tested general philosophy. The paper presents the first systematic computational study of the rank one quadratic assignment problem, along with new mathematical programming models and complexity analysis. We believe the theoretical and computational results of this paper will inspire further research on the topic and will be of significant value to practitioners using rank one quadratic assignment models. [ABSTRACT FROM AUTHOR]

This letter considers the robust design of radar waveform with discrete phase codes under constant modulus constraint to enhance target detectability. To solve the resultant max‐min non‐convex optimization problem, a robust discrete phase coding algorithm via iterative technology (R‐DPCA‐IT) is developed which monotonically improves the worst‐case SNR and has an upper bound ensuring to converge a finite value. At each iteration, the original multidimensional quadratic optimization problem is turned into multiple one‐dimensional optimization problems solved globally via line search. Finally, the computational time and objective value of the proposed algorithm are assessed in comparison with the existing methods. [ABSTRACT FROM AUTHOR]

The facility layout problem (FLP) is a very important class of NP-hard problems in operations research that deals with the optimal assignment of facilities to minimize transportation costs. The quadratic assignment problem (QAP) can model the FLP effectively. One of the FLPs is the hospital facility layout problem that aims to place comprehensive clinics, laboratories, and radiology units within predefined boundaries in a way that minimizes the cost of movement of patients and healthcare personnel. We are going to develop a hybrid method based on discrete differential evolution (DDE) algorithm for solving the QAP. In the existing DDE algorithms, certain issues such as premature convergence, stagnation, and exploitation mechanism have not been properly addressed. In this study, we first aim to discover the issues that make the current problem worse and to identify the best solution to the problem, and then we propose to develop a hybrid algorithm (HDDETS) by combining the DDE and tabu search (TS) algorithms to enhance the exploitation mechanism in the DDE algorithm. Then, the performance of the proposed HDDETS algorithm is evaluated by implementing on the benchmark instances from the QAPLIB website and by comparing with DDE and TS algorithms on the benchmark instances. It is found that the HDDETS algorithm has better performance than both the DDE and TS algorithms where the HDDETS has obtained 42 optimal and best-known solutions from 56 instances, while the DDE and TS algorithms have obtained 15 and 18 optimal and best-known solutions out of 56 instances, respectively. Finally, we propose to apply the proposed algorithm to find the optimal distributions of the advisory clinics inside the Azadi Hospital in Iraq that minimizes the total travel distance for patients when they move among these clinics. Our application shows that the proposed algorithm could find the best distribution of the hospital's rooms, which are modeled as a QAP, with reduced total distance traveled by the patients. [ABSTRACT FROM AUTHOR]

The facility layout problem (FLP) is a very important class of NP-hard problems in operations research that deals with the optimal assignment of facilities to minimize transportation costs. The quadratic assignment problem (QAP) can model the FLP effectively. One of the FLPs is the hospital facility layout problem that aims to place comprehensive clinics, laboratories, and radiology units within predefined boundaries in a way that minimizes the cost of movement of patients and healthcare personnel. We are going to develop a hybrid method based on discrete differential evolution (DDE) algorithm for solving the QAP. In the existing DDE algorithms, certain issues such as premature convergence, stagnation, and exploitation mechanism have not been properly addressed. In this study, we first aim to discover the issues that make the current problem worse and to identify the best solution to the problem, and then we propose to develop a hybrid algorithm (HDDETS) by combining the DDE and tabu search (TS) algorithms to enhance the exploitation mechanism in the DDE algorithm. Then, the performance of the proposed HDDETS algorithm is evaluated by implementing on the benchmark instances from the QAPLIB website and by comparing with DDE and TS algorithms on the benchmark instances. It is found that the HDDETS algorithm has better performance than both the DDE and TS algorithms where the HDDETS has obtained 42 optimal and best-known solutions from 56 instances, while the DDE and TS algorithms have obtained 15 and 18 optimal and best-known solutions out of 56 instances, respectively. Finally, we propose to apply the proposed algorithm to find the optimal distributions of the advisory clinics inside the Azadi Hospital in Iraq that minimizes the total travel distance for patients when they move among these clinics. Our application shows that the proposed algorithm could find the best distribution of the hospital's rooms, which are modeled as a QAP, with reduced total distance traveled by the patients. [ABSTRACT FROM AUTHOR]

As the distributed computing systems have been widely used in many research and industrial areas, the problem of allocating tasks to available processors in the system efficiently has been an important concern. Since the problem is proven to be NP-hard, heuristic-based optimization techniques have been proposed to solve the task allocation problem. Particularly, the current cloud-based systems have been grown massively requiring multiple features like lower cost, higher reliability, and higher throughput; therefore, the problem has become more challenging and approximate methods have gained more importance. Migrating birds optimization (MBO) algorithm offers successful solutions, especially for quadratic assignment problems. Inspired by the movement of the birds, it exhibits good results by its population-based approach. Since the algorithm needs to deal with many individuals in the population, and the neighbor solution generation phase takes substantial time for large problem instances, we need parallelism to have execution time improvements and make the algorithm practical for large-scale problems. In this work, we propose a scalable parallel implementation of the MBO algorithm, PMBO, for the multi-objective task allocation problem. We redesigned the implementation of the MBO algorithm so that its computationally heavy independent tasks are executed concurrently in separate threads. We compare our implementation with three parallel island-based approaches. The experimental results demonstrate that our implementation exhibits substantial solution quality improvements for difficult problem instances as the computing resources, namely parallelism, increase. Our scalability analysis also presents that higher parallelism levels offer larger solution improvement for the PMBO over the island-based parallel implementations on very hard problem instances. [ABSTRACT FROM AUTHOR]

Operations Research (OR) analytics play a crucial role in optimizing decision-making processes for real-world problems. The assignment problem, with applications in supply chains, healthcare logistics, and production scheduling, represents a prominent optimization challenge. This paper focuses on addressing the Generalized Quadratic Assignment Problem (GQAP), a well-known NP-hard combinatorial optimization problem. To tackle the GQAP, we propose an OR analytical approach that incorporates efficient relaxations, reformulations, heuristics, and a metaheuristic algorithm. Initially, we employ the Reformulation Linearization Technique (RLT) to generate various linear relaxation models, carefully selecting the most efficient ones. Building upon this foundation, we introduce a robust reformulation based on Benders Decomposition (BD), which serves as the basis for an iterative optimization algorithm applied to the GQAP. Furthermore, we develop a constructive heuristic algorithm to identify near-optimal solutions, followed by an enhancement utilizing an Adaptive Large Neighborhood Search (ALNS) metaheuristic algorithm. This ALNS algorithm is enhanced through the integration of a tabu list derived from Tabu Search (TS) and a decision rule inspired by Simulated Annealing (SA). To validate our approach and evaluate its performance, we conduct a comparative analysis against state-of-the-art algorithms documented in the literature. This comparison confirms the significant improvements achieved in terms of solution quality and computational efficiency through our proposed methodology. These advancements contribute to the state of the art in solving the GQAP and hold the potential to enhance decision-making processes in a wide range of domains. Our methodology demonstrates remarkable improvements in solution quality and computational efficiency when compared to existing approaches, as evidenced by the comparative results with state-of-the-art algorithms. The potential implications of our research extend to optimizing decision-making processes in diverse fields, rendering it highly relevant and impactful. • Analyzing different reformulation linearization inequalities for the GQA. • Introducing a novel Benders decomposition reformulation method for the GQAP. • Developing a new constructive heuristic algorithm for the initial solution of the GQAP. • Proposing different removal–insertion​ heuristics and a local search using a tabu list. • Introducing an efficient adaptive large neighborhood search algorithm for solving the GQAP. [ABSTRACT FROM AUTHOR]

Graph matching is an important and persistent problem in computer vision and pattern recognition for finding node-to-node correspondence between graphs. However, graph matching that incorporates pairwise constraints can be formulated as a quadratic assignment problem (QAP), which is NP-complete and results in intrinsic computational difficulties. This paper presents a functional representation for graph matching (FRGM) that aims to provide more geometric insights on the problem and reduce the space and time complexities. To achieve these goals, we represent each graph by a linear function space equipped with a functional such as inner product or metric, that has an explicit geometric meaning. Consequently, the correspondence matrix between graphs can be represented as a linear representation map. Furthermore, this map can be reformulated as a new parameterization for matching graphs in Euclidean space such that it is consistent with graphs under rigid or nonrigid deformations. This allows us to estimate the correspondence matrix and geometric deformations simultaneously. We use the representation of edge-attributes rather than the affinity matrix to reduce the space complexity and propose an efficient optimization strategy to reduce the time complexity. The experimental results on both synthetic and real-world datasets show that the FRGM can achieve state-of-the-art performance. [ABSTRACT FROM AUTHOR]

The bilinear assignment problem (BAP) is a generalization of the well-known quadratic assignment problem. In this paper, we study the problem from the computational analysis point of view. Several classes of neighborhood structures are introduced for the problem along with some theoretical analysis. These neighborhoods are then explored within a local search and variable neighborhood search frameworks with multistart to generate robust heuristic algorithms. In addition, we present several very fast construction heuristics. Our systematic experimental analysis disclosed some interesting properties of the BAP, different from those of comparable models. We have also introduced benchmark test instances that can be used for future experiments on exact and heuristic algorithms for the problem. [ABSTRACT FROM AUTHOR]

The firefly algorithm (FA) is a swarm intelligence optimization algorithm based on the glow behavior of fireflies in nature. The classic firefly algorithm has the problem that it is easy to fall into the local optimum and the search accuracy is not high in the later stage. An improved firefly algorithm based on chaos mapping strategy was proposed to solve the quadratic assignment problem (QAP). The egocentricity of chaos just avoids the firefly algorithm from falling into the local optimum, enhances its search ability and solves the convergence prematurely phenomenon of the firefly algorithm. The improved algorithm is compared with genetic algorithm (GA), particle swarm optimization (PSO) algorithm and the classic firefly algorithm to solve the same quadratic assignment problems. The simulation experiments results verify the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper we suggest a new rule for parent selection in genetic algorithms inspired by natural evolutionary processes. The new rule is simple to implement in any genetic or hybrid genetic algorithm. We also review some biological principles that inspire genetic algorithms and their extensions. The new rule is tested on the planar p-median problem, also termed the location–allocation problem or the multi-source Weber problem, and the quadratic assignment problem. The genetic algorithm incorporating the new rule provided better results without increasing the computing time including five new best known solutions to well researched problem instances. [ABSTRACT FROM AUTHOR]

The Reformulation Linearization Technique (RLT) of Sherali and Adams (Manag Sci 32(10):1274–1290, 1986; SIAM J Discrete Math 3(3):411–430, 1990), when applied to a pure 0–1 quadratic optimization problem with linear constraints (P), constructs a hierarchy of LP (i.e., continuous and linear) models of increasing sizes. These provide monotonically improving continuous bounds on the optimal value of (P) as the level, i.e., the stage in the process, increases. When the level reaches the dimension of the original solution space, the last model provides an LP bound equal to the IP optimum. In practice, unfortunately, the problem size increases so rapidly that for large instances, even computing bounds for RLT models of level k (called RLTk) for small k may be challenging. Their size and their complexity increase drastically with k. To our knowledge, only results for bounds of levels 1, 2, and 3 have been reported in the literature. We are proposing, for certain quadratic problem types, a way of producing stronger bounds than continuous RLT1 bounds in a fraction of the time it would take to compute continuous RLT2 bounds. The approach consists in applying a specific decomposable Lagrangean relaxation to a specially constructed RLT1-type linear 0–1 model. If the overall Lagrangean problem does not have the integrality property, and if it can be solved as a 0–1 rather than a continuous problem, one may be able to obtain 0–1 RLT1 bounds of roughly the same quality as standard continuous RLT2 bounds, but in a fraction of the time and with much smaller storage requirements. If one actually decomposes the Lagrangean relaxation model, this two-step procedure, reformulation plus decomposed Lagrangean relaxation, will produce linear 0–1 Lagrangean subproblems with a dimension no larger than that of the original model. We first present numerical results for the Crossdock Door Assignment Problem, a special case of the Generalized Quadratic Assignment Problem. These show that just solving one Lagrangean relaxation problem in 0–1 variables produces a bound close to or better than the standard continuous RLT2 bound (when available) but much faster, especially for larger instances, even if one does not actually decompose the Lagrangean problem. We then present numerical results for the 0–1 quadratic knapsack problem, for which no RLT2 bounds are available to our knowledge, but we show that solving an initial Lagrangean relaxation of a specific 0–1 RLT1 decomposable model drastically improves the quality of the bounds. In both cases, solving the fully decomposed rather than the decomposable Lagrangean problem to optimality will make it feasible to compute such bounds for instances much too large for computing the standard continuous RLT2 bounds. [ABSTRACT FROM AUTHOR]

Meta-heuristics perform differently depending on the problem instance they are solving, meaning that manually choosing an algorithm is not trivial and an automatic selection is desirable. This task can be addressed using a meta-learning approach, which relates the characteristics of the problem instances to the performance of a set of solving algorithms. Therefore, the success of such approach is based on the quality of the extracted set of features. Some studies have proposed the use of features based on Fitness Landscape Analysis (FLA) to characterize optimization problems. However, extracting measures based on FLA usually requires a high computational effort. In a previous work, we have employed meta-heuristic selection on the Quadratic Assignment Problem (QAP) using some FLA measures. This research extends our study by including additional FLA meta-features, by using a less costly extraction method, and by considering more QAP instances. In total, we built five multi-label datasets, each composed of meta-features that were extracted by different sampling sizes, and then we used them to train Random Forest classifiers. Besides presenting satisfactory classification performance, and a decrease in time consumption in relation to our previous work, this selection approach was able to achieve better solution costs over the set of QAP instances if compared to running the meta-heuristics individually. [ABSTRACT FROM AUTHOR]

In this paper we discuss the problem of locating items within carousel bins in order to minimize the average carousel rotational distance per retrieval. We consider two cases: (1) a single two-dimensional carousel and (2) a group of two one-dimensional carousels. The corresponding problems are formulated as mixed-integer programs. In the second problem we apply concepts from Markovian performance evaluation methods to write the objective functions in a simple linear form. We also define a set of uniqueness constraints that significantly reduces the size of the solution feasibility space. We then apply Benders decomposition algorithm to solve both problems. We develop a closed form solution for the dual subprobem and present numerical results to show the efficiency of the proposed solution methodology. [ABSTRACT FROM AUTHOR]

This paper discusses efficient parallel algorithms for obtaining strong lower bounds and exact solutions for large instances of the quadratic assignment problem (QAP). Our parallel architecture is comprised of both multicore processors and compute unified device architecture–enabled NVIDIA graphics processing units (GPUs) on the Blue Waters Supercomputing Facility at the University of Illinois at Urbana–Champaign. We propose novel parallelization of the Lagrangian dual ascent algorithm on the GPUs, which is used for solving a QAP formulation based on the level-2 reformulation linearization technique. The linear assignment subproblems in this procedure are solved using our accelerated Hungarian algorithm [Date K, Rakesh N (2016) GPU-accelerated Hungarian algorithms for the linear assignment problem. Parallel Computing 57:52–72.]. We embed this accelerated dual-ascent algorithm in a parallel branch-and-bound scheme and conduct extensive computational experiments on single and multiple GPUs, using problem instances with up to 42 facilities from the quadratic assignment problem library (QAPLIB). The experiments suggest that our GPU-based approach is scalable, and it can be used to obtain tight lower bounds on large QAP instances. Our accelerated branch-and-bound scheme is able to comfortably solve Nugent and Taillard instances (up to 30 facilities) from the QAPLIB, using a modest number of GPUs. [ABSTRACT FROM AUTHOR]

Abstract With the rapid growth of the Chinese economy, environmental pollution from traditional resource endowments and extensive economic development is becoming an increasingly prominent problem. Research into the present pollution control situation is thus relevant to adjusting pollution control methods and improving pollution control effects. However, pollution control has the externality characteristics of a public good, creating a problem of spatial association. This paper used the social network analysis method to analyse this problem. First, a spatial association network of provincial pollution control in China was established based on a gravitation model, and the structural characteristics of this spatial association network were analysed. Then, the quadratic assignment procedure (QAP) analysis method was employed to explore the main influencing factors impacting the association intensity of this spatial association network. These results contribute by illustrating the current situation of Chinese pollution control and provide a theoretical foundation for the government when it formulates future development directions and policies. [ABSTRACT FROM AUTHOR]

We consider the assignment problem with a special structure with a general form value function and constraints prohibiting certain matchings. In this case, the matching cost may be undefined until some permutation is found. We formulate the problem in terms of graph theory and reduce it to finding a minimal cost path in a graph with nonlocal edge weights. The proposed method for solving the problem is a modification of the Dijkstra's shortest path algorithm in a weighted directed graph. This research is motivated by well drilling applications. We also show the analysis of our numerical experiments. [ABSTRACT FROM AUTHOR]

Music listening is an inherently cultural behavior, which may be shaped by users’ backgrounds and contextual characteristics. Due to geographical, socio-economic, linguistic, and cultural factors as well as friendship networks, users in different countries may have different music preferences. Investigating cultural-socio-economic factors that might be associated with between-country differences in music preferences can facilitate music information retrieval, contribute to the prediction of users’ music preferences, and improve music recommendation in cross-country contexts. However, previous literature provides limited empirical evidence of the relationships between possible cross-country differences on a wide range of socio-economic aspects and those in music preferences. To bridge this research gap, and drawing on a large-scale dataset, LFM-1b, this study examines the possible relationship between cross-country differences in artist, album, and genre listening frequencies as well as the cross-country distance in geographical, socio-economic, linguistic, cultural, and friendship connections using the Quadratic Assignment Procedure. Results indicate: (1) there is no significant relationship between geographical and economic distance on album, artist, and genre preferences’ distance at the country-level; (2) the cross-country distance of three cultural dimensions (masculinity, long-term orientation, and indulgence) is positively associated with both the album and artist preferences distances; (3) the between-country distance in main languages has a positive relationship with the album, artist, and genre preferences distances across countries; (4) the density of friendship connections among countries negatively correlates to the cross-country preference distances in terms of artist and genre. Findings from this study not only expand knowledge of factors related to music preferences at the country level, but also can be integrated into real-world music recommendation systems that consider country-level music preferences. [ABSTRACT FROM AUTHOR]

This paper introduces a Multi-Agent based Optimization Method for Combinatorial Optimization Problems named MAOM-COP. In this method, a set of agents are cooperatively interacting to select the appropriate operators of metaheuristics using learning techniques. MAOM-COP is a flexible architecture, whose objective is to produce more generally applicable search methodologies. In this paper, the MAOM-COP explores genetic algorithm and local search metaheuristics. Using these metaheuristics, the decision-maker agent, the intensification agents and the diversification agents are seeking to improve the search. The diversification agents can be divided into the perturbation agent and the crossover agents. The decision-maker agent decides dynamically which agent to activate between intensification agents and crossover agents within reinforcement learning. If the intensification agents are activated, they apply local search algorithms. During their searches, they can exchange information, as they can trigger the perturbation agent. If the crossover agents are activated, they perform recombination operations. We applied the MAOM-COP to the following problems: quadratic assignment, graph coloring, winner determination and multidimensional knapsack. MAOMCOP shows competitive performances compared with the approaches of the literature. [ABSTRACT FROM AUTHOR]

Crossover operators play a very important role by creation of genetic algorithms (GAs) which are applied in various areas of computer science, including combinatorial optimization. In this paper, fifteen genetic crossover procedures are designed and implemented using a modern C# programming language. The computational experiments have been conducted with these operators by solving the famous combinatorial optimization problem - the quadratic assignment problem (QAP). The results of the conducted experiments on the characteristic benchmark instances from the QAP instances library QAPLIB illustrate the relative performance of the examined crossover operations. All crossover procedures are publicly available with the intention that the GA researchers will choose a procedure which suits the individual demand at the highest degree. [ABSTRACT FROM AUTHOR]

Quadratic assignment problem (QAP) is one of the most difficult combinatorial optimization problems in the NP-hard class. Due to the difficulty of the problem, many researchers have been studying this type of assignment problem. In this work, simulated annealing method is parallelized on MATLAB platform and is used to solve 36 problems from QAPLIB which is a well-known QAP library. The performance of different parallelization methods is compared for the problems used. As a result, when compared with the serial simulated annealing method, it is seen that the parallel methods give faster results when the appropriate parameters are used. [ABSTRACT FROM AUTHOR]

This paper presents a new local search approach, called randomized decomposition (RD), for solving nonlinear, nonconvex mathematical programs. Starting from a feasible solution, RD partitions the problem's decision variables into a randomly ordered list of randomly generated subsets. RD then optimizes over the variables in each subset, keeping all other variables fixed. Unlike most other decomposition methods, no knowledge of the problem structure is required. RD has been combined with a metaheuristic RDPerturb, for escaping local optima, to create a generic framework for solving mathematical programs, especially hard combinatorial nonconvex problems. The framework has been implemented as an optimization platform we call RDSolver and successfully applied to over 400 instances of the quadratic assignment problem (QAP). The results obtained by RDSolver are competitive with the solutions obtained by heuristics specially tailored for those problems, even though RDSolver is a general purpose mathematical programming solver. In addition to a strong performance on previously solved problems, RDSolver has found two new best known solutions and provided solutions to 68 large QAP problems for which no solutions have been previously reported. [ABSTRACT FROM AUTHOR]

In the classical Travelling Salesman Problem (TSP), the objective function sums the costs for travelling from one city to the next city along the tour. In the q-stripe TSP with $$q\ge 1$$ , the objective function sums the costs for travelling from one city to each of the next q cities in the tour. The resulting q-stripe TSP generalizes the TSP and forms a special case of the quadratic assignment problem. We analyze the computational complexity of the q-stripe TSP for various classes of specially structured distance matrices. We derive NP-hardness results as well as polynomially solvable cases. One of our main results generalizes a well-known theorem of Kalmanson from the classical TSP to the q-stripe TSP. [ABSTRACT FROM AUTHOR]

This paper presents an application of the ant algorithm and bees algorithm in optimization of QAP problem as an example of NPhard optimization problem. The experiments with two types of algorithms: the bees algorithm and the ant algorithm were performed for the test instances of the quadratic assignment problem from QAPLIB, designed by Burkard, Karisch and Rendl. On the basis of the experiments results, an influence of particular elements of algorithms, including neighbourhood size and neighbourhood search method, will be determined. [ABSTRACT FROM AUTHOR]

With this study, we propose a novel parallel robust tabu-search algorithm (Parallel-Tabu-QAP) for the NP-Hard Quadratic Assignment Problem (QAP)of whose instances having large number of location and facilites have not been reported to be solved exactly so far. Parallel- Tabu-QAP algorithm that has two phases optimizes the parameters of tabu-search algorithm in its first phase by using genetic algorithms through generations. The individuals that have parameters of the tabu-search are optimized in a population that is located on a master processor. In the second phase, slave processors optimize the solution of the problem by restarting their search process in case of stagnations. With its stagnation prevention and parallel optimization talents, parallel-tabu-QAP algorithm is observed to obtain better results than its sequential and statically parameter-tuned counterparts. The algorithm has 0.05% deviation for the benchmark tests performed on more than 100 problem instances. These experimental results show that the parallel-tabu-QAP algoritm is one the best performing techniques in its heuristics algorithms class when compared with state-of-the-art QAP algorithms. [ABSTRACT FROM AUTHOR]

In this study, we propose a novel hybrid multiobjective evolutionary algorithm for solving multiobjective quadratic assignment problems. During the last decade, the researchers gave increasing attention to the multiobjective structure of quadratic assignment problems and developed and/or used several multi objective metaheuristics. The nondominated sorting genetic algorithm (NSGA-II) has been shown to solve various multiobjective problems much better than other recently-proposed constraint handling approaches. Besides, the effectiveness of conic scalarization method was also proven for solution of multiobjective problems, that have non-linear structure. Here, a hybrid multiobjective evolutionary algorithm (cNSGA-II) featured with NSGA-II and conic scalarization's Pareto solutions is developed to obtain as much Pareto points, as possible. To test the performance of the algorithm we have selected the test problems from the literature and compared the performances by well-known diameter metric. It has been shown that cNSGA-II is effective in solving multiobjective quadratic assignment problems. [ABSTRACT FROM AUTHOR]

Allocating tasks to processors is a well-known NP-Hard problem in distributed computing systems. Due to the lack of practicable exact solutions, it has been attracted by the researchers working on heuristic-based suboptimal search algorithms. With the recent inclusion of multiple objectives such as minimizing the cost, maximizing the throughput and maximizing the reliability, the problem gets even more complex and an efficient approximate method becomes more valuable. In this work, I propose a new solution for the multi-objective task allocation problem. My solution consists in designing a problem-specific neighboring function for an existing metaheuristic algorithm that is proven to be successful in quadratic assignment problems. The neighboring function, namely greedy reassignment with maximum release (GR-MR), provides a dynamic mechanism to switch the preference of the search between the exploration and exploitation. The experiments validate both that the quality of the solutions are close to the optimal and the proposed method performs significantly better comparing to three other metaheuristic algorithms. Neighboring functions being the common reusable components of metaheuristic algorithms, GR-MR can also be utilized by other metaheuristic-based solutions in the future. [ABSTRACT FROM AUTHOR]

In genetic algorithms crossover is the most important operator where pair of chromosomes and crossover site along their common length are selected randomly. Then the information after the crossover site of the parent chromosomes is swapped. On the other hand, mutation operator randomly alters some genes of a chromosome, and thus diversifies the search space. We consider three crossover and ten mutation operators for the genetic algorithms which are then compared for the quadratic assignment problem on some benchmark QAPLIB instances. The experimental study shows the effectiveness of the sequential constructive crossover and the adaptive mutation operators for the problem. [ABSTRACT FROM AUTHOR]

Graph matching (GM) is a fundamental problem in computer science, and it plays a central role to solve correspondence problems in computer vision. GM problems that incorporate pairwise constraints can be formulated as a quadratic assignment problem (QAP). Although widely used, solving the correspondence problem through GM has two main limitations: (1) the QAP is NP-hard and difficult to approximate; (2) GM algorithms do not incorporate geometric constraints between nodes that are natural in computer vision problems. To address aforementioned problems, this paper proposes factorized graph matching (FGM). FGM factorizes the large pairwise affinity matrix into smaller matrices that encode the local structure of each graph and the pairwise affinity between edges. Four are the benefits that follow from this factorization: (1) There is no need to compute the costly (in space and time) pairwise affinity matrix; (2) The factorization allows the use of a path-following optimization algorithm, that leads to improved optimization strategies and matching performance; (3) Given the factorization, it becomes straight-forward to incorporate geometric transformations (rigid and non-rigid) to the GM problem. (4) Using a matrix formulation for the GM problem and the factorization, it is easy to reveal commonalities and differences between different GM methods. The factorization also provides a clean connection with other matching algorithms such as iterative closest point; Experimental results on synthetic and real databases illustrate how FGM outperforms state-of-the-art algorithms for GM. The code is available at http://humansensing.cs.cmu.edu/fgm. [ABSTRACT FROM AUTHOR]

This paper presents a novel range division and contraction approach for globally solving nonconvex quadratic program with quadratic constraints. By constructing new underestimating linear relaxation functions, we can transform the initial nonconvex quadratic program problem into a linear program relaxation problem. By employing a branch and bound scheme with a range contraction approach, we describe a novel global optimization algorithm for effectively solving nonconvex quadratic program with quadratic constraints. Finally, the global convergence of the proposed algorithm is proved and numerical experimental results demonstrate the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]