Search

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.

Majority of chapters of this book show usefulness of greedy like algorithms for solving various combinatorial optimization problems. The aim of this chapter is to warn the reader that not always a greedy like approach is a good option and, in certain cases, it is a very bad option being sometimes among the worst possible options. Our message is not a discouragement from using greedy like algorithms altogether; we think that for every combinatorial optimization problem of importance, researchers and practitioners should simply investigate the appropriateness of greedy like algorithms and the existence of better alternatives to them (considering both quality of solution and running time). In many cases, especially when the running time must be very short, the conclusion may still be that the most practical of known approaches is a greedy like algorithm. The Traveling Salesman and Multidimensional Assignment Problems are optimization problems for which greedy like approaches are usually not very successful. We demonstrate this by providing both theoretical and experimental results on greedy like algorithms as well as on some other algorithms that produce (in theory and/or in experiments) much better results without spending significantly more time. There are some general theoretical results that indicate that there are, in fact, many combinatorial optimization problems for which greedy like algorithms are not the best option even among fast construction heuristics, see, e.g., [3, 5, 17]. We will not consider these general results in order to avoid most mathematical details that are not necessary for understanding the results of this chapter. For this reason we will not give proofs here apart from two simple proofs: that of Theorem 8 which shows that some instances on which the greedy algorithm fails are not exotic in a sense and that of Theorem 11 since Theorem 11 is a new result. It is not a trivial question whether a certain algorithm is greedy like or not. In the next section we define an independence system and give the classic definition of the greedy algorithm for such a system. We extend this definition to so-called greedy type algorithms that include such well-known algorithms as the Prim’s algorithm for the minimum spanning tree problem and the nearest neighbor algorithm for the traveling salesman problem. We use the term ‘greedy like’ in an informal way and we include in this class simple and fast construction heuristics that seem to us to be of greedy nature. O pe n A cc es s D at ab as e w w w .in te ch w eb .o rg

Kılıç, Haydar (Bilecik, Author) Yüzgeç, Uğur (Bilecik, Author) We propose and develop an improved version of antlion optimizer (ALO), namely tournament selection based antlion optimization algorithm for quadratic assignment problem (QAP). ALO algorithm has some handicaps, such as long run time, local optima stagnation and premature convergence for some problems. The literature describes different methods that improve the performance of antlion optimizer, but most of these are about specific optimization problems. In this paper, we introduce the tournament selection method instead of the roulette wheel method on random walking mechanism of ALO and we update some equations used in ALO algorithm. To compare the proposed tournament selection based ALO (TALO) algorithm with classic ALO, we deal with ten benchmark functions from literature. The comparison results are evaluated according to the different metrics, such as mean best, standard deviation, optimality, accuracy, CPU time, number of function evaluations (NFE). The detailed analyzes of the proposed TALO algorithm are performed. These are the convergence analysis, statistical analysis, search history analysis, trajectory analysis, average distance analysis, computational complexity analysis. The proposed TALO algorithm is compared with the other ALO versions (binary ALO and chaotic ALO variants) for same ten benchmark functions. As last, TALO algorithm has been also implemented for the quadratic assignment problem (QAP). The QAP results has been compared with several well-known meta-heuristic algorithms. TALO's performance has been evaluated with those of binary ALO and chaotic ALO variants for same QAP instance. Finally, the solution quality of proposed TALO algorithm has been analyzed for solving QAP using some instances presented in QAPLIB site. The results provide the proposed TALO algorithm has the best performance in comparison with those of the other meta-heuristic algorithms. Due to the performance of TALO algorithm, we expect this version to be applied for different optimization problems. (C) 2018 Karabuk University. Publishing services by Elsevier B.V. WOS:000463211100031 1-s2.0-S2215098618311340 Q1 Q2

Recently, multi-objective evolutionary algorithms (MOEAs) have been extensively used to solve multi-objective optimization problems (MOPs) since they have the ability to approximate a set of non-dominated solutions in reasonable CPU times. In this paper, we consider the bi-objective quadratic assignment problem (bQAP), which is a variant of the classical QAP, which has been extensively investigated to solve several real-life problems. The bQAP can be defined as having many input flows with the same distances between the facilities, causing multiple cost functions that must be optimized simultaneously. In this study, we propose a memetic algorithm with effective local search and mutation operators to solve the bQAP. Local search is based on swap neighborhood structure whereas the mutation operator is based on ruin and recreate procedure. The experimental results show that our bi-objective memetic algorithm (BOMA) substantially outperforms all the island-based variants of the PASMOQAP algorithm proposed very recently in the literature.

Levy flight Shuffle Frog Leaping Algorithm (LSFLA) is a SFLA variant and enhances the performance of SFLA largely, however, it still has some defects, such as poor convergence and low efficiency. So an improved LSFLA, namely, LSFLA based on Differential perturbation and Quasi-Newton search (DQLSFLA), is proposed in this paper. Firstly, the way of updating only one solution which is the worst one at every sub-iteration in LSFLA is replaced with an all-solution updating way in the subgroup to improve the probability of obtaining the best solution, to omit one sorting step at every sub-iteration and the sub-iteration number parameter setting, to reduce the computational complexity and to enhance the optimization efficiency. Secondly, a random differential perturbation approach and an improved Levy flight updating one are created and used in the subgroup updating to form DLSFLA, that is, the first half frogs in the subgroup use the random differential perturbation updating approach to improve the global search ability, and the last half adopt the improved Levy flight updating method to keep the advantage of the Levy flight updating method and overcome its defects. Finally, quasi-Newton local search is integrated into DLSFLA near the end of the algorithm to improve the convergence speed. Experimental results on the complex functions from CEC-2014 show that DQLSFLA's convergence quality and optimization efficiency are much better than LSFLA's and that compared with quite a few other state-of-the-art algorithms, DQLSFLA has better performance. The results on medical image enhancement and Quadratic Assignment Problem (QAP) also show that DQLSFLA can solve the real word optimization problems better than LSFLA can.

The Quadratic Assignment Problem (QAP) is a combinatorial NP-hard optimization problem that is not solvable in a polynomial time. It has a large number of real-world applications in diverse fields (e.g. facility arrangement in a hospital). The Whale Optimization Algorithm is a new meta-heuristic that achieves a great success in solving the continuous problems. In this paper, we propose a memetic algorithm using the Whale optimization Algorithm (WA) Integrated with a Tabu Search (WAITS) for solving QAP. In fact, this work employs Tabu Search to improve the quality of solution obtained by WA for QAP problem as a local search algorithm. This is an attempt to improve the convergence speed and local search of WA as its main drawbacks. Due to the combinatorial nature of QAP, the continuous values generated from the standard WA were converted to discrete values by the largest real value mapping. The WAITS algorithm is enhanced by a local search that defines a set of neighborhood solutions to improve the accuracy of the obtained solutions. Fourteen different case studies including 122 test problems are employed for analyzing the performance of the proposed WAITS. The results show that the proposed memetic algorithm finds near-optimal solutions with an acceptable computational time. WAITS is compared to several algorithms in the literature. The results show that the proposed algorithm outperforms similar algorithms in the literature.

There has always been a need to solve real-life large-scale problems, suchas efficiently allocating limited resources, and other complex and conflicting situations related to combinatorial optimization genre. A class of combinato- rial optimization problems is NP-hard and, among many well-known, several of them are assignment, planning and rescheduling problems. Assignment problems can deal with optimal assignment of teams of collaborating agents; planning problems can be effects-based planning that search for promising plans to get desired end states with minimal cost; rescheduling problems can be multi-criteria optimization of rescheduling resources that modify existing original schedule. These large scale optimization problems are complex with intractable and highly complex search spaces. Currently, there are no known algorithms with polynomial time complexity, which can solve these problems. Genetic Algorithms have been successfully applied to solve many complex optimization problems but not to the specific problems mentioned above.The aim of the research, presented in this thesis, is to use Genetic Algo- rithms for large scale optimization of assignment, planning and rescheduling problems. More specifically, the contributions of the thesis are to: (i) adapt existing and develop new efficient Genetic Algorithms to solve large scale as- signment problems, and (ii) adapt existing Genetic Algorithms to solve large scale effects-based planning, and multi-objective rescheduling optimization problems.In case of assignment, we solve a team assignment problem and investigate specific regions in a solution space for assignment problems with huge search spaces.For the team assignment, an existing Genetic Algorithm is adapted and applied for optimal assignment of tasks to teams of collaborating agents. The algorithm is scalable, stable, robust and produces a near optimal solution. The results of the team assignment problem show that the existing Genetic Algorithms are not efficient for optimal assignment of tasks to teams of agents. Hence, to solve larger instances of the problem efficiently, new Genetic Algo- rithms are developed with emphasis on the construction of crossover opera- tors. Since teams assignment can be multi-criteria, a multi-objective model is constructed and two widely used multi-objective evolutionary algorithms are applied. Further, for the assignment problems with huge search spaces, an existing Genetic Algorithm is adapted to extract possible combinations of input parameters from a specified solution space region. To solve the large scale effects-based planning, a multi-objective optimization problem is formu- lated for the evaluation of operational plans and a multi-objective Genetic Algorithm is adapted and applied to the problem. The results show that the suggested algorithm is much more efficient than A*. For the rescheduling problem, a multi-objective optimization model for rescheduling of resources is proposed and a multi-objective Genetic Algorithm is adapted and applied to obtain the Pareto-optimal solutions.The research presented in this thesis confirms that Genetic Algorithms can be used for large scale assignment, planning and rescheduling problems since they have shown to be suitable in solving these problems efficiently.

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., open-source code available at https://jugit.fz-juelich.de/qip/garden-optimization-problem.git

Quadratic Assignment Problem (QAP) is a problem of facility locations of individual resources. QAP is a proven NP-hard challenging optimization problem and has a large number of real-life applications in diverse fields such as hospital layout problems, machine scheduling, keyboard design, and backboard wiring problem. Artificial electric field optimization (AEFA) is a new metaheuristic optimization algorithm and has achieved great success in continuous optimization problems. This paper presents a discrete artificial electric field algorithm for QAP. Due to the combinatorial nature of QAP, the general operations of AEFA such as particle representations, velocity and position update rules, and subtraction operations are modified. The proposed algorithm is applied to solve the QAP instances taken from the QAP library. The results show the promising performance of the proposed algorithm.

Due to ever changing browsing patterns of the website users, the companies need to adapt the structure of their websites regularly. Webpage positioning problem (WPP) is about deciding the best locations of the webpages in the hyperlink graph structure of the website. Ant colony optimization (ACO) is among the prominent algorithms to solve the optimization problems. In this regard, this chapter aims to solve the webpage positioning problem by formulating it as quadratic assignment problem (QAP). The solution of this problem by ant colony optimization can already be found in the existing literature, subsequently in this chapter the solution to the problem is found by considering heuristic desirability parameter in ant colony optimization technique. In the end, a comparative analysis of both simple ACO and ACO with heuristic desirability as solutions to WPP problem is performed. The experimental results on artificial and real life datasets reveal that the ACO with heuristic desirability produced better results with most of the problem instances.

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.

The Quadratic Assignment problem (QAP) is one of the most studied optimization problem. Although many direct and heuristic methods are used to give the solution of QAP for small size instances in reasonable time but it takes huge time for large size instances. So, solving QAP in massively parallel architecture like Graphics processing unit (GPU) by applying a noble metaheuristics Crow Search Algorithm (CSA) can further optimize the solution and their execution time. So, in this paper we analyse the QAP in accelerated systems by using CSA metaheuristics and CSA performs approximately 10 times faster on GPU as compared to CPU.

© 2020, CIMNE, Barcelona, Spain. Many optimization problems encountered in the real-world have more than two objectives. To address such optimization problems, a number of evolutionary many-objective optimization algorithms were developed recently. In this paper, we tested 18 evolutionary many-objective algorithms against well-known combinatorial optimization problems, including knapsack problem (MOKP), traveling salesman problem (MOTSP), and quadratic assignment problem (mQAP), all up to 10 objectives. Results show that some of the dominance and reference-based algorithms such as non-dominated sort genetic algorithm (NSGA-III), strength Pareto-based evolutionary algorithm based on reference direction (SPEA/R), and Grid-based evolutionary algorithm (GrEA) are promising algorithms to tackle MOKP and MOTSP with 5 and 10 while increasing the number of objectives. Also, the dominance-based algorithms such as MaOEA-DDFC as well as the indicator-based algorithms such as HypE are promising to solve mQAP with 5 and 10 objectives. In contrast, decomposition based algorithms present the best on almost problems at saving time. For example, t-DEA displayed superior performance on MOTSP for up to 10 objectives.

Quantum annealing and D-Wave quantum annealer attracted considerable attention for their ability to solve combinatorial optimization problems. In order to solve other type of optimization problems, it is necessary to apply certain kinds of mathematical transformations. However, linear constraints reduce the size of problems that can be represented in quantum annealers, owing to the sparseness of connections between qubits. For example, the quadratic assignment problem (QAP) with linear equality constraints can be solved only up to size 12 in the quantum annealer D-Wave Advantage, which has 5640 qubits. To overcome this obstacle, Ohzeki developed a method for relaxing the linear equality constraints and numerically verified the effectiveness of this method with some target problems, but others remain unsolvable. In particular, it is difficult to obtain feasible solutions to problems with hard constraints, such as the QAP. We therefore propose a method for solving the QAP with quantum annealing by applying a post-processing bit-flip heuristic algorithm to solutions obtained by the Ohzeki method. In a numerical experiment, we solved a sparse QAP by the proposed method. This sparse QAP has been used in areas such as item listing on an E-commerce website. We successfully solved a QAP of size 19 with high accuracy for the first time using D-Wave Advantage. We also confirmed that the bit-flip heuristic algorithm moves infeasible solutions to nearby feasible solutions in terms of Hamming distance with good computational efficiency., Comment: 11 pages. The first page includes the initial screen displaying IEEE-copyrighted material

This paper aims to highlight the motivations for investigating genetic algorithms to solve the DNA Fragments Assembly problem (DNA_FA). DNA_FA is an optimization problem that attempts to reconstruct the original DNA sequence by finding the shortest DNA sequence from a given set of fragments. We showed that the DNA_FA optimization problem is a special case of the two well-known optimization problems: The Traveling Salesman Problem (TSP) and the Quadratic Assignment Problem (QAP). TSP and QAP are important problems in the field of combinatorial optimization and for which there exists an abundant literature. Genetic Algorithms (GA) applied to these problems have led to very satisfactory results in practice. In the perspective of designing efficient genetic algorithms to solve DNA_FA we showed the existence of a polynomial-time reduction of DNA-FA into TSP and QAP enabling us to point out some technical similarities in terms of solutions and search space complexity. We then conceptually designed a genetic algorithm platform for solving the DNA-FA problem inspired from the existing efficient genetic algorithms in the literature solving TSP and QAP problems. This platform offers several ingredients enabling us to create several variants of GA solvers for the DNA assembly optimization problems.

This paper studies a specific class of multiobjective combinatorial optimization problems (MOCOPs), namely the permutation-based MOCOPs. Many commonly seen MOCOPs, e.g., multiobjective traveling salesman problem (MOTSP), multiobjective project scheduling problem (MOPSP), belong to this problem class and they can be very different. However, as the permutation-based MOCOPs share the inherent similarity that the structure of their search space is usually in the shape of a permutation tree, this paper proposes a generic multiobjective set-based particle swarm optimization methodology based on decomposition, termed MS-PSO/D. In order to coordinate with the property of permutation-based MOCOPs, MS-PSO/D utilizes an element-based representation and a constructive approach. Through this, feasible solutions under constraints can be generated step by step following the permutation-tree-shaped structure. And problem-related heuristic information is introduced in the constructive approach for efficiency. In order to address the multiobjective optimization issues, the decomposition strategy is employed, in which the problem is converted into multiple single-objective subproblems according to a set of weight vectors. Besides, a flexible mechanism for diversity control is provided in MS-PSO/D. Extensive experiments have been conducted to study MS-PSO/D on two permutation-based MOCOPs, namely the MOTSP and the MOPSP. Experimental results validate that the proposed methodology is promising.

Combinatorial optimization problems arise from various real life situations and the quadratic assignment problem (QAP) to model a facility layout problem or a plant location problem is such an example. While examining the facility layout of a semi-automated bus body manufacturing unit, a bi-objective facility layout optimization problem is identified in which the solution space of the second objective function depends and changes upon the feasible solutions of the first objective function. In this paper, the said problem is first defined in the form of a bi-objective quadratic dependent location assignment problem (bi-d-QAP), a heuristic solution approach is then provided, and finally, a modified artificial bee colony algorithm is proposed while combining both the genetic and neighborhood search algorithms to solve the considered bi-d-QAP. The data obtained from the above-mentioned manufacturing unit are utilized to show how the proposed algorithm performs better in comparison to some of the popular state-of-the-art optimization algorithms.

Advances in Pareto optimization techniques have encouraged the study of their application to solve single-objective optimization problems. The motive is that the Pareto concept can be an effective approach to reduce the impacts of local optima. The most challenging task in developing such an approach is the reformulation of the target single-objective to multiple objectives. This paper proposes a new multi-objectivization approach by introducing an additional helper objective that is to be optimized with the primary objective simultaneously using Pareto local search. As a key feature, the additional objective is formulated as a function of the primary objective and penalties associated to solution features. The penalties are dynamically updated during the search, with the hope to guide the search to avoid non-promising features for the primary objective. Computational results on the traveling salesman problem and the quadratic assignment problem confirm the effectiveness of the proposed approach in comparison to other multi-objectivization approaches and state-of-the-art methods on these benchmarks.

Many-objective optimization focuses on solving optimization problems with four or more objectives. Effort has been made mainly on studying continuous problems, with interesting results and for which several proposals have appeared. An important result states that the problem does not necessarily becomes more difficult while more objectives are considered. Nevertheless, combinatorial problems have not received an appropriate attention, making this an open research area. This investigation takes this subject on by studying a many-objective combinatorial problem, particularly, the pickup and delivery problem (PDP), which is an important combinatorial optimization problem in the transportation industry and consists of finding a collection of routes with minimum cost. Traditionally, cost has been associated with the number of routes and the total travel distance, however, in many applications, some other objectives emerge, for example, travel time, workload imbalance, and uncollected profit. If we consider all these objectives equally important, PDP can be tackled as a many-objective problem. This study is concerned with the study of: (i) the performance of four representative multi-objective evolutionary algorithms on PDP varying the number of objectives, (ii) the properties of the many-objective PDP regarding scalability, i.e. the conflict between each pair of objectives and the proportion of non-dominated solutions as the number of objectives is varied, and finally (iii) the change of PDP's difficulty when the number of objectives is increased. Results show that the regarded objectives are actually in conflict and that the problem is more difficult to solve while more objectives are considered.

The Quadratic assignment problem (QAP) is to assign a set of facilities to a set of locations with given distances between the locations and given flows between the facilities such that the sum of the products between flows and distances is minimized, which is a notoriously difficult NP-hard combinatorial optimization problem. A lot of heuristics have been proposed for the QAP problem, and some of them have proved to be efficient approximation algorithms for this problem. Ant colony optimization (ACO) is a general-purpose heuristic and usually considered as an approximation algorithms for NP-hard optimization problems. However, we know little about the performance of ACO for QAP from a theoretical perspective. This paper contributes to a theoretical understanding of ACO on the QAP problem. The worst-case bound on a simple ACO algorithm called (1+1) Max-min ant algorithm ((1+1) MMAA) for the QAP problem is presented. It is shown that a degenerate (1+1) MMAA finds an approximate solution on the QAP problem. Finally, we reveal that ACO can outperform the 2-exchange local search algorithm on an instance of the QAP problem.

This paper applies four population-based classical meta-heuristic algorithms to solve a pick-and-place optimization problem for a surface mounter in a PCB assembly environment. A mathematical model of this optimization problem is formulated as an integrated problem of the capacitated vehicle routing problem and the quadratic assignment problem, which are well-known NP-hard problems. A brief description of each method is presented and special operators for the integer encoded solutions are developed. Ten real-world PCB samples are tested and optimized using all the four algorithms. The experiment results show that the genetic algorithm has better performance than the others in terms of solution quality, especially the deviation of results from multiple trials, and computation time.

The kernel technology is proposed to solve discrete optimization problems. It forms solution kernel and allows efficient stochastic perturbations of this solution in iterative schemes. Comparative analysis of the two versions of the new algorithm for the quadratic assignment problem (with and without kernel allocation technology) and modern algorithms demonstrated the efficiency of this technology in terms of speed and solution quality. The kernel technology can be easily incorporated into the available algorithms.

The bat algorithm is one of the recent nature-inspired algorithms, which has been emerged as a powerful search method for solving continuous as well as discrete problems. The quadratic assignment problem is a well-known NP-hard problem in combinatorial optimization. The goal of this problem is to assign n facilities to n locations in such a way as to minimize the assignment cost. For that purpose, this paper introduces a novel discrete variant of bat algorithm to deal with this combinatorial optimization problem. The proposed algorithm was evaluated on a set of benchmark instances from the QAPLIB library and the performance was compared to other algorithms. The empirical results of exhaustive experiments were promising and illustrated the efficacy of the suggested approach.

Solution representation is an important aspect of the development of a meta-heuristic. However, most meta-heuristics focus on the algorithm aspect rather than the solution representation. As the scale of the optimization problem under study rises, the solution representation becomes ever more crucial because the computational performance tends to deteriorate for three reasons: (1) increased landscape complexity, (2) exponential growth of search space, and (3) costly function evaluation. In this study, data compression of solution representation is explored to improve the performance of meta-heuristics in terms of compression efficiency and solution quality. A proposed new data compression scheme – variable-length solution representation compression for meta-heuristics – is developed and tested against benchmarked problem instances from the quadratic assignment problem library (QAPLIB) and additional large problem instances. The analyzed results indicate that the compressed solution representation scheme under a meta-heuristic framework performs well against the QAPLIB and large problem instances with less space complexity and computation time.

The pipeline task of scheduling theory (flow shop) with the standard constraints, the variables of which are the times of the beginning of processing of each of the tasks on the corresponding device are investigated. Tasks of this type belong to the NP-complex class with the number of processing devices more than two. The number of calculations and the search time for the optimal schedule grow in proportion to n !, where n is the number of jobs. By some transformations the constraints of the pipeline task are reduced to analytical functions of the unknown variables, and the objective function to the linear function of these variables. The number of functions, the constraints of the optimization problem, depends polynomially on the number of tasks of the original pipeline task. Then, using the method of exact quadratic regularization (EQR), let’s pass to the problem of convex optimization. Since the number of constraints depends polynomially on the number of jobs, the search time of the optimal schedule will grow polynomially for a fixed accuracy of the solution. Thus, the NP-complex problem of scheduling theory is transformed to the problem of convex optimization with a linear objective function. It is shown that any pipeline problem of scheduling theory reduces to the problem of a minimum of a linear function with a set of linear and quadratic constraints, that is, to a problem of convex optimization. A model example is considered and an optimal schedule with a given accuracy is obtained by the method of exact quadratic regularization.

Bi-level optimization problems (BOPs) are a class of challenging problems with two levels of optimization tasks. The main goal is to optimize the upper level problem which has another optimization problem as a constraint. In these problems, the optimal solutions to the lower level problem become possible feasible candidates to the upper level one. Such a requirement makes the optimization problem difficult to solve, and has kept the researchers busy towards devising methodologies, which can efficiently handle the problem. Recently, a new research field, called EBO (Evolutionary Bi-Level Optimization) has appeared thanks to the promising results obtained by the use of EAs (Evolutionary Algorithms) to solve such kind of problems. However, most of these promising results are restricted to the continuous case. The number of existing EBO works for the discrete (combinatorial case) bi-level problems is relatively small when compared to the field of evolutionary continuous BOP. Motivated by this observation, we have recently proposed a Co-evolutionary Decomposition-Based Algorithm (CODBA) to solve combinatorial bi-level problems. The recently proposed approach applies a Genetic Algorithm to handle BOPs. Besides, a new recently proposed meta-heuristic called CRO has been successfully applied to several practical NP-hard problems. To this end, we propose in this work a CODBA-CRO (CODBA with Chemical Reaction Optimization) to solve BOP. The experimental comparisons against other works within this research area on a variety of benchmark problems involving various difficulties show the effectiveness and the efficiency of our proposal.

This article explores the integrated optimization problem of location assignment and sequencing in multi-shuttle automated storage/retrieval systems under the modified 2n-command cycle pattern. The decision of storage and retrieval (S/R) location assignment and S/R request sequencing are jointly considered. An integer quadratic programming model is formulated to describe this integrated optimization problem. The optimal travel cycles for multi-shuttle S/R machines can be obtained to process S/R requests in the storage and retrieval request order lists by solving the model. The small-sized instances are optimally solved using CPLEX. For large-sized problems, two tabu search algorithms are proposed, in which the first come, first served and nearest neighbour are used to generate initial solutions. Various numerical experiments are conducted to examine the heuristics’ performance and the sensitivity of algorithm parameters. Furthermore, the experimental results are analysed from the viewpoint of prac...

This paper presents GHOST , a combinatorial optimization framework that a real-time strategy (RTS) AI developer can use to model and solve any problem encoded as a constraint satisfaction/optimization problem (CSP/COP). We show a way to model three different problems as a CSP/COP, using instances from the RTS game StarCraft as test beds. Each problem belongs to a specific level of abstraction (the target selection as reactive control problem, the wall-in as a tactics problem, and the build order planning as a strategy problem). In our experiments, GHOST shows good results computed within some tens of milliseconds. We also show that GHOST outperforms state-of-the-art constraint solvers, matching them on the resources allocation problem, a common combinatorial optimization problem.

In this paper we discuss the use of graph deep learning in solving quadratic assignment problems (QAP). The quadratic assignment problem is an NP hard optimization problem. We shall analyze an approach using Graph Convolutional Networks (GCN). We prove that a specially designed GCN produces the optimal solution for a broad class of assignment problems. By appropriate training, the class of problems correctly solved is thus enlarged. Numerical examples compare this method with other simpler methods.

This paper proposes a method for visualizing combinatorial search spaces named low-dimensional Euclidean embedding (LDEE). The proposed method transforms the original search space, such as a set of permutations or binary vectors, to $\pmb {\mathbb {R}}^{k}$ (with ${k} {=} {2}$ or 3 in practice) while aiming to preserve spatial relationships existing in the original space. The LDEE method uses the t-distributed stochastic neighbor embedding (t-SNE) to transform solutions from the original search space to the Euclidean one. In this paper, it is mathematically shown that the assumptions underlying the t-SNE method are valid in the case of permutation spaces with the Mallows distribution. The same is true for other metric spaces provided that the distribution of points is assumed to be normal with respect to the adopted metric. The embedding obtained using t-SNE is further refined to ensure visual separation of individual solutions. The visualization obtained using the LDEE method can be used for analyzing the behavior of the population in a population-based metaheuristic, the working of the genetic operators, etc. Examples of visualizations obtained using this method for the four peaks problem, the firefighter problem, the knapsack problem, the quadratic assignment problem, and the traveling salesman problem are presented in this paper.

International audience; Parallelization is an important paradigm for solving massive optimization problems. Understanding how to fully benefit form the aggregated computing power and what makes a parallel strategy successful is a difficult issue. In this study, we propose a simple parallel iterative tabu search (PITS) and study its effectiveness with respect to different experimental settings. Using the quadratic assignment problem (QAP) as a case study, we first consider different small-and medium-size instances from the literature and then tackle a large-size instance that was rarely considered due the its inherent solving difficulty. In particular, we show that a balance between the number of function evaluations each parallel process is allowed to perform before resuming the search is a critical issue to obtain an improved quality.

The quadratic assignment problem is involved with designing the best layouts for facilities and has a wide variety of applications in industry. This paper presents a decomposition-based procedure for solving this NP-hard optimization problem. The procedure aims at enhancing an initial solution in five interacting and synergetic layers. In the first layer, the initial solution undergoes the process of local search and becomes local optimal. In the second layer, the linear assignment technique is called and results in a suggestion for an enhancement. The third layer is about decomposing the proposed suggestion into several cycles. Then, in the fourth layer, each cycle is further decomposed into several segments. The number of the segments associated with each cycle is the length of the corresponding cycle, which was calculated in the third layer. Finally, the segments are processed in the fifth layer and potentially enhance the original solution. The employed decomposition has proved to be effective, and comparing the performance of the procedure with that of other state-of-the-art procedures indicates its efficiency.

For e-commerce websites, deciding the manner in which items are listed on webpages is an important issue because it can dramatically affect item sales. One of the simplest strategies of listing items to improve the overall sales is to do so in a descending order of sales or sales numbers. However, in lists generated using this strategy, items with high similarity are often placed consecutively. In other words, the generated item list might be biased toward a specific preference. Therefore, this study employs penalties for items with high similarity being placed next to each other in the list and transforms the item listing problem to a quadratic assignment problem (QAP). The QAP is well-known as an NP-hard problem that cannot be solved in polynomial time. To solve the QAP, we employ quantum annealing (QA), which exploits the quantum tunneling effect to efficiently solve an optimization problem. In addition, we propose a problem decomposition method based on the structure of the item listing problem because the quantum annealer we use (i.e., D-Wave 2000Q) has a limited number of quantum bits. Our experimental results indicate that we can create an item list that considers both sales and diversity. In addition, we observe that using the problem decomposition method based on a problem structure can lead to a better solution with the quantum annealer in comparison with the existing problem decomposition method.

Motivated by the ability that visualizations have for explaining complex relationships, we revisit an alternative and efficient algorithm for visualizing relationships between objects. QAPgrid was proposed to solve the problem of allocating objects in a grid. The algorithm uses as its mathematical model the NP-hard Quadratic Assignment Problem. We implemented an efficient Memetic Algorithm for solving the layout optimization problem. The algorithm has been previously tested on a variety of datasets with good results. In this chapter, we explore the algorithm’s potential for analysing social networks. In particular, we examined the collaboration network created around the artificial world of the Marvel Universe comic books. We show how the algorithm can generate accurate and informative visualizations for analysing complex graphs. Furthermore, to demonstrate an alternative use of the algorithm, we analyse and visualize products (wines) and customers (telecom clients). In doing so, we show how the algorithm is suitable for the analysis of different types of objects organized as a network.

Leonhard Euler introduced the concept of Graph Theory in his paper about the seven bridges of Konigsberg published in 1736. It is the study of pair-wise relationships between objects. Each object is represented using a vertex, and in case of a relationship between a pair of vertices, they will be connected using an edge. In this dissertation, graph theory is used to study several important combinatorial optimization problems. In chapter 2, we study the multi-dimensional assignment problem using its underlying hypergraphs. It will be shown how the MAP can be represented by a k-partite graph and how any solution to MAP is associated to a k-clique in the respective k-partite graph. Two heuristics are proposed to solve the MAP and computational studies are performed to compare the performance of the proposed methods with exact solutions. On the heels of chapter 2, a new branch-and-bound method is proposed to solve the problem of finding all k-cliques in a k-partite graph in chapter 3. The new method utilizes bitsets as the datastructure to represent graph data. A new pruning method is introduced in BitCLQ, and CPU instructions are used to improve the performance of the branch-and-bound method. BitCLQ gains up to 300% speed up over existing methods. In chapter 4, two new heuristics to solve decomposable cost MAP’s are proposed. The proposed heuristic are based on the partitioning of the underlying graph representing the MAP. In the first heuristic method, MAP’s are partitioned into several smaller MAP’s with the same dimensial

Hyper-heuristics are optimization techniques for solving hard combinatorial problems. Their main feature is that their design involves an important decoupling of the search components from the problem domain ones. This allows them to extend their applicability to different problem domains without major redesign, unlike traditional methods such as metaheuristics. In this work, a hyper-heuristic is evaluated for a transportation problem. The implemented hyper-heuristic uses a greedy operator, and it implements an adapter layer that would allow it to be used in other similar problems. Experimental results shows balanced solution quality and CPU time performance, regarding other metaheuristics in literature.

The real world problems in the supply-chain domain are generally constrained and combinatorial in nature. Several nature-/bio-/socio-inspired metaheuristic methods have been proposed so far solving such problems. An emerging metaheuristic methodology referred to as Cohort Intelligence (CI) in the socio-inspired optimization domain is applied in order to solve three selected combinatorial optimization problems. The problems considered include a new variant of the assignment problem which has applications in healthcare and inventory management, a sea-cargo mix problem and a cross-border shipper selection problem. In each case, we use two benchmarks for evaluating the effectiveness of the CI method in identifying optimal solutions. To assess the quality of solutions obtained by using CI, we do comparative testing of its performance against solutions generated by using CPLEX. Furthermore, we also compare the performance of the CI method to that of specialized multi-random-start local search optimization methods that can be used to find solutions to these problems. The results are robust with a reasonable computational time and accuracy.

The quadratic assignment problem (QAP) is an NP-hard combinatorial optimization problem with a wide variety of applications. Biogeography-based optimization (BBO), a relatively new optimization technique based on the biogeography concept, uses the idea of migration strategy of species to derive algorithm for solving optimization problems. It has been shown that BBO provides performance on a par with other optimization methods. A classical BBO algorithm employs the mutation operator as its diversification strategy. However, this process will often ruin the quality of solutions in QAP. In this paper, we propose a hybrid technique to overcome the weakness of classical BBO algorithm to solve QAP, by replacing the mutation operator with a tabu search procedure. Our experiments using the benchmark instances from QAPLIB show that the proposed hybrid method is able to find good solutions for them within reasonable computational times. Out of 61 benchmark instances tested, the proposed method is able to obtain the best known solutions for 57 of them.

The Job-Shop Scheduling Problem (JSSP) is a well-known and one of the challenging combinatorial optimization problems and falls in the NP-complete problem class. This paper presents an algorithm based on integrating Genetic Algorithms and Simulated Annealing methods to solve the Job Shop Scheduling problem. The procedure is an approximation algorithm for the optimization problem i.e. obtaining the minimum makespan in a job shop. The proposed algorithm is based on Genetic algorithm and simulated annealing. SA is an iterative well known improvement to combinatorial optimization problems. The procedure considers the acceptance of cost-increasing solutions with a nonzero probability to overcome the local minima. The problem studied in this research paper moves around the allocation of different operation to the machine and sequencing of those operations under some specific sequence constraint.

This paper concerns the design of optimized single-finger keyboard layouts on smartphones. In the literature, the optimization problem associated with assigning characters to keys on a single-finger keyboard is denoted as single-finger keyboard layout problem (SK-QAP), which can be seen as a variant of the quadratic assignment problem (QAP), a classical combinatorial optimization problem. To solve it, we propose a simple yet effective local search-based metaheuristic which is composed of three neighborhood structures. Two of them were previously applied to solve the SK-QAP, whereas the third one consists of an adaptation of a QAP neighborhood and it was introduced in this work. In addition, two perturbation mechanisms were developed as diversification procedures and together with the latter neighborhood structure, they revealed to be highly beneficial for improving the performance of the algorithm. Computational experiments were carried out on benchmark instances for English, French, Italian and Spanish. The results obtained were extremely competitive both in terms of solution quality and CPU time, such that all best known solutions were found in a matter of seconds. Moreover, we developed and solved benchmark instances for Portuguese, which currently has more than 230 million speakers, as a first or second language, and also uses the Latin alphabet. We have also proposed and solved bilingual instances, combining English, one of the top spoken languages in the world, with each of the remaining four ones. In addition, we quantify the potential practical benefits of adopting alternative and smartphone-oriented optimized single-finger keyboards, when compared to well-known layouts, namely QWERTY and AZERTY, for the five languages and bilingual variants considered. Finally, we show the efficiency of the proposed algorithm when generating layouts based on other existing arrangements, namely Metropolis and FITALY.

International audience; The graph edit distance (GED) is a widely used distance measure for attributed graphs. It has recently been shown that the problem of computing GED, which is a NP-hard optimization problem, can be formulated as a quadratic assignment problem (QAP). This formulation is useful, since it allows to derive well performing approximative heuristics for GED from existing techniques for QAP. In this paper, we focus on the case where the edit costs that underlie GED are quasimetric. This is the case in many applications of GED. We show that, for quasimetric edit costs, it is possible to reduce the size of the corresponding QAP formulation. An empirical evaluation shows that this reduction significantly speeds up the QAP-based approximative heuristics for GED.

Algorithms for data visualizations are essential tools for transforming data into useful narratives. Unfortunately, very few visualization algorithms can handle the large datasets of many real-world scenarios. In this study, we address the visualization of these datasets as a Multi-Objective Optimization Problem. We propose mQAPViz, a divide-and-conquer multi-objective optimization algorithm to compute large-scale data visualizations. Our method employs the Multi-Objective Quadratic Assignment Problem (mQAP) as the mathematical foundation to solve the visualization task at hand. The algorithm applies advanced sampling techniques originating from the field of machine learning and efficient data structures to scale to millions of data objects. The algorithm allocates objects onto a 2D grid layout. Experimental results on real-world and large datasets demonstrate that mQAPViz is a competitive alternative to existing techniques., Proceeding GECCO 18 Proceedings of the Genetic and Evolutionary Computation Conference. Pages 737-744 Kyoto, Japan - July 15 - 19, 2018

Inverse problems correspond to a certain type of optimization problems formulated over appropriate input distributions. Recently, there has been a growing interest in understanding the computational hardness of these optimization problems, not only in the worst case, but in an average-complexity sense under this same input distribution.In this revised note, we are interested in studying another aspect of hardness, related to the ability to learn how to solve a problem by simply observing a collection of previously solved instances. These ‘planted solutions’ are used to supervise the training of an appropriate predictive model that parametrizes a broad class of algorithms, with the hope that the resulting model will provide good accuracy-complexity tradeoffs in the average sense.We illustrate this setup on the Quadratic Assignment Problem, a fundamental problem in Network Science. We observe that data-driven models based on Graph Neural Networks offer intriguingly good performance, even in regimes where standard relaxation based techniques appear to suffer.

Optimal flight gate assignment is a highly relevant optimization problem from airport management. Among others, an important goal is the minimization of the total transit time of the passengers. The corresponding objective function is quadratic in the binary decision variables encoding the flight-to-gate assignment. Hence, it is a quadratic assignment problem being hard to solve in general. In this work we investigate the solvability of this problem with a D-Wave quantum annealer. These machines are optimizers for quadratic unconstrained optimization problems (QUBO). Therefore the flight gate assignment problem seems to be well suited for these machines. We use real world data from a mid-sized German airport as well as simulation based data to extract typical instances small enough to be amenable to the D-Wave machine. In order to mitigate precision problems, we employ bin packing on the passenger numbers to reduce the precision requirements of the extracted instances. We find that, for the instances we investigated, the bin packing has little effect on the solution quality. Hence, we were able to solve small problem instances extracted from real data with the D-Wave 2000Q quantum annealer., Comment: Updated figure 2