Search

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

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

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

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

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

The transportation and storage of dangerous goods are gradually increasing with the rapid development of China's economy. To ensure safety and increase the operational efficiency of warehouses, we propose a four-door dangerous goods warehouse and a kind of route planning method for forklifts in the newly proposed warehouse. The main innovation of this study is to revolutionize the warehouse design through elevating the routing optimization problem of two forklifts operating in the four-door warehouse considered as a quadratic assignment problem (QAP). Theoretically, the classic particle swarm algorithm (PSO) is used to develop a unique genetic-discrete particle swarm algorithm (DPSO) to solve the proposed QAP. For the simulation, this study utilizes the database from real dangerous goods warehouse using the proposed genetic DPSO algorithm, after which it compares the results with the classic DPSO algorithm and other mathematical calculations. In conclusion, the four-door dangerous goods warehouse concept can improve the efficiency of warehouse management and reduce the cost of management under the condition of maintaining the original safety level, which provides a train of thought for the reform of the dangerous goods warehouse. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Optimization problems over permutation matrices appear widely in facility layout, chip design, scheduling, pattern recognition, computer vision, graph matching, etc. Since this problem is NP-hard due to the combinatorial nature of permutation matrices, we relax the variable to be the more tractable doubly stochastic matrices and add an Lp-norm (0 < p < 1) regularization term to the objective function. The optimal solutions of the Lp-regularized problem are the same as the original problem if the regularization parameter is sufficiently large. A lower bound estimation of the nonzero entries of the stationary points and some connections between the local minimizers and the permutation matrices are further established. Then we propose an Lp regularization algorithm with local refinements. The algorithm approximately solves a sequence of Lp regularization subproblems by the projected gradient method using a nonmonotone line search with the Barzilai{Borwein step sizes. Its performance can be further improved if it is combined with certain local search methods, the cutting plane techniques as well as a new negative proximal point scheme. Extensive numerical results on QAPLIB and the bandwidth minimization problem show that our proposed algorithms can often find reasonably high quality solutions within a competitive amount of time. [ABSTRACT FROM AUTHOR]

The computational power requirements of real-world optimization problems begin to exceed the general performance of the Central Processing Unit (CPU). The modeling of such problems is in constant evolution and requires more computational power. Solving them is expensive in computation time and even metaheuristics, well known for their eficiency, begin to be unsuitable for the increasing amount of data. Recently, thanks to the advent of languages such as CUDA, the development of parallel metaheuristics on Graphic Processing Unit (GPU) platform to solve combinatorial problems such as the Quadratic Assignment Problem (QAP) has received a growing interest. It is one of the most studied NP-hard problems and it is known for its high computational cost. In this paper, we survey several of the most important metaheuristics approaches for the QAP and we focus our survey on parallel metaheuristics using the GPU. [ABSTRACT FROM AUTHOR]

This work is related to the combinatorial data analysis problem of seriation used for data visualization and exploratory analysis. Seriation re-sequences the data, so that more similar samples or objects appear closer together, whereas dissimilar ones are further apart. Despite the large number of current algorithms to realize such re-sequencing, there has not been a systematic way for analyzing the resulting sequences, comparing them, or fusing them to obtain a single unifying one. We propose a new positional proximity measure that evaluates the similarity of two arbitrary sequences based on their agreement on pairwise positional information of the sequenced objects. Furthermore, we present various statistical properties of this measure as well as its normalized version modeled as an instance of the generalized correlation coefficient. Based on this measure, we define a new procedure for consensus seriation that fuses multiple arbitrary sequences based on a quadratic assignment problem formulation and an efficient way of approximating its solution. We also derive theoretical links with other permutation distance functions and present their associated combinatorial optimization forms for consensus tasks. The utility of the proposed contributions is demonstrated through the comparison and fusion of multiple seriation algorithms we have implemented, using many real-world datasets from different application domains. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Inspired by the idea of interacting intelligent agents of a multi-agent system, we introduce a multi-agent based optimization method applied to the quadratic assignment problem (MAOM-QAP). MAOM-QAP is composed of several agents (decision-maker agent, local search agents, crossover agents and perturbation agent) which are designed for the purpose of intensified and diversified search activities. With the help of a reinforcement learning mechanism, MAOM-QAP dynamically decides the most suitable agent to activate according to the state of search process. Under the coordination of the decision-maker agent, the other agents fulfill dedicated search tasks. The performance of the proposed approach is assessed on the set of well-known QAP benchmark instances, and compared with the most advanced QAP methods of the literature. The ideas proposed in this work are rather general and could be adapted to other optimization tasks. This work opens the way for designing new distributed intelligent systems for tackling other complex search problems. [ABSTRACT FROM AUTHOR]

The quadratic assignment problem (QAP) is one of the most studied NP-hard problems with various practical applications. In this work, we propose a powerful population-based memetic algorithm (called BMA) for QAP. BMA integrates an effective local optimization algorithm called Breakout Local Search (BLS) within the evolutionary computing framework which itself is based on a uniform crossover, a fitness-based pool updating strategy and an adaptive mutation procedure. Extensive computational studies on the set of 135 well-known benchmark instances from the QAPLIB revealed that the proposed algorithm is able to attain the best-known results for 133 instances and thus competes very favorably with the current most effective QAP approaches. A study of the search landscape and crossover operators is also proposed to shed light on the behavior of the algorithm. [ABSTRACT FROM AUTHOR]

In this paper we propose the graduated nonconvexity and concavity procedure (GNCCP) as a general optimization framework to approximately solve the combinatorial optimization problems defined on the set of partial permutation matrices. GNCCP comprises two sub-procedures, graduated nonconvexity which realizes a convex relaxation and graduated concavity which realizes a concave relaxation. It is proved that GNCCP realizes exactly a type of convex-concave relaxation procedure (CCRP), but with a much simpler formulation without needing convex or concave relaxation in an explicit way. Actually, GNCCP involves only the gradient of the objective function and is therefore very easy to use in practical applications. Two typical related NP-hard problems, partial graph matching and quadratic assignment problem (QAP), are employed to demonstrate its simplicity and state-of-the-art performance. [ABSTRACT FROM AUTHOR]

Minimization with orthogonality constraints (e.g., $$X^\top X = I$$ ) and/or spherical constraints (e.g., $$\Vert x\Vert _2 = 1$$ ) has wide applications in polynomial optimization, combinatorial optimization, eigenvalue problems, sparse PCA, p-harmonic flows, 1-bit compressive sensing, matrix rank minimization, etc. These problems are difficult because the constraints are not only non-convex but numerically expensive to preserve during iterations. To deal with these difficulties, we apply the Cayley transform—a Crank-Nicolson-like update scheme—to preserve the constraints and based on it, develop curvilinear search algorithms with lower flops compared to those based on projections and geodesics. The efficiency of the proposed algorithms is demonstrated on a variety of test problems. In particular, for the maxcut problem, it exactly solves a decomposition formulation for the SDP relaxation. For polynomial optimization, nearest correlation matrix estimation and extreme eigenvalue problems, the proposed algorithms run very fast and return solutions no worse than those from their state-of-the-art algorithms. For the quadratic assignment problem, a gap 0.842 % to the best known solution on the largest problem “tai256c” in QAPLIB can be reached in 5 min on a typical laptop. [ABSTRACT FROM AUTHOR]

This paper presents a multi-objective local search, where the selection is realized according to the hypervolume contribution of solutions. The HBMOLS algorithm proposed is inspired from the IBEA algorithm, an indicator-based multi-objective evolutionary algorithm proposed by Zitzler and Künzli in 2004, where the optimization goal is defined in terms of a binary indicator defining the selection operator. In this paper, we use the indicator optimization principle, and we apply it to an iterated local search algorithm, using hypervolume contribution indicator as selection mechanism. The methodology proposed here has been defined in order to be easily adaptable and to be as parameter-independent as possible. We carry out a range of experiments on the multi-objective flow shop problem and the multi-objective quadratic assignment problem, using the hypervolume contribution selection as well as two different binary indicators which were initially proposed in the IBEA algorithm. Experimental results indicate that the HBMOLS algorithm is highly effective in comparison with the algorithms based on binary indicators. [ABSTRACT FROM AUTHOR]

Abstract: In this article we provide an exact expression for computing the autocorrelation coefficient and the autocorrelation length of any arbitrary instance of the Quadratic Assignment Problem (QAP) in polynomial time using its elementary landscape decomposition. We also provide empirical evidence of the autocorrelation length conjecture in QAP and compute the parameters and for the 137 instances of the QAPLIB. Our goal is to better characterize the difficulty of this important class of problems to ease the future definition of new optimization methods. Also, the advance that this represents helps to consolidate QAP as an interesting and now better understood problem. [Copyright &y& Elsevier]

Abstract: This paper presents several optimization problems occurring in VLSI interconnect, Networks on Chip (NoC) design and 3D VLSI integration, all possessing closed-form solutions obtained by well-solvable Quadratic Assignment Problems (QAP). The first type of problems deals with the optimal ordering of signals in a bus bundle such that the switching power, delay and noise interference are minimized. We extend a known solution of ordering the signals in a bus bundle to minimize the impact of the first order wire-to-wire parasitic capacitance occurring between adjacent wires into a model accounting for also secondary components of wire-to-wire parasitic capacitances. The second type of problems arises in the mapping of computation tasks into an array of processors sharing a common bus, such as those found in NoC. We show a QAP closed-form solution to the optimal mapping problem which simultaneously minimizes the switching power and the average delay of the bus. The third problem deals with the optimization of 3D VLSI, vertically stacking ordinary ICs. Some of the above problems involve -salesmen Traveling Salesman Problem (TSP), where costs are evaluated for elements located at -distance apart along the tour. We show a simple proof that these are well-solvable problems and obtain their solution. This is then generalized to well-solvable QAPs obtained by superposition of such TSPs. A simple proof shows that if -distance TSPs are well-solvable, so is the QAP obtained by their sum, where the solution of -distance TSPs dominates all the others. [Copyright &y& Elsevier]

Abstract: In this paper some global optimality conditions for general quadratic {0,1} programming problems with linear equality constraints are discussed and then some global optimality conditions for quadratic assignment problems (QAP) are presented. A local optimization method for (QAP) is derived according to the necessary global optimality conditions. A global optimization method for (QAP) is presented by combining the sufficient global optimality conditions, the local optimization method and some auxiliary functions. Some numerical examples are given to illustrate the efficiency of the given optimization methods. [Copyright &y& Elsevier]

In this paper, we deal with the single-row equidistant facility layout problem (SREFLP), which asks to find a one-to-one assignment of n facilities to n locations equally spaced along a straight line so as to minimize the sum of the products of the flows and distances between facilities. We develop a branch-and-bound algorithm for solving this problem. The lower bound is computed first by performing transformation of the flow matrix and then applying the well-known Gilmore-Lawler bounding technique. The algorithm also incorporates a dominance test which allows to drastically reduce redundancy in the search process. The test is based on the use of a tabu search procedure designed to solve the SREFLP. We provide computational results for problem instances of size up to 35 facilities. For a number of instances, the optimal value of the objective function appeared to be smaller than the best value reported in the literature. [ABSTRACT FROM AUTHOR]

Abstract: The mapping of tasks of a parallel program onto nodes of a parallel computing system has a remarkable impact on application performance. In this paper we propose an optimization framework to solve the mapping problem, which takes into account the communication matrix of the application and a cost matrix that depends on the topology of the parallel system. This cost matrix is usually a distance matrix (the classic approach), but we propose a novel definition of the cost criterion, applicable to torus networks, that tries to distribute traffic evenly over the different axes; we call this the Traffic Distribution criterion. As the mapping problem can be seen as a particular instance of the Quadratic Assignment Problem (QAP), we can apply any QAP solver to this problem. In particular, we use a greedy randomized algorithm. Using simulation, we test the performance levels of the optimization-based mappings, and compare them with those of trivial mappings (consecutive, random), in two different environments: single application (one application uses all system resources all the time) and space sharing (several applications run simultaneously, on different system partitions), using systems with 2D and 3D topologies and real application traffic. Experimental results show that some applications do not benefit from optimization-based mappings: those in which there is a match between virtual and physical topologies, and those that carry out massive all-to-all communications. In other cases, optimization-based mappings with the TD criterion provide excellent performance levels. [Copyright &y& Elsevier]

In this paper we study a class of nonconvex quadratically constrained quadratic programming problems generalized from relaxations of quadratic assignment problems. We show that each problem is polynomially solved. Strong duality holds if a redundant constraint is introduced. As an application, a new lower bound is proposed for the quadratic assignment problem. [ABSTRACT FROM AUTHOR]

Abstract: Facility layout design and planning within construction sites are a common construction management problem and regarded as a complex combinatorial problem. To transport heavy materials, tower cranes are needed and should be well located to reduce operating costs and improve overall efficiency. Quadratic assignment problem (QAP), non-linear in nature, has been developed to simulate the material transportation procedure. Applying linear constraint sets, the quadratic problem can be linearized and the problem could be formulated into a mixed-integer-linear programming (MILP) problem solvable by a standard branch-and-bound technique for true optimal results. Numerical findings show that MILP results outperform those optimized by Genetic Algorithms with almost 7% on improving the objective function values in which facilities and locations can be modeled using integer variables. To demonstrate the design flexibility of using MILP formulation, the problem is also extended to non-homogeneous storages where different materials can be stored at a single supply point. [Copyright &y& Elsevier]

In many practical applications, the task is to optimize a non-linear objective function over the vertices of a well-studied polytope as, e.g., the matching polytope or the travelling salesman polytope (TSP). Prominent examples are the quadratic assignment problem and the quadratic knapsack problem; further applications occur in various areas such as production planning or automatic graph drawing. In order to apply branch-and-cut methods for the exact solution of such problems, the objective function has to be linearized. However, the standard linearization usually leads to very weak relaxations. On the other hand, problem-specific polyhedral studies are often time-consuming. Our goal is the design of general separation routines that can replace detailed polyhedral studies of the resulting polytope and that can be used as a black box. As unconstrained binary quadratic optimization is equivalent to the maximum-cut problem, knowledge about cut polytopes can be used in our setting. Other separation routines are inspired by the local cuts that have been developed by Applegate, Bixby, Chvátal and Cook for faster solution of large-scale traveling salesman instances. Finally, we apply quadratic reformulations of the linear constraints as proposed by Helmberg, Rendl and Weismantel for the quadratic knapsack problem. By extensive experiments, we show that a suitable combination of these methods leads to a drastic speedup in the solution of constrained quadratic 0–1 problems. We also discuss possible generalizations of these methods to arbitrary non-linear objective functions. [ABSTRACT FROM AUTHOR]

We consider semidefinite programming relaxations of the quadratic assignment problem, and show how to exploit group symmetry in the problem data. Thus we are able to compute the best known lower bounds for several instances of quadratic assignment problems from the problem library: (Burkard et al. in J Global Optim 10:291–403, 1997). [ABSTRACT FROM AUTHOR]

The facility layout design problem is an extensively studied research problem and belongs to nonpolynomial hard (NP-hard) combinatorial optimization problem. Quadratic assignment problem (QAP) is one of the formulations that is investigated for facility layout design because of its wide applicability. Ant colony optimization (ACO), a biologically inspired heuristic has centered on solving the QAP by achieving approximation as good as possible. This paper presents a population-based hybrid ant system (PHAS), which is an extension of the hybrid ant system (HAS) in which the size of the ant colony has been fixed. The performance of the proposed ant algorithm for QAP is compared with the existing metaheuristic implementations such as tabu search, reactive tabu search, simulated annealing, genetic hybrid method, HAS, and max–min ant system. The experimental results show that the proposed PHAS perform significantly better than the other existing algorithms of QAP. [ABSTRACT FROM AUTHOR]

In this paper, an efficient hybrid genetic algorithm (HGA) and its variants for the well-known combinatorial optimization problem, the quadratic assignment problem (QAP) are discussed. In particular, we tested our algorithms on a special type of QAPs, the structured quadratic assignment problems. The results from the computational experiments on this class of problems demonstrate that HGAs allow to achieve near-optimal and (pseudo-)optimal solutions at very reasonable computation times. The obtained results also confirm that the hybrid genetic algorithms are among the most suitable heuristic approaches for this type of QAPs. [ABSTRACT FROM AUTHOR]

The quadratic assignment problem (QAP) is a well-known combinatorial optimization problem with a wide variety of applications, prominently including the facility location problem. The acknowledged difficulty of the QAP has made it the focus of many metaheuristic solution approaches. In this paper, we show the benefit of utilizing strategic diversification within the tabu search (TS) framework for the QAP, by incorporating several diversification and multistart TS variants. Computational results for an extensive and challenging set of QAP benchmark test problems demonstrate the ability of our TS variants to improve on a classic TS approach that is one of the principal and most extensively used methods for the QAP. We also show that our new procedures are highly competitive with the best recently introduced methods from the literature, including more complex hybrid approaches that incorporate the classic TS method as a subroutine. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents an advanced software system for solving the flexible manufacturing systems (FMS) scheduling in a job-shop environment with routing flexibility, where the assignment of operations to identical parallel machines has to be managed, in addition to the traditional sequencing problem. Two of the most promising heuristics from nature for a wide class of combinatorial optimization problems, genetic algorithms (GA) and ant colony optimization (ACO), share data structures and co-evolve in parallel in order to improve the performance of the constituent algorithms. A modular approach is also adopted in order to obtain an easy scalable parallel evolutionary-ant colony framework. The performance of the proposed framework on properly designed benchmark problems is compared with effective GA and ACO approaches taken as algorithm components. [Copyright &y& Elsevier]

Abstract  Augmented Lagrangian coordination (ALC) is a provably convergent coordination method for multidisciplinary design optimization (MDO) that is able to treat both linking variables and linking functions (i.e. system-wide objectives and constraints). Contrary to quasi-separable problems with only linking variables, the presence of linking functions may hinder the parallel solution of subproblems and the use of the efficient alternating directions method of multipliers. We show that this unfortunate situation is not the case for MDO problems with block-separable linking constraints. We derive a centralized formulation of ALC for block-separable constraints, which does allow parallel solution of subproblems. Similarly, we derive a distributed coordination variant for which subproblems cannot be solved in parallel, but that still enables the use of the alternating direction method of multipliers. The approach can also be used for other existing MDO coordination strategies such that they can include block-separable linking constraints. [ABSTRACT FROM AUTHOR]

In this paper we propose a reduced vertex result for the robust solution of uncertain semidefinite optimization problems subject to interval uncertainty. If the number of decision variables is m and the size of the coefficient matrices in the linear matrix inequality constraints is n× n, a direct vertex approach would require satisfaction of 2 n( m+1)( n+1)/2 vertex constraints: a huge number, even for small values of n and m. The conditions derived here are instead based on the introduction of m slack variables and a subset of vertex coefficient matrices of cardinality 2 n−1, thus reducing the problem to a practically manageable size, at least for small n. A similar size reduction is also obtained for a class of problems with affinely dependent interval uncertainty. [ABSTRACT FROM AUTHOR]

This paper considers the homogeneous packing of binary hard spheres in an equimolar stoichiometry, and postulates the densest packing at each sphere size ratio. Monte Carlo simulated annealing optimizations are seeded with all known atomic inorganic crystal structures, and the search is performed within the degrees of freedom associated with each homogeneous AB structure type. Structures isopointal to the FeB structure type are found to have the highest packing fraction at all sphere size ratios. The optimized structures match or improve on the best previously demonstrated packings of this type, and show that compound structures can pack more densely than segregated close-packed structures at all radius ratios less than 0.62. [ABSTRACT FROM AUTHOR]

Abstract: Biological computing provides a promising approach to attacking computationally intractable problems. The quadratic assignment problem (QAP) is a well-known NP-hard combinatorial optimization problem. This paper addresses the problem of how to solve QAP under the Adleman–Lipton-sticker model. A theoretically efficient DNA algorithm for solving QAP is proposed, which is executed by performing O(Kn 4) operations on test tubes of DNA molecular strands with n 2 + K +1 bit regions, where n is the number of facilities, and K is the length of the binary representation of an upper bound on the objective function. With the rapid progress of molecular biology techniques, the proposed algorithm might be of practical use in treating medium-sized instances of QAP. [Copyright &y& Elsevier]

This paper presents a new unified modeling and heuristic solution framework for vehicle-routing problems (VRPs) with complex side constraints. The work is focused on strong modeling capabilities as well as efficient solution procedures to be used in all kinds of metaheuristics. From the modeling point of view, the framework covers a variety of standard VRP types with classical constraints such as capacity, distance, route length, time window, pairing, and precedence constraints, but also nonstandard "rich" VRPs. From the methodological point of view, local search (LS) is the key solver engine to be used in heuristic solution procedures. First and foremost, the framework introduces two generic techniques for the efficient exploration of edge- and node-exchange neighborhoods. New preprocessing methods allow O(nk) neighborhoods to be searched in time complexity O(nk), i.e., without an additional effort for feasibility testing in the worst case. Moreover, for accelerating LS in the average case, Irnich et al. [Irnich, S., B. Funke, T. Grünert. 2006. Sequential search and its application to vehiclerouting problems. Comput. Oper. Res. 33 2405-2429] have introduced sequential search that is here adapted to cope with rich VRPs (complex side constraints). Computational tests on different types of VRPs indicate that the proposed techniques are highly efficient. Sequential search procedures outperform the currently most efficient search methods, which are based on lexicographic search, on large-scale instances and for nearly all types of neighborhoods by factors of between 10 and 1,000. [ABSTRACT FROM AUTHOR]

This article uses a hybrid optimization approach to solve the discrete facility layout problem (FLP), modelled as a quadratic assignment problem (QAP). The idea of this approach design is inspired by the ant colony meta-heuristic optimization method, combined with the extended great deluge (EGD) local search technique. Comparative computational experiments are carried out on benchmarks taken from the QAP-library and from real life problems. The performance of the proposed algorithm is compared to construction and improvement heuristics such as H63, HC63-66, CRAFT and Bubble Search, as well as other existing meta-heuristics developed in the literature based on simulated annealing (SA), tabu search and genetic algorithms (GAs). This algorithm is compared also to other ant colony implementations for QAP. The experimental results show that the proposed ant colony optimization/extended great deluge (ACO/EGD) performs significantly better than the existing construction and improvement algorithms. The experimental results indicate also that the ACO/EGD heuristic methodology offers advantages over other algorithms based on meta-heuristics in terms of solution quality. [ABSTRACT FROM AUTHOR]

In this study, a fuzzy multi-item economic order quantity (EOQ) problem is solved by employing four different fuzzy ranking methods. All of the parameters of the multi-item EOQ problem are defined as triangular fuzzy numbers. Fuzzy ranking methods are used to rank the fuzzy objective values and to handle the constraints in the model. The results obtained by employing different fuzzy ranking methods are also compared. [ABSTRACT FROM AUTHOR]

We introduce a convex relaxation approach for the quadratic assignment problem to the field of computer vision. Due to convexity, a favourable property of this approach is the absence of any tuning parameters and the computation of high-quality combinatorial solutions by solving a mathematically simple optimization problem. Furthermore, the relaxation step always computes a tight lower bound of the objective function and thus can additionally be used as an efficient subroutine of an exact search algorithm. We report the results of both established benchmark experiments from combinatorial mathematics and random ground-truth experiments using computer-generated graphs. For comparison, a deterministic annealing approach is investigated as well. Both approaches show similarly good performance. In contrast to the convex approach, however, the annealing approach yields no problem relaxation, and four parameters have to be tuned by hand for the annealing algorithm to become competitive. [Copyright &y& Elsevier]

The author offers his views on discrete optimization. According to him, the obvious analogies between quadratic assignment problems with a sum objective and quadratic assignment problems with a bottleneck objective led to an investigation on the common mathematical background of both problems. Some of the factors that makes the optimization attractive are the links to other mathematical areas like algebra and numerical analysis, geometry and combinatorics.

Abstract: We develop an optimal algorithm for the numerical solution of semi-coercive variational inequalities by combining dual-primal FETI algorithms with recent results for bound and equality constrained quadratic programming problems. The discretized version of the model problem, obtained by using the FETI-DP methodology, is reduced by the duality theory of convex optimization to a quadratic programming problem with bound and equality constraints, which is solved by a new algorithm with a known rate of convergence given in terms of the spectral condition number of the quadratic problem. We present convergence bounds that guarantee the scalability of the algorithm. These results are confirmed by numerical experiments. [Copyright &y& Elsevier]

We consider the NP-hard problem of finding a minimum norm vector in n-dimensional real or complex Euclidean space, subject to m concave homogeneous quadratic constraints. We show that a semidefinite programming (SDP) relaxation for this nonconvex quadratically constrained quadratic program (QP) provides an O(m²) approximation in the real case and an O(m) approximation in the complex case. Moreover, we show that these bounds are tight up to a constant factor. When the Hessian of each constraint function is of rank 1 (namely, outer products of some given so-called steering vectors) and the phase spread of the entries of these steering vectors are bounded away from π/2, we establish a certain "constant factor" approximation (depending on the phase spread but independent of m and n) for both the SDP relaxation and a convex QP restriction of the original NP-hard problem. Finally, we consider a related problem of finding a maximum norm vector subject to m convex homogeneous quadratic constraints. We show that an SDP relaxation for this nonconvex QP provides an O(1/ ln(m)) approximation, which is analogous to a result of Nemirovski et al. [Math. Program., 86 (1999), pp. 463-473] for the real case. [ABSTRACT FROM AUTHOR]

Abstract: Ant algorithm is a multi-agent systems inspired by the behaviors of real ant colonies function to solve optimization problems. In this paper an ant colony optimization algorithm is developed to solve the quadratic assignment problem. The local search process of the algorithm is simulated annealing. In the exploration of the search space, the evaluation of pheromones which are laid on the ground by ants is used. In this work, the algorithm is analyzed by using current problems in the literature and is compared with other metaheuristics. [Copyright &y& Elsevier]

Recently, genetic algorithms (GAs) and their hybrids have achieved great success in solving difficult combinatorial optimization problems. In this paper, the issues related to the performance of the genetic search in the context of the grey pattern problem (GPP) are discussed. The main attention is paid to the investigation of the solution recombination, i.e., crossover operators which play an important role by developing robust genetic algorithms. We implemented seven crossover operators within the hybrid genetic algorithm (HGA) framework, and carried out the computational experiments in order to test the influence of the recombination operators to the genetic search process. We examined the one point crossover, the uniform like crossover, the cycle crossover, the swap path crossover, and others. A so-called multiple parent crossover based on a special type of recombination of several solutions was tried, too. The results obtained from the experiments on the GPP test instances demonstrate promising efficiency of the swap path and multiple parent crossovers. [ABSTRACT FROM AUTHOR]

The vertex coloring problem has been the subject of extensive research for many years. Driven by application potential as well as computational challenge, a variety of methods have been proposed for this difficult class of problems. Recent successes in the use of the unconstrained quadratic programming (UQP) model as a unified framework for modeling and solving combinatorial optimization problems have motivated a new approach to the vertex coloring problem. In this paper we present a UQP approach to this problem and illustrate its attractiveness with preliminary computational experience. [ABSTRACT FROM AUTHOR]

Abstract: We construct a mixed analog/digital chaotic neuro-computer prototype system for quadratic assignment problems (QAPs). The QAP is one of the difficult -hard problems, and includes several real-world applications. Chaotic neural networks have been used to solve combinatorial optimization problems through chaotic search dynamics, which efficiently searches optimal or near optimal solutions. However, preliminary experiments have shown that, although it obtained good feasible solutions, the Hopfield-type chaotic neuro-computer hardware system could not obtain the optimal solution of the QAP. Therefore, in the present study, we improve the system performance by adopting a solution construction method, which constructs a feasible solution using the analog internal state values of the chaotic neurons at each iteration. In order to include the construction method into our hardware, we install a multi-channel analog-to-digital conversion system to observe the internal states of the chaotic neurons. We show experimentally that a great improvement in the system performance over the original Hopfield-type chaotic neuro-computer is obtained. That is, we obtain the optimal solution for the size-10 QAP in less than 1000 iterations. In addition, we propose a guideline for parameter tuning of the chaotic neuro-computer system according to the observation of the internal states of several chaotic neurons in the network. [Copyright &y& Elsevier]

Goal programming is a commonly used technique for modelling and solving multiple objective optimization problems. It has been successfully applied to many diverse real-life problems in engineering design and optimization. One of the first attempts is made in this article to solve preemptive goal programming (PGP) problems by using a simulated annealing (SA) algorithm. The developed algorithm can be applied to non-linear, linear, integer and combinatorial goal programs. However, the main concentration is on non-linear programs, mainly due to the difficulty in solving these programs with the classical approaches. Several test problems are solved in order to test the suitability of SA in solving preemptive goal programs. It is observed that the SA algorithm is a suitable candidate to solve goal programs. The method can easily be applied to any kind of PGP problem. [ABSTRACT FROM AUTHOR]

The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Very few instances of this problem can be solved in polynomial time. In this paper we address the problem of allocating rooms among people in a suitable shape of corridor with some constraints of undesired neighborhood. We give a linear time algorithm for this problem that we formulate as a QAP. [Copyright &y& Elsevier]

This paper describes and experimentally compares five rather different multistart tabu search strategies for the unconstrained binary quadratic optimization problem: a random restart procedure, an application of a deterministic heuristic to specially constructed subproblems, an application of a randomized procedure to the full problem, a constructive procedure using tabu search adaptive memory, and an approach based on solving perturbed problems. In the solution improvement phase a modification of a standard tabu search implementation is used. A computational trick applied to this modification – mapping of the current solution to the zero vector – allowed to significantly reduce the time complexity of the search. Computational results are provided for the 25 largest problem instances from the OR-Library and, in addition, for the 18 randomly generated larger and more dense problems. For 9 instances from the OR-Library new best solutions were found. [ABSTRACT FROM AUTHOR]

We prove a sufficient global optimality condition for the problem of minimizing a quadratic function subject to quadratic equality constraints where the variables are allowed to take values -1 and 1. We extend the condition to quadratic problems with matrix variables and orthonormality constraints, and in particular to the quadratic assignment problem. [ABSTRACT FROM AUTHOR]

In this paper, we propose an improved hybrid genetic algorithm (IHGA). It uses a robust local improvement procedure as well as an effective restart mechanism that is based on so-called ‘shift mutations’. IHGA has been applied to the well-known combinatorial optimization problem, the quadratic assignment problem (QAP). The results obtained from the experiments on different QAP instances show that the proposed algorithm appears to be superior to other approaches that are among the best algorithms for the QAP. The high efficiency of our algorithm is also corroborated by the fact that new record-breaking solutions were obtained for a number of large real-life instances. [Copyright &y& Elsevier]