Search

Lithium has broad applications in several emerging industries and fields, including high energy batteries, energy storage, aerospace, and controlled nuclear reactions. Currently, the discrepancy between the supply and demand for lithium resources increases, and its distribution is uneven. Within the framework of the "Belt and Road" Initiative, the lithium trade pattern evolves constantly. However, the trade pattern of lithium in the nations along the "Belt and Road" is likely to face substantial repercussions in modern world of unilateral protectionism and geopolitical conflicts. Taking the social network analysis approach as a tool, this study first examines the characteristics of the lithium trade network structure as it has evolved over the years in the Belt and Road countries, from 2000 to 2022. Additionally, this study uses the quadratic assignment problem approach to analyze the factors influencing the evolution of the lithium trade network. The study shows that: (1) The spatial patterns of import and export trade network of lithium in countries along the route has a certain path dependence. And the market is mainly concentrated in East Asia, Central and Eastern Europe, South America and Southeast Asia. (2) The network density of the countries along the route has increased year after year, but it remains low. And the fluctuation of the network's reciprocity has increased, with a huge magnitude of variation. The number of core countries in the network has decreased over time, but the core-periphery structure has stayed largely steady. China, Chile, and South Korea are the network's main node countries. (3) Regarding the influencing factors, the differences in economic and technological development between these countries have a beneficial impact on the formation of lithium trade; whether or not regional trade agreements have been signed, the differences about average tax rates for mineral products, bordering countries, and similar languages and cultures are all conducive to the establishment of close trade links. The contribution of this essay is of paramount importance for understanding different countries' role along the Belt and Road in the lithium trade network pattern, and promoting regional trade cooperation. [ABSTRACT FROM AUTHOR]

Population-based meta-heuristic optimization algorithms play a vital role in addressing optimization problems. Nowadays, exponential distribution optimizer (EDO) can be considered to be one of the most recent among these algorithms. Although it has achieved many promising results, it has a set of shortcomings, for example, the decelerated convergence, and provides local optima solution as it cannot escape from local regions in addition to imbalance between diversification and intensification. Therefore, in this study, an enhanced variant of EDO called mEDO was proposed to address these shortcomings by combining two efficient search mechanisms named orthogonal learning (OL) and local escaping operator (LEO). In mEDO, the LEO has been exploited to escape local optima and improve the convergence behavior of the EDO by employing random operators to maximize the search process and to effectively discover the globally optima solution. Then the OL has been combined to keep the two phases (i.e., exploration and exploitation) balanced. To validate the effectiveness and performance of the mEDO algorithm, the proposed method has been evaluated over ten functions of the IEEE CEC'2020 test suite as well as eight real-world applications (engineering design optimization problems), Furthermore we test the applicability of the proposed algorithm by tackling 21 instance of the quadratic assignment problem (QAP). The experimental and statistical results of the proposed algorithm have been compared against seven other common metaheuristic algorithms (MAs), including the basic EDO. The results show the supremacy of the mEDO algorithm over the other algorithms and reveal the applicability and effectiveness of the mEDO algorithm compared to well-established metaheuristic algorithms. The experimental results and different statistical measures revealed the reliability and applicability of the mEDO method in solving the global, engineering design, and combinatorial optimization problems by achieving a reasonable solution in terms of scoring a global optima solutions and avoiding premature convergence by increasing the population's diversity. [ABSTRACT FROM AUTHOR]

A primal quadratic simplex algorithm tailored to the optimization over the vertices of a polytope is presented. Starting from a feasible vertex, it performs either strictly improving or admissible non-deteriorating steps in order to determine a locally optimum basic feasible solution in terms of the quadratic objective function. The algorithm so generalizes over local improvement methods for according applications, including in particular quadratic optimization problems whose feasible solutions correspond to vertices of a 0-1 polytope. Computational experiments for unconstrained binary quadratic programs, maximum cut, and the quadratic assignment problem serve as a proof of concept and underline the importance of a pivoting rule that is able to accept at least a restricted class of degenerate steps. [ABSTRACT FROM AUTHOR]

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]

It is well known that by adding integrality constraints to the semidefinite programming (SDP) relaxation of the max-cut problem, the resulting integer semidefinite program is an exact formulation of the problem. In this paper we show similar results for a wide variety of discrete optimization problems for which SDP relaxations have been derived. Based on a comprehensive study on discrete positive semidefinite matrices, we introduce a generic approach to derive mixed-integer SDP (MISDP) formulations of binary quadratically constrained quadratic programs and binary quadratic matrix programs. Applying a problem-specific approach, we derive more compact MISDP formulations of several problems, such as the quadratic assignment problem, the graph partition problem, and the integer matrix completion problem. We also show that several structured problems allow for novel compact MISDP formulations through the notion of association schemes. Complementary to the recent advances on algorithmic aspects related to MISDP, this work opens new perspectives on solution approaches for the here considered problems. [ABSTRACT FROM AUTHOR]

This paper proposes a new approach for solving dynamic facility layout problems (DFLP) using a genetic algorithm (GA) enhanced with machine learning techniques, namely clustering algorithms. The proposed course aims to design a robust layout that can adapt to changes in the input parameters. Traditionally, the DFLPs are solved using adaptive methods, i.e., the layout from period to period varies. However, in the robust approach, the layout remains the same throughout the different planning periods. The GA is used for generating the solutions, and the machine learning technique is used to cluster the solutions and select the candidate solution to undergo the local search procedure. The proposed approach is tested on a set of benchmark instances and compared with published approaches. The results show that the proposed approach outperforms the existing approaches in terms of solution quality, robustness, and computational efficiency. [ABSTRACT FROM AUTHOR]

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]

Comparing combinatorial optimization problems is a difficult task. They are defined using different criteria and terms: weights, flows, distances, etc. In spite of this apparent discrepancy, on many occasions, they tend to produce problem instances with similar properties. One avenue to compare different problems is to project them onto the same space, in order to have homogeneous representations. Expressing the problems in a unified framework could also lead to the discovery of theoretical properties or the design of new algorithms. This article proposes the use of the Fourier transform over the symmetric group as the tool to project different permutation-based combinatorial optimization problems onto the same space. Based on a previous study (Kondor, 2010), which characterized the Fourier coefficients of the quadratic assignment problem, we describe the Fourier coefficients of three other well-known problems: the symmetric and nonsymmetric traveling salesperson problem and the linear ordering problem. This transformation allows us to gain a better understanding of the intersection between the problems, as well as to bound their intrinsic dimension. [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]

A new method is proposed for robust partial quadratic eigenvalue assignment problem (RPQEAP) with repeated prescribed eigenvalues. We first derive a result on the solution of partial quadratic eigenvalue assignment problem, which leads to the partial Schur form of the closed-loop system. Then by minimizing the normality departure of the partial Schur form of the closed-loop system, we assign the prescribed eigenvalues step by step such that the closed-loop system is as robust as possible. Our method allows the prescribed eigenvalues are repeated. Moreover, the proposed method does not use the unchanged eigenpairs of the open-loop system and avoids transforming the second-order control system to the first-order system. Numerical experiments show that the proposed method is efficient for solving the RPQEAP with repeated eigenvalues. [ABSTRACT FROM AUTHOR]

Harris Hawk optimization (HHO) is a new robust metaheuristic algorithm proposed for the solution of large intractable combinatorial optimization problems. The hawks are cooperative birds and use many intelligent hunting techniques. This study proposes new HHO algorithms for solving the well-known quadratic assignment problem (QAP). Large instances of the QAP have not been solved exactly yet. We implement HHO algorithms with robust tabu search (HHO-RTS) and introduce new operators that simulate the actions of hawks. We also developed an island parallel version of the HHO-RTS algorithm using the message passing interface. We verify the performance of our proposed algorithms on the QAPLIB benchmark library. One hundred and twenty-five of 135 problems are solved optimally, and the average deviation of all the problems is observed to be 0.020%. The HHO-RTS algorithm is a robust algorithm compared to recent studies in the literature. [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]

We consider both facial reduction, FR, and symmetry reduction, SR, techniques for semidefinite programming, SDP. We show that the two together fit surprisingly well in an alternating direction method of multipliers, ADMM, approach. In fact, this approach allows for simply adding on nonnegativity constraints, and solving the doubly nonnegative, DNN , relaxation of many classes of hard combinatorial problems. We also show that the singularity degree remains the same after SR, and that the DNN relaxations considered here have singularity degree one, that is reduced to zero after FR. The combination of FR and SR leads to a significant improvement in both numerical stability and running time for both the ADMM and interior point approaches. We test our method on various DNN relaxations of hard combinatorial problems including quadratic assignment problems with sizes of more than n = 500 . This translates to a semidefinite constraint of order 250, 000 and 625 × 10 8 nonnegative constrained variables, before applying the reduction techniques. [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]

A common computational approach for polynomial optimization problems (POPs) is to use (hierarchies of) semidefinite programming (SDP) relaxations. When the variables in the POP are required to be nonnegative – as is the case for combinatorial optimization problems, for example – these SDP problems typically involve nonnegative matrices, i.e. they are conic optimization problems over the doubly nonnegative cone. The Jordan reduction, a symmetry reduction method for conic optimization, was recently introduced for symmetric cones by Parrilo and Permenter [Mathematical Programming 181(1), 2020]. We extend this method to the doubly nonnegative cone, and investigate its application to known relaxations of the quadratic assignment and maximum stable set problems. We also introduce new Julia software where the symmetry reduction is implemented. [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]

A new method is proposed for robust quadratic pole assignment problem. We first give the results on the solution of quadratic pole assignment problem. Then the Schur form corresponding to closed-loop system is established and normality departure is used to measure the robustness of closed-loop system. On these grounds, a method for robust quadratic pole assignment problem is proposed by minimizing the normality departure of closed-loop system. The proposed method avoids to transform the second-order control system to the first-order control system. Moreover, it is implemented in real operations. Numerical experiments show that our method has good performance on the robustness of closed-loop system. [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]

ELA features are used for identifying strengths and weaknesses of algorithms, automatic algorithm selection, per instance algorithm configuration and generation methods, and benchmark construction techniques. The extracted features of algorithms, their main concepts, and search operators, are used to create a set of classification indicators to distinguish between a representative set of algorithm behaviors. The paper I Understanding measure-driven algorithms solving irreversibly ill-conditioned problems i by Sawicki et al. provides a framework for understanding and analyzing the behavior of stochastic population-based algorithms in solving ill-conditioned global optimization problems. Understanding of optimization algorithm's behavior is a vital part that is needed for quality progress in the field of stochastic optimization algorithms. [Extracted from the article]

The quadratic assignment problem (QAP) is a well-known challenging combinational optimization problem that has received many researchers' attention with varied real-world and industrial applications areas. Using the framework of basic artificial bee colony algorithm, frequently used crossover and mutation operators, and combined with an effective local search method, this paper proposes a simple but effective discrete artificial bee colony (DABC) algorithm for solving quadratic assignment problems (QAPs). Typical QAP benchmark instances are selected from QAPLIB in order to conduct the simulation experiment where common performance metrics are used to evaluate the algorithm. The paper also investigates the influence factors of the algorithm's performance. The results show that the proposed algorithm is a quite effective and practical new approach for handling QAP problems. [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]

In this paper, we consider the partial quadratic eigenvalue assignment problem (PQEAP) for vibration system by active feedback control, such that some "troublesome" eigenpairs are replaced by some suitable chosen or newly measured ones, while the remaining unknown eigenpairs are kept unchanged. With the assumptions that the mass and stiffness matrices are nonsingular, we give a new proof of the spectral decomposition of quadratic symmetric pencil. And then we provide some necessary and sufficient conditions of the feedback matrices so that the closed-loop can preserve the no spill-over property. With these conditions, we characterize a set of parametric solutions to the PQEAP using receptances, system matrices and a few open-loop eigenpairs. Finally, we propose a gradient-based optimization method for solving the minimum norm solution to the PQEAP. Numerical experiments illustrate the effectiveness and robustness of the proposed algorithm. • Consider quadratic eigenvalue assignment for vibration system. • Solve problem using receptances and system matrices. • Provide necessary and sufficient condition of closed-loop preserving no spillover. • Propose gradient-based optimization method for minimum norm solution. [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]

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]

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]

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 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 quadratic assignment problem (QAP) is one of the hardest combinatorial optimization tasks. It has many real-world applications such as airport gate assignment, and hospital layout problem. Designing enhanced optimization methodologies for the QAP is an active research area. In this paper, we present an integrated firefly algorithm (FA) based on mutually orthogonal Latin squares (MOLS), named as FA-MOLS, to solve the QAP. In the optimization process, the FA-MOLS employs three improvements, namely the MOLS strategy, opposition-based learning scheme, and repeated 2-exchange mutation to maintain the balance between exploitation and exploration abilities. By these improvements, it is intended to avoid the trapping in local optima and improve the convergence speed. The performance of the proposed FA-MOLS is validated on different test instances from the literature. Additionally, two real-world QAPs are simulated and investigated, the office buildings of a single company and the layout of hospital departments. The comprehensive experimental simulations and the nonparametric Wilcoxon's test affirm that the proposed FA-MOLS can provide a highly competitive performance compared with other algorithms from the literature. Therefore, it is concluded that FA-MOLS is an efficient and reliable algorithm for solving industrial quadratic assignment tasks. [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]

• Connect quadratic assignment model (QAP) with network design problem. • Reformulate time-dependent synchronized service design as network-based quadratic assignment problem. • Propose extended Gilmore-Lawler Bound (EGLB) in the generic QAP network. • Develop Branch & Bound algorithm with an effective lower bound estimator using EGLB. A new modeling framework is developed in this paper to design a class of synchronized transportation services that can be formulated as a time-dependent synchronized service network design problem. The framework is established using a generic network representation for the quadratic assignment problem (QAP). As one of the fundamental combinatorial optimization problems, the QAP was introduced by Koopmans and Beckman (KB-QAP), in 1957, in the context of locating economic activities. Our proposed network-based QAP (NET-QAP) model not only linearizes the KB-QAP model but also generalizes the traditional QAP model as a special case with a symmetric network structure. The NET-QAP is utilized to formulate a time-dependent synchronized service network design problem to obtain an optimal schedule for both inbound and outbound services in a transshipment area, where commodities are collected from origins using the inbound services and distributed to their final destinations using the outbound services (after sorting and storage). From the view of the Gilmore-Lawler Bound (GLB), this paper explores a new branch and bound framework to solve the synchronizing NET-QAP problem. An extended GLB (E-QAP) is adopted in this research as a lower bound estimator for the first-stage assignment costs, based on several relaxed subproblems in the second-stage assignment. Then, the framework can also be applied to estimate the cost of sub-decisions that are involved in making a broader decision-making problem. Numerical experiments are conducted to demonstrate the effectiveness and applicability of the proposed modeling and computational framework. [ABSTRACT FROM AUTHOR]

We benchmark the 5000+ qubit system Advantage coupled with the Hybrid Solver Service 2 released by D-Wave Systems Inc. in September 2020 by using a new class of optimization problems called garden optimization problems known in companion planting. These problems are scalable to an arbitrarily large number of variables and intuitively find application in real-world scenarios. We derive their QUBO formulation and illustrate their relation to the quadratic assignment problem. We demonstrate that the Advantage system and the new hybrid solver can solve larger problems in less time than their predecessors. However, we also show that the solvers based on the 2000+ qubit system DW2000Q sometimes produce more favourable results if they can solve the problems. [ABSTRACT FROM AUTHOR]

• Based on practical instances, we formalize two special cases of graph matching and wireless localization matching problem. • We show that the first special case is NP-hard when the graph degree k is greater than one. • We also give an O (k) -approximation algorithm for the first special case. • We give an O (n χ) -approximation algorithm for the second special case when χ is the problem parameter. Given a set of edge pairs in a complete bipartite graph, we want to find a bipartite matching that includes the maximum number of those edge pairs. While the problem has many applications to wireless localization and computer vision, to the best of our knowledge, there is no theoretical work for the problem. In this work, unless P = N P , we show that there is no constant approximation for the problem. Then, we consider two special cases of the problem. Suppose that k denotes the maximum number of input edge pairs such that a particular node can be in. Inspired by experimental results, the first case is for when k is not large. While there is a simple polynomial-time algorithm for the problem when k is one, we show that the problem is NP-hard when k is greater than one. We also devise an efficient O (k) -approximation algorithm for the problem. For the second case, every pair of nodes in the same partition of the input bipartite graph are labeled with one of χ colors. We want to match, between the two partitions, a pair of nodes to a pair of nodes with the same color. Denote n as the number of nodes, we give an O (χ n) -approximation algorithm for this case. [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]

Random graph matching refers to recovering the underlying vertex correspondence between two random graphs with correlated edges; a prominent example is when the two random graphs are given by Erdős-Rényi graphs G (n , d n) . This can be viewed as an average-case and noisy version of the graph isomorphism problem. Under this model, the maximum likelihood estimator is equivalent to solving the intractable quadratic assignment problem. This work develops an O ~ (n d 2 + n 2) -time algorithm which perfectly recovers the true vertex correspondence with high probability, provided that the average degree is at least d = Ω (log 2 n) and the two graphs differ by at most δ = O (log - 2 (n)) fraction of edges. For dense graphs and sparse graphs, this can be improved to δ = O (log - 2 / 3 (n)) and δ = O (log - 2 (d)) respectively, both in polynomial time. The methodology is based on appropriately chosen distance statistics of the degree profiles (empirical distribution of the degrees of neighbors). Before this work, the best known result achieves δ = O (1) and n o (1) ≤ d ≤ n c for some constant c with an n O (log n) -time algorithm and δ = O ~ ((d / n) 4) and d = Ω ~ (n 4 / 5) with a polynomial-time algorithm. [ABSTRACT FROM AUTHOR]