Search

We commence an algorithmic study of Bulk-Robustness, a new model of robustness in combinatorial optimization. Unlike most existing models, Bulk-Robust combinatorial optimization features a highly nonuniform failure model. Instead of an interdiction budget, Bulk-Robust counterparts provide an explicit list of interdiction sets, comprising the admissible set of scenarios, thus allowing to model correlations between failures of different components in the system, interdiction sets of variable cardinality and more. The resulting model is suitable for capturing failures of complex structures in the system. We provide complexity results and approximation algorithms for Bulk-Robust counterparts of the Minimum Matroid Basis problems and the Shortest Path problem. Our results rely on various techniques, and outline the rich and heterogeneous combinatorial structure of Bulk-Robust optimization., Mathematical Programming, 149 (1-2), ISSN:0025-5610, ISSN:1436-4646

The quadratic assignment problem (QAP) is a well-known optimization problem that has many applications in various engineering areas. Due to its NP-hard nature, rather than the exact methods, heuristic and metaheuristic approaches are commonly adapted. In this study, we propose an improved hybrid genetic algorithm which mainly combines a greedy heuristic, and a simulated annealing algorithm with the classical genetic algorithm. We test our algorithm on the well-known benchmark for the QAP and compare the results with four different algorithms: a greedy algorithm, simulated annealing algorithm (SA), demon algorithm (DA), and a classical genetic algorithm (GA). The results of the experiments validate that our hybridization significantly improves the performance of the algorithms comparing to their standalone executions.

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.

Το Shortest Superstring Problem (SSP) είναι ένα πρόβλημα συνδυαστικής βελτιστοποίησης που έχει προσελκύσει το ενδιαφέρων πολλών ερευνητών, λόγω των εφαρμογών του. Μπορεί να χρησιμοποιηθεί σε προβλήματα Υπολογιστικής Μοριακής Βιολογίας όπως η αλληλούχιση του DNA και σε προβλήματα της επιστήμης υπολογιστών όπως η συμπίεση δεδομένων. Το SSP είναι ένα NP-hard πρόβλημα. Ένα άρθρο ανασκόπησης για το SSP παρουσιάζεται στο πρώτο κεφάλαιο της παρούσας διατριβής με έναν περιεκτικό και σαφή τρόπο, καλύπτοντας ολόκληρη τη σχετική βιβλιογραφία, αναδεικνύοντας την κατακτημένη γνώση και βοηθώντας στην μελλοντική έρευνα.Η μέθοδος GRASP (Greedy Randomized Adaptive Search Procedure) είναι μια επαναληπτική ευρετική μέθοδος για συνδυαστική βελτιστοποίηση. Η μέθοδος Path Relinking (PR) αποτελεί έναν τρόπο ενοποίησης των στρατηγικών εντατικοποίησης και διαφοροποίησης στην αναζήτηση για βέλτιστες λύσεις. Η PR στα πλαίσια του GRASP εισήχθη ως μηχανισμός μνήμης για την αξιοποίηση των δεδομένων από καλές λύσεις που έχουν ήδη βρεθεί. Στο δεύτερο κεφάλαιο, παρουσιάζεται η υλοποίηση της μεθόδου GRASP με PR για το SSP. Η νέα μέθοδος λύνει στιγμιότυπα μεγάλης κλίμακας και υπερτερεί του φυσικού άπληστου αλγόριθμου στη συντριπτική πλειοψηφία των στιγμιοτύπων που δοκιμάστηκαν. Η προτεινόμενη μέθοδος είναι ικανή να παράγει πολλαπλές λύσεις κοντά στο βέλτιστο, γεγονός το οποίο είναι σημαντικό για την πρακτική της αλληλούχισης του DNA και επιτρέπει μια φυσική και εύκολη παράλληλη υλοποίηση. Ένα σύνολο αναφοράς στιγμιοτύπων με γνωστή βέλτιστη λύση κατασκευάστηκε χρησιμοποιώντας μια νέα Διατύπωση Ακέραιου Προγραμματισμού (Integer Programming Formulation) για το SSP.Η οικογένεια των γράφων επικάλυψης αποτελεί ένα κατάλληλο είδος δομής δεδομένων για την περίπτωση του SSP. Έχουν εφαρμογές στην αλληλούχιση γονιδιώματος, στην συμπίεση ακολουθιών και στον χρονοπρογραμματισμό μηχανών. Ένας κατευθυνόμενος γράφος με βάρη είναι γράφος επικάλυψης αν υπάρχει ένα σύνολο από ακολουθίες, οι οποίες βρίσκονται σε ένα προς ένα αντιστοιχία με τις κορυφές του γράφου, έτσι ώστε κάθε βάρος του γράφου να ισούται με την επικάλυψη μεταξύ των αντίστοιχων ακολουθιών. Στο τρίτο κεφάλαιο της παρούσας διατριβής, παρουσιάζεται ένα θεώρημα χαρακτηρισμού των γράφων επικάλυψης και ο αντίστοιχος αλγόριθμος αναγνώρισής τους.Το Quadratic Assignment Problem (QAP) είναι ένα από τα δυσκολότερα προβλήματα συνδυαστικής βελτιστοποίησης. Το QAP είναι ένα NP-hard πρόβλημα, ενώ η εύρεση ενός ε-προσεγγιστικού αλγόριθμου για αυτό είναι επίσης δύσκολη. Ο κλασικός άπληστος αλγόριθμος για διακριτά προβλήματα βελτιστοποίησης όπου η βέλτιστη λύση είναι ένα μεγιστοτικό ανεξάρτητο υποσύνολο ενός πεπερασμένου συνόλου βάσης με στοιχεία με βάρη, μπορεί να οριστεί με δύο διαφορετικούς τρόπους που είναι δυϊκοί ο ένας προς το άλλο. Τον άπληστο-εισαγωγής (greedy-in) αλγόριθμο, όπου μια λύση κατασκευάζεται από ένα κενό σύνολο με την εισαγωγή του επόμενου καλύτερου στοιχείου, ενός κάθε φορά, μέχρι να προκύψει μια μη εφικτή λύση και τον άπληστο-εξαγωγής (greedy-out) αλγόριθμο, όπου ξεκινώντας από το σύνολο βάσης, διαγράφεται το επόμενο χειρότερο στοιχείο, ένα κάθε φορά, μέχρι να προκύψει κάποια εφικτή λύση. Έχει αποδειχτεί ότι ενώ ο πρώτος αλγόριθμος παρέχει έναν παράγοντα προσέγγισης για τα προβλήματα μεγιστοποίησης, η απόδοσή του στην χειρότερη περίπτωση δεν είναι φραγμένη για τα προβλήματα ελαχιστοποίησης και το αντίστροφο για τον δεύτερο αλγόριθμο. Στο τέταρτο κεφάλαιο αυτής της διατριβής, παρουσιάζεται ο άπληστος-εξαγωγής αλγόριθμος για το QAP, αφότου αναπτύσσεται ένας συνδυαστικός χαρακτηρισμός των λύσεων του προβλήματος.

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

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

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.

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

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.

Theoretical Computer Science, 745, ISSN:0304-3975

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.

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.

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.

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.

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.

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.

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 Travelling Salesman Problem (TSP) is an NP-hard problem with high number of possible solutions. The complexity increases with the factorial of n nodes in each specific problem. Meta-heuristic algorithms are an optimization algorithm that able to solve TSP problem towards a satisfactory solution. To date, there are many meta-heuristic algorithms introduced in literatures which consist of different philosophies of intensification and diversification. This paper focuses on 6 heuristic algorithms: Nearest Neighbor, Genetic Algorithm, Simulated Annealing, Tabu Search, Ant Colony Optimization and Tree Physiology Optimization. The study in this paper includes comparison of computation, accuracy and convergence.

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.

We study the q -adic assignment problem. We first give an O ( n (q−1)/2) )-approximation algorithm for the Koopmans--Beckman version of the problem, improving upon the result of Barvinok. Then, we introduce a new family of instances satisfying “tensor triangle inequalities” and give a constant factor approximation algorithm for them. We show that many classical optimization problems can be modeled by q -adic assignment problems from this family. Finally, we give several integrality gap examples for the natural LP relaxations of the problem.

This paper addresses the problem of joint power management and radar assignment to detect multiple targets in surveillance region for a distributed mono-static radar network while a low probability of interception (LPI) has been attained. Based on detection probabilities and target location estimates, the targeted problem is formulated as a combinatorial non-convex optimization problem which needs exhaustive search through all assignment schemes to reach optimal solution. Due to NP-hardness and non-convexity of the problem, some relaxations are proposed to transform the problem to a more tractable form. The main problem can be considered from two viewpoints, without information fusion and with information fusion. As another relaxation, we separated power allocation from radar assignments through two sub-problems in which first, the optimum power allocation is obtained for each assignment scheme and second, the target assignment schemes are selected based on the allocated powers. Simulation results show that our proposed algorithms not only guarantee detection performances but also considerably improve LPI specification in comparison with benchmark algorithms.

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.

Accurate fault detection and isolation requires signal processing of measurement signals which are contaminated with noise. Typically, gas turbine faults are revealed by sharp trend shifts in the signals and these trend shifts should be preserved during signal processing. Linear filters can smooth out the sharp trend shifts while removing noise. However, nonlinear filters such as the weighted recursive median (WRM) filters show good noise reduction while preserving key signal features if their integer weights are determined optimally. We propose the ant colony optimization (ACO) method coupled with local search to calculate the integer weights of WRM filters. It is found that the filter weight optimization problem is mathematically equivalent to the quadratic assignment problem which can be solved by ACO. Optimal parameters for the ACO are found using numerical experiments. The WRM filter is demonstrated for abrupt and gradual faults in gas turbines and is found to yield noise reduction of 52–64% for simulated noisy signals considered in this paper.

A new location problem is formulated and solved. It is the continuous version of the grey pattern problem which is a special case of the Quadratic Assignment Problem. The problem is a minimization of a convex function subject to non-convex constraints and has infinitely many optimal solutions. We propose several mathematical programming formulations that are suitable for a multi-start heuristic algorithm. In addition to solving these formulations by the Solver in Excel and Mathematica, a special Nelder–Mead algorithm is proposed. This special algorithm provided the best results. One suggested modification may improve the performance of the Nelder–Mead algorithm for other optimization problems as well.

LibCoopt is an open-source matlab code library which provides a general and convenient tool to approximately solve the combinatorial optimization problems on the set of partial permutation matrices, which are frequently encountered in computer vision, bioinformatics, social analysis, etc. To use the library, the user needs only to give the objective function and its gradient function associated with the problem. Two typical problems, the subgraph matching problem and the quadratic assignment problem, are employed to illustrate how to use the library and also its flexibility on different types of problems.

In this article, we will examine whether the Problem Aware Local Search, an efficient method initially proposed for the DNA Fragment Assembly Problem, can also be used in other application domains and with other optimization problems. The main idea is to maintain the key features of PALS and apply it to different permutation-based combinatorial problems. In order to carry out a comprehensive analysis, we use a wide benchmark of well-known problems with different kinds of variation operators and fitness functions, such as the Quadratic Assignment Problem, the Flow Shop Scheduling Problem, and the Multiple Knapsack Problem. We also discuss the main design alternatives for building an efficient and accurate version of PALS for these problems in a competitive manner. In general, the results show that PALS can achieve high-quality solutions for these problems and do it efficiently.

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.

In this paper, we address continuous, integer and combinatorial k-sum optimization problems. We analyze different formulations of this problem that allow to solve it through the minimization of a relatively small number of minisum optimization problems. This approach provides a general tool for solving a variety of k-sum optimization problems and at the same time, improves the complexity bounds of many ad-hoc algorithms previously reported in the literature for particular versions of this problem. Moreover, the results developed for k-sum optimization have been extended to the more general case of the convex ordered median problem, improving upon existing solution approaches.

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.

We review some complexity results and present a viable heuristic approach based on the Variable Neighborhood Search (VNS) framework for multimode extension of combinatorial optimization problems, such as the the Set Covering Problem (SCP) and the Covering Location Problem (CLP).