Search

Exact computation of graph edit distance (GED) can be solved in exponential time complexity only. A previously introduced approximation framework reduces the computation of GED to an instance of a linear sum assignment problem. Major benefit of this reduction is that an optimal assignment of nodes (including local structures) can be computed in polynomial time. Given this assignment an approximate value of GED can be immediately derived. Yet, since this approach considers local — rather than the global — structural properties of the graphs only, the GED derived from the optimal assignment is suboptimal. The contribution of the present paper is twofold. First, we give a formal proof that this approximation builds an upper bound of the true graph edit distance. Second, we show how the existing approximation framework can be reformulated such that a lower bound of the edit distance can be additionally derived. Both bounds are simultaneously computed in cubic time.

There exist local search landscapes where the evaluation function is an eigenfunction of the graph Laplacian that corresponds to the neighborhood structure of the search space. Problems that display this structure are called “Elementary Landscapes” and they have a number of special mathematical properties. The problems that are not elementary landscapes can be decomposed in a sum of elementary ones. This sum is called the elementary landscape decomposition of the problem. In this paper, we provide the elementary landscape decomposition for the Hamiltonian Path Optimization Problem under two different neighborhoods.

In the last few years, fitness landscape analysis has seen an increase in interest due to the availability of large problem collections and research groups focusing on the development of a wide array of different optimization algorithms for diverse tasks. Instead of being able to rely on a single trusted method that is tuned and tweaked to the application more and more, new problems are investigated, where little or no experience has been collected. In an attempt to provide a more general criterion for algorithm and parameter selection other than "it works better than something else we tried", sophisticated problem analysis and classification schemes are employed. In this work, we combine several of these analysis methods and evaluate the suitability of fitness landscape analysis for the task of algorithm selection.

We present a \(1-\frac{1}{\sqrt{k}}\)-competitive algorithm for the online stochastic generalized assignment problem under the assumption that no item takes up more than \(\frac{1}{k}\) fraction of the capacity of any bin. Items arrive online; each item has a value and a size; upon arrival, an item can be placed in a bin or discarded; the objective is to maximize the total value of the placement. Both value and size of an item may depend on the bin in which the item is placed; the size of an item is revealed only after it has been placed in a bin; distribution information is available about the value and size of each item in advance (not necessarily i.i.d), however items arrive in adversarial order (non-adaptive adversary).

Metaheuristic optimization algorithms are general optimization strategies suited to solve a range of real-world relevant optimization problems. Many metaheuristics expose parameters that allow to tune the effort that these algorithms are allowed to make and also the strategy and search behavior [1]. Adjusting these parameters allows to increase the algorithms' performances with respect to different problem- and problem instance characteristics.

Tuning stochastic local search algorithms for tackling large instances is difficult due to the large amount of CPU-time that testing algorithm configurations requires on such large instances. We define an experimental protocol that allows tuning an algorithm on small tuning instances and extrapolating from the obtained configurations a parameter setting that is suited for tackling large instances. The key element of our experimental protocol is that both the algorithm parameters that need to be scaled to large instances and the stopping time that is employed for the tuning instances are treated as free parameters. The scaling law of parameter values, and the computation time limits on the small instances are then derived through the minimization of a loss function. As a proof of concept, we tune an iterated local search algorithm and a robust tabu search algorithm for the quadratic assignment problem.

Assigning an optimal combination of empirical amino acid substitution models (e.g., WAG, LG, MTART) to partitioned multi-gene datasets when branch lengths across partitions are linked, is suspected to be an NP-hard problem. Given p partitions and the approximately 20 empirical protein models that are available, one needs to compute the log likelihood score of 20 p possible model-to-partition assignments for obtaining the optimal assignment.

We consider the multi-level bottleneck assignment problem (MBA). This problem is described in the recent book "Assignment Problems" by Burkard et al. (2009) on pages 188 - 189. One of the applications described there concerns bus driver scheduling. We view the problem as a special case of a bottleneck m-dimensional multi-index assignment problem. We give approximation algorithms and inapproximability results, depending upon the completeness of the underlying graph.

We focus on the problem of graph matching that is fundamental in computer vision and machine learning. Many state-of-the-arts frequently formulate it as integer quadratic programming, which incorporates both unary and second-order terms. This formulation is in general NP-hard thus obtaining an exact solution is computationally intractable. Therefore most algorithms seek the approximate optimum by relaxing techniques. This paper commences with the finding of the "circular" character of solution chain obtained by the iterative Gradient Assignment (via Hungarian method) in the discrete domain, and proposes a method for guiding the solver converging to a fixed point, resulting a convergent algorithm for graph matching in discrete domain. Furthermore, we extend the algorithms to their counterparts in continuous domain, proving the classical graduated assignment algorithm will converge to a double-circular solution chain, and the proposed Soft Constrained Graduated Assignment (SCGA) method will converge to a fixed (discrete) point, both under wild conditions. Competitive performances are reported in both synthetic and real experiments.

Travelling Salesman Problem(TSP) is a combinatorial optimization problem. This paper proposes a new high-efficiency global optimizationmethod for solving TSP. This method is described generally as: deleting unnecessary edges from edge set, and then generating a ring based on the remaining edges. Theories and experiments demonstrate that new algorithm just needs small quantity iterative steps to solve the problem, and achieves an optimization result.

Image analysis is directly applicable to various important and sensitive societal sectors, such as medicine, defense, and security. Often, related research is funded under industrial projects with tight deadlines. Therefore, sometimes certain important theoretical issues remain unaddressed. Such issues have been discussed in length in a recent article [2]. The latter suggested a number of strategic objectives for theoretical research in combinatorial image analysis. Most of these relate to the need to make the discipline better integrated within a number of well-established subjects of theoretical computer science and discrete applied mathematics, such as theory of algorithms and problem complexity, combinatorial optimization and polyhedral combinatorics, integer and linear programming, and computational geometry. Here we concern more in detail one aspect of the research on combinatorial algorithms for image analysis.

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.

The matching and retrieval of shapes is an important challenge in computer vision. A large number of shape similarity approaches have been developed. In this paper, we employ two approaches for improving shape retrieval. First, we use angle gradient to extract contour’s critical points, this is a simple approach which decrease the computational cost while retain spatial information of shapes. Second, we present a pairwise similarity measure, which is a quadratic assignment problem. This problem is approximately solved by spectral technique. This method is tested on standard MPEG-7 shape database using the standard performance evaluation scheme. The experimental results indicate that the proposed method outperforms the closely relate method.

Very large-scale neighborhood search (VLSNS) is a technique intensively used in single-objective optimization. However, there is almost no study of VLSNS for multiobjective optimization. We show in this paper that this technique is very efficient for the resolution of multiobjective combinatorial optimization problems. Two problems are considered: the multiobjective multidimensional knapsack problem and the multiobjective set covering problem. VLSNS are proposed for these two problems and are integrated into the two-phase Pareto local search. The results obtained on biobjective instances outperform the state-of-the-art results for various indicators.

This paper is concerned with automated tuning of parameters in local-search based meta-heuristics. Several generic approaches have been introduced in the literature that returns a ”one-size-fits-all” parameter configuration for all instances. This is unsatisfactory since different instances may require the algorithm to use very different parameter configurations in order to find good solutions. There have been approaches that perform instance-based automated tuning, but they are usually problem-specific. In this paper, we propose CluPaTra, a generic (problem-independent) approach to perform parameter tuning, based on CLUstering instances with similar PAtterns according to their search TRAjectories. We propose representing a search trajectory as a directed sequence and apply a well-studied sequence alignment technique to cluster instances based on the similarity of their respective search trajectories. We verify our work on the Traveling Salesman Problem (TSP) and Quadratic Assignment Problem (QAP). Experimental results show that CluPaTra offers significant improvement compared to ParamILS (a one-size-fits-all approach). CluPaTra is statistically significantly better compared with clustering using simple problem-specific features; and in comparison with the tuning of QAP instances based on a well-known distance and flow metric classification, we show that they are statistically comparable.

We are given a digraph G = (N,A), where each arc is colored with one among k given colors. We look for a spanning arborescence T of G rooted (wlog) at node 1 and having minimum changeover cost. We call this the Minimum Changeover Cost Arborescence problem. To the authors' knowledge, it is a new problem. The concept of changeover costs is similar to the one, already considered in the literature, of reload costs, but the latter depend also on the amount of commodity flowing in the arcs and through the nodes, whereas this is not the case for the changeover costs. Here, given any node j ≠1, if a is the color of the single arc entering node j in arborescence T, and b is the color of an arc (if any) leaving node j, then these two arcs contribute to the total changeover cost of T by the quantity dab, an entry of a k-dimensional square matrix D. We first prove that our problem is NPO-complete and very hard to approximate. Then we present Integer Programming formulations together with a combinatorial lower bound, a greedy heuristic and an exact solution approach. Finally, we report extensive computational results and exhibit a set of challenging instances.

This chapter presents a methodology for maintenance optimization for heterogeneous infrastructure systems, i.e., systems composed of multiple facilities with different characteristics such as environments, materials and deterioration processes. We present a two-stage bottom-up approach. In the first step, optimal and near-optimal maintenance policies for each facility are found and used as inputs for the system-level optimization. In the second step, the problem is formulated as a constrained combinatorial optimization problem, where the best combination of facility-level optimal and near-optimal solutions is identified. An Evolutionary Algorithm (EA) is adopted to solve the combinatorial optimization problem. Its performance is evaluated using a hypothetical system of pavement sections. We find that a near-optimal solution (within less than 0.1% difference from the optimal solution) can be obtained in most cases. Numerical experiments show the potential of the proposed algorithm to solve the maintenance optimization problem for realistic heterogeneous systems.

From within the variety of research that has been devoted to the adaptation of Differential Evolution to the solution of problems dealing with permutation variables, the Geometric Differential Evolution algorithm appears to be a very promising strategy. This approach is based on a geometric interpretation of the evolutionary operators and has been specifically proposed for combinatorial optimization. Such an approach is adopted in this paper, in order to evaluate its efficiency on a challenging class of combinatorial optimization problems: the Job-Shop Scheduling Problem. This algorithm is implemented and tested on a selection of instances normally adopted in the specialized literature. The results obtained by this approach are compared with respect to those generated by a classical DE implementation (using Random Keys encoding for the decision variables). Our computational experiments reveal that, although Geometric Differential Evolution performs (globally) as well as classical DE, it is not really able to significantly improve its performance.

This paper describes a generic (meta-)cooperative optimization schema in which several agents endowed with an optimization technique (whose nature is not initially restricted) cooperate to solve an optimization problem. These agents can use a wide set of optimization techniques, including local search, population-based methods, and hybrids thereof, hence featuring multilevel hybridization. This optimization approach is here deployed on the Tool Switching Problem (ToSP), a hard combinatorial optimization problem in the area of flexible manufacturing. We have conducted an ample experimental analysis involving a comparison of a wide number of algorithms or a large number of instances. This analysis indicates that some meta-cooperative instances perform significantly better than the rest of the algorithms, including a memetic algorithm that was the previous incumbent for this problem.

Stochastic Pareto local search (SPLS) methods are local search algorithms for multi-objective combinatorial optimization problems that restart local search from points generated using a stochastic process. Examples of such stochastic processes are Brownian motion (or random processes), and the ones resulting from the use of mutation and recombination operators. We propose a path-guided mutation operator for SPLS where an individual solution is mutated in the direction of the path to another individual solution in order to restart a PLS.We study the exploration of the landscape of the bi-objective Quadratic assignment problem (bQAP) using SPLSs that restart the PLSs from: i) uniform randomly generated solutions, ii) solutions generated from best-so-far local optimal solutions with uniform random mutation and iii) with path-guided mutation. Experiments on a bQAP with a large number of facilities and high correlation between the flow matrices show that using mutation, and especially path-guided mutation, is beneficial for performance of SPLS. The performance of SPLSs is partially explained using their dynamical behavior like the probability of escaping the local optima and the speed of enhancing the Pareto front.

The fitness distance correlation (FDC) as a measure for problem difficulty was first introduced by Forrest and Jones. It was applied to many binary coded problems. This method is now applied to permutation based problems. As demanded by Schiavinotto and Stutzle, the distance in a search space is calculated by regarding the steps of the (neighborhood) operator. In this paper the five most common operators for permutations are analyzed on symmetric and asymmetric TSP instances. In addition a local quality measure, the point quality (PQ) is proposed as a supplement to the global FDC. With this local measure more characteristics and differences can be investigated. Some experimental results are illustrating these concepts.

We show that for every positive e > 0, unless NP ⊂ BPQP, it is impossible to approximate the maximum quadratic assignment problem within a factor better than 2log1-en by a reduction from the maximum label cover problem. Then, we present an O(√n)-approximation algorithm for the problem based on rounding of the linear programming relaxation often used in the state of the art exact algorithms.

International audience; Many combinatorial real-world problems are mostly dynamic. They are dynamic in the sense that the global optimum location and its value change over the time, in contrast to static problems. The task of the optimization algorithm is to track this shifting optimum. Particle Swarm Optimization (PSO) has been previously used to solve continuous dynamic optimization problems, whereas only a few works have been proposed for combinatorial ones. One of the most interesting dynamic problems is the Dynamic Vehicle Routing Problem (DVRP). This paper presents a Multi-Adaptive Particle Swarm Optimization (MAPSO) for solving the Vehicle Routing Problem with Dynamic Requests (VRPDR). In this approach the population of particles is split into a set of interacting swarms. Such a multi-swarm helps to maintain population diversity and good tracking is achieved. The effectiveness of this approach is tested on a well-known set of benchmarks, and compared to other metaheuristics from literature. The experimental results show that our multi-swarm optimizer significantly outperforms single solution and population based metaheuristics on this problem.

This paper proposes an optimization algorithm, which utilizes ideal spatiotemporal chaotic dynamics for solution search in a high dimensional solution space. Such chaotic dynamics is generated by the Lebesgue spectrum filter, which has been applied to the chaotic CDMA in previous researches to minimize the cross-correlation among the sequences. In the proposed method, such a filter is applied to the output functions of optimization neural networks to realize an ideal chaotic search, which generates ideally complicated searching dynamics. The proposed scheme is applied to two combinatorial optimization approaches, the Hopfield-Tank neural network with additive noise and a heuristic algorithm driven by neural networks, which solve the Traveling Salesman Problems and the Quadratic Assignment Problems. The simulation results show that the proposed approach using the ideal chaotic dynamics simply improves the performance of the chaotic algorithms without searching appropriate parameter values even for large-scale problems.

The RAND Corporation in the early 1950s contained “what may have been the most remarkable group of mathematicians working on optimization ever assembled” [6]: Arrow, Bellman, Dantzig, Flood, Ford, Fulkerson, Gale, Johnson, Nash, Orchard-Hays, Robinson, Shapley, Simon, Wagner, and other household names. Groups like this need their challenges. One of them appears to have been the traveling salesman problem (TSP) and particularly its instance of finding a shortest route through Washington, DC, and the 48 states [4, 7].

We survey recent results on combinatorial optimization problems in which the objective function is the entropy of a discrete distribution. These include the minimum entropy set cover, minimum entropy orientation, and minimum entropy coloring problems.

The Vehicle Routing Problem with Time Windows is a complex combinatorial optimization problem which can be seen as a fusion of two well known sub-problems: the Travelling Salesman Problem and the Bin Packing Problem. Its main objective is to find the lowest-cost set of routes to deliver demand, using identical vehicles with limited capacity, to customers with fixed service time windows. In this paper, we consider the minimization of the number of routes and the total cost simultaneously. Although previous evolutionary studies have considered this problem, none of them has focused on the similarity of solutions in the population. We propose a method to measure route similarity and incorporate it into an evolutionary algorithm to solve the bi-objective VRPTW. We have applied this algorithm to a publicly available set of benchmark instances, resulting in solutions that are competitive or better than others previously published.

ACO algorithms iteratively build solutions to an optimization problem. The solution construction process is guided by pheromone trails which represents a mechanism of adaptation that allows to bias the sampling of new solutions toward promising regions of the search space. Additionally, the bias of the search is influenced by problem dependent heuristic information. In this work we describe an ACO algorithm that incorporates principles of Tabu Search (TS) for the solution construction process. These concepts specifically address the way that TS uses the history of the search to avoid visiting solutions already analyzed. We consider the Quadratic Assignment Problem (QAP) as a case-study, since this problem was also tackled in a closely related research to ours, the one on the usage of external memory in ACO algorithms. The performance of the proposed algorithm is assessed by considering a well-known set of instances of QAP.

We propose an elitist Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic algorithm, called mGRASP/MH, for approximating the Pareto-optimal front in the multi-objective quadratic assignment problem (mQAP). The proposed algorithm is characterized by three features: elite greedy randomized construction, adaptation of search directions and cooperation between solutions. The approach builds starting solutions in a greedy fashion by using problem-specific information and elite solutions found previously. Also, mGRASP/MH maintains a population of solutions, each associated with a search direction (i.e. weight vector). These search directions are adaptively changed during the search. Moreover, a cooperation mechanism is also implemented between the solutions found by different local search procedures in mGRASP/MH. Our experiments show that mGRASP/MH performs better or similarly to several other state-of-the-art multi-objective metaheuristic algorithms when solving benchmark mQAP instances.

In this paper we present a hybrid model for the demand acceptance variant of the routing and wavelength assignment problem in directed networks, an important benchmark problem in optical network design. Our solution uses a decomposition into a MIP model for the routing and optimization aspect, combined with a finite domain constraint model for the wavelength assignment. If a solution to the constraint problem is found, it provides an optimal solution to the overall problem. If the constraint problem is infeasible, we use an extended explanation technique to find a good relaxation of the problem which leads to a near optimal solution. Extensive experiments show that proven optimality is achieved for more than 99.8% of all cases tested, while run-times are orders of magnitude smaller than the best known MIP solution.

The greedy approach is widely used for combinatorial optimization problems, but its implementation varies from problem to problem. In this paper we propose a mechanical approach for implementing greedy algorithmic programs. Using PAR method, a problem can be continually partitioned into subproblems in smaller size based on the problem singleton and the maximum selector, and the greedy algorithm can be mechanically generated by combining the problem-solving sequences. Our structural model supports logical transformation from specifications to algorithmic programs by deductive inference, and thus significantly promotes the automation and reusability of algorithm design.

This chapter addresses to the blocking flowshop scheduling problem with the aim of minimizing the makespan. An Estimation of Distribution Algorithm, followed by a local search procedure, after the step of creating a new individual, was developed in order to solve this problem. Our comparisons were performed against representative approaches proposed in the literature related to the blocking flowshop scheduling problem. The obtained results have shown that the proposed algorithm is able to improve 109 out of 120 best known solutions of Taillard’s instances. Moreover, our algorithm outperforms all competing approaches in terms of solution quality and computational time.

An approach to solve complex combinatorial optimizations problems is the Ant Colony Optimization Metaheuristic (ACO). There are several variations of this metaheuristic. One of them, the Max-Min Ant System, is an algorithm that presents excellent performance for some classes of combinatorial problems, such as Traveling Salesman Problem and the Quadratic Assignment Problem. This paper presents a method of convergence control of the Max-Min variation of Ant Colony Optimization Metaheuristic using paraconsistent logic. The proposed method can be adapted to any variation of the Ant Colony Optimization Metaheuristic.

The quadratic assignment problem (QAP) is one of the combinatorial optimization problems which belong to a class of NP-hard. To solve QAP, various algorithms for finding near optimal solutions have already been proposed. Among them, the Hopfield-Tank neural network approach is very attractive from a viewpoint of an application of neural dynamics to combinatorial optimization, this approach is not so effective because of local minimum problem. To overcome this problem, a method which uses chaotic dynamics has already been proposed. On the other hand, to avoid undesirable local minima, dynamical noise is often used. In this paper, we combine these two approaches---chaotic dynamics and dynamical noise---to realize an effective approach for solving combinatorial optimization problems: we add dynamical noise to chaotic neural network for solving QAP. The results show that when the small amount of dynamical noise is added, the solving performance is much improved. We also analyze the influence of dynamical noise to the chaotic dynamics, and show that dynamical noise diversifies the searching states to explore much better solutions.

In this paper, we apply the ant colony optimization metaheuristic to the Single Round Robin Maximum Value Problem, a problem from sports scheduling. This problem contains both feasibility constraints and an optimization goal. We approach this problem using a combination of the metaheuristic with backtracking search. We show how using constraint satisfaction techniques can improve the hybrid's performance. We also show that our approach performs comparably to integer programming and better than tabu search when applied to the Single Round Robin Maximum Value Problem.

The Minimum Interference Frequency Assignment Problem (MI-FAP) is an important optimization problem that arises in operational wireless networks. Solution techniques based on meta-heuristic algorithms have been shown to be successful for some test problems. However, they have not been demonstrated on the large scale problems that occur in practice, and their performance is poor in these cases. We propose a decomposed assignment technique which divides the initial problem into a number of simpler subproblems that are solved either independently or in sequence. Partial subproblems solutions are recomposed into a solution of the original problem. Our results, show that the decomposed assignment approach proposed can improve the outcomes, both in terms of solution quality and runtime. A number of partitioning methods are presented and compared, such as clique detection; partitioning based on sequential orderings; and novel applications of existing graph partitioning and clustering methods adapted for this problem.

In recent years we have witnessed a tremendous growth of communication networks resulted in a large variety of combinatorial optimization problems. One of these problems is the terminal assignment problem. In this paper, we propose a genetic algorithm employing multiple crossover and mutation operators for solving the well-known terminal assignment problem. Two sets of available crossover and mutation operators are established initially. In each generation a crossover method is selected for recombination and a mutation method is selected for mutation based on the amount fitness improvements achieved over a number of previous operations (recombinations/mutations). We use tournament selection for this purpose. Simulation results with the different methods implemented are compared.

We investigate cost propagation for solving combinatorial optimization problems with finite domain variables, expressed as an additive component model. Cost propagation combines ideas from both constraint programming and integer programming into a single approach, where problems are iteratively solved by numerical propagation, with updates for single constraint terms in the component model. We outline a theory of propagation in terms of equivalent problems with notions of consistency, local optimality, convergence and bounds. We define several different updates and analyze their properties. Finally, we outline computational experiments on the simple assignment problem, the set partitioning problem, and a crossword puzzle. The experiments illustrate that even without a top level search, cost propagation can by itself solve non-trivial problems, and also be attractive compared to standard methods.

In this paper, we apply the parallel predator-prey model for multi-objective optimization to a combinatorial problem for the first time: Exemplarily, we optimize sequences of 50 jobs for an instance of the bi-criteria scheduling problem 1|d j | i¾? C j ,L max with this approach. The modular building block architecture of the predator-prey system and the distribution of acting entities enables the analysis of separated problem knowledge and the design of corresponding variation operators. The actual modules are derived from local heuristics that tackle fractions of the complete problem. We unveil that it is possible to cover different areas of the Pareto-front with special property operators and make evident that the whole front can be covered if those operators are applied simultaneously to the spatial population. Further, we identify open problems that arise when the predator-prey model is applied to combinatorial problems which have not yet occurred for real-valued optimization problems.

This paper deals with a memetic algorithm for the reconstruction of binary images, by using their projections along four directions. The algorithm generates by network flows a set of initial images according to two of the input projections and lets them evolve toward a solution that can be optimal or close to the optimum. Switch and compactness operators improve the quality of the reconstructed images which belong to a given generation, while the selection of the best image addresses the evolution to an optimal output.

This paper examines a new way of dividing computational tasks into smaller interacting components, in order to effectively solve constrained optimization problems. In dividing the tasks, we propose problem decomposition, and the use of GAs as the solution approach. In this paper, we consider problems with block angular structures with or without overlapping variables. We decompose not only the problem but also appropriately the chromosome for different components of the problem. We also design a communication process for exchanging information between the components. The approach can be implemented for solving large scale optimization problems using parallel machines. A number of test problems have been solved to demonstrate the use of the proposed approach. The results are very encouraging.

This paper presents a novel hybrid algorithm for combinatorial optimization problems based on mixing the cross-entropy (CE) method and a Hopfield neural network. The algorithm uses the CE method as a global search procedure, whereas the Hopfield network is used to solve the constraints associated to the problems. We have shown the validity of our approach in several instance of the generalized frequency assignment problem.

The previously proposed cunning ant system (cAS), a variant of the ACO algorithm, worked well on the TSP and the results showed that the cAS could be one of the most promising ACO algorithms. In this paper, we apply cAS to solving QAP. We focus our main attention on the effects of applying local search and parallelization of the cAS. Results show promising performance of cAS on QAP.

We describe the use of very large-scale neighborhood search (VLSN) techniques in examination timetabling problems.We detail three applications of VLSN algorithms that illustrate the versatility and potential of such algorithms in timetabling. The first of these uses cyclic exchange neighborhoods, in which an ordered subset of exams in disjoint time slots are swapped cyclically such that each exam moves to the time slot of the exam following it in the order. The neighborhood of all such cyclic exchanges may be searched effectively for an improving set of moves, making this technique computationally reasonable in practice. We next describe the idea of optimized crossover in genetic algorithms, where the parent solutions used in the genetic algorithm perform an optimization routine to produce the 'most fit' of their children under the crossover operation. This technique can be viewed as a form of multivariate large-scale neighborhood search, and it has been applied successfully in several areas outside timetabling. The final topic we discuss is functional annealing, which gives a method of incorporating neighborhood search techniques into simulated annealing algorithms. Under this technique, the objective function is perturbed slightly to avoid stopping at local optima, while neighborhood search techniques help provide an effective search of the feasible space.

Optimization in sports is a field of increasing interest. Combinatorial optimization techniques have been applied, for example, to game scheduling and playoff elimination. A common problem usually found in sports management is the assignment of referees to games already scheduled. There are a number of rules and objectives that should be taken into account when referees are assigned to games. We address a simplified version of a referee assignment problem common to many amateur leagues of sports such as soccer, baseball, and basketball. The problem is formulated by integer programming and its decision version is proved to be NP-complete. To tackle real-life large instances of the referee assignment problem, we propose a three-phase heuristic approach based on a constructive procedure, a repair heuristic to make solutions feasible, and a local search heuristic to improve feasible solutions. Numerical results on realistic instances are presented and discussed.

We formulate decomposition of two-dimensional shapes as a combinatorial optimization problem and present a dynamic programming algorithm that solves it.

The Multidimensional Assignment Problem (MAP) is a combinatorial optimization problem that arises in many important practical areas including capital investment, dynamic facility location, elementary particle path reconstruction, multiple target tracking and sensor fusion. Since the solution space of the MAP increases exponentially with the problem parameters, and the problem has exponentially many local minima, only moderate-sized instances can be solved to optimality. We investigate the combinatorial structure of the solution space by extending a concept of Hamming distance. The results of numerical experiments indicate a linear trend for average Hamming distance to optimal solution for the cases where one of the parameters is fixed.

We discuss fast exponential time exact algorithms for generalized combinatorial optimization problems. The list of discussed NP-complete generalized combinatorial optimization problems includes the generalized minimum spanning tree problem, the generalized subset assignment problem and the generalized travelling salesman problem.

Particle Swarm Optimization (PSO) algorithm has exhibited good performance across a wide range of application problems. But research on the Quadratic Assignment Problem (QAP) has not much been investigated. In this paper, we introduce a novel approach based on PSO for QAPs. The representations of the position and velocity of the particles in the conventional PSO is extended from the real vectors to fuzzy matrices. A new mapping is proposed between the particles in the swarm and the problem space in an efficient way. We evaluate the performance of the proposed approach with Ant Colony Optimization (ACO) algorithm. Empirical results illustrate that the approach can be applied for solving quadratic assignment problems and it has outperforms ACO in the completion time.

A new type of approximate algorithm for optimization problems, called the membrane algorithm, is proposed. A membrane algorithm consists of several regions separated by means of membranes; in each region we place a few tentative solutions of the optimization problem and a subalgorithm. The subalgorithms improve the tentative solutions simultaneously. The best and worst solutions in a region are sent to adjacent inner and outer regions, respectively. By repeating this process, a good solution will appear in the innermost region. The algorithm terminates if a termination condition is satisfied. A simple condition is the number of iterations, while a little more sophisticated condition becomes true if the good solution is not changed during a predetermined number of iterations. Computer experiments show that the membrane algorithms solve the traveling salesman problem better than the simulated annealing algorithm.