Search

This paper describes a heuristic algorithm for solving the plant/facility location problem by applying ant-colony optimization meta-heuristic. The facility location problem is discussed, and a mathematical formulation is presented. The problem is then modelled as a quadratic assignment problem. An ant algorithm is developed to solve the problem. The results reveal that the proposed algorithm can be adaptively constructed to solve discrete plant location problems. This has been applied to a set of known test problems and appears to be able to compete with other current solutions with encouraging results.

Ant colony optimization metaheuristic (ACO) represents a new class of algorithms particularly suited to solve real-world combinatorial optimization problems. ACO algorithms, published for the first time in 1991 by M. Dorigo [Optimization, learning and natural algorithms (in Italian). Ph.D. Thesis, Dipartimento di Elettronica, Politecnico di Milano, Milan, 1992] and his coworkers, have been applied, particularly starting from 1999 (Bonabeau et al., Swarm intelligence: from natural to artificial systems, Oxford University Press, New York, 1999; Dorigo et al., Artificial life 5(2):137–172, 1999; Dorigo and Di Caro, Ant colony optimization: a new metaheuristic, IEEE Press, Piscataway, NJ, 1999; Dorigo et al., Ant colony optimization and swarm intelligence, Springer, Berlin Heidelberg New York, 2004; Dorigo and Stutzle, Ant colony optimization, MIT Press, Cambridge, MA, 2004), to several kinds of optimization problems such as the traveling salesman problem, quadratic assignment problem, vehicle routing, sequential ordering, scheduling, graph coloring, management of communications networks, and so on. The ant colony optimization metaheuristic takes inspiration from the studies of real ant colonies’ foraging behavior. The main characteristic of such colonies is that individuals have no global knowledge of problem solving but communicate indirectly among themselves, depositing on the ground a chemical substance called pheromone, which influences probabilistically the choice of subsequent ants, which tend to follow paths where the pheromone concentration is higher. Such behavior, called stigmergy, is the basic mechanism that controls ant activity and permits them to take the shortest path connecting their nest to a food source. In this paper, it is shown how to convert natural ant behavior to algorithms able to escape from local minima and find global minimum solutions to constrained combinatorial problems. Some examples on plane trusses are also presented.

Cellular manufacturing system (CMS) which is based on the concept of group technology (GT) has been recognized as an efficient and effective way to improve the productivity in a factory. In recent years, there have been continuous research efforts to study different facet of CMS. Most of them concentrated on distinguishing the part families and machine cells either simultaneously or individually with the objective of minimizing intercellular and intracellular part movements. This is known as machine-part grouping problem (MPGP) which is a crucial process while designing CMS. Nevertheless, in reality some components may not be finished within only one cell, they have to travel to another cell(s) for further operation(s). Under this circumstance, intercellular part movement will occur. Different order/sequence of machine cells allocation may result in different total intercellular movement distance unit. It should be noted that if the production volume of each part is very large, then the total number of intercellular movement will be further larger. Therefore, the sequence of machine cells is particularly important in this aspect. With this consideration, the main aim of this work is to propose two-stage approach for solving cell formation problem as well as cell layout problem. The first stage is to identify machine cells and part families, which is the essential part of MPGP. The work in second stage is to carry out a macro-approach to study the cell formation problem with consideration of machining sequence. The impact of the sequencing for allocating the machine cells on minimizing intercellular movement distance unit will be investigated in this stage. The problem scope, which is a MPGP together with the background of cell layout problem (CLP), has been identified. Two mathematical models are formulated for MPGP and CLP respectively. The primary assumption of CLP is that it is a linear layout. The CLP is considered as a quadratic assignment problem (QAP). As MPGP and QAP are NP-hard, genetic algorithm (GA) is employed as solving algorithm. GA is a popular heuristic search technique and has proved superior performance on complex optimization problem. In addition, an industrial case study of a steel member production company has been employed to evaluate the proposed MPGP and CLP models, and the computational results are presented.

Metaheuristics is a set of intelligent nature inspired method, it aims to solve some optimization problems, such as quadratic assignment problem, knapsack problem, and graph colouring problem. Resolving an optimization problem consist in applying a mathematic process to find the minimum or the maximum solution depending on the constraints of the problem. In this paper, the travelling salesman problem is chosen to test the performance of a new proposed discrete novel hybrid particle swarm optimization. This method presents a combination between particle swarm optimization and harmony search algorithm, where harmony search improved the swarm. An experimental result of a different methaheuristics shows the efficiency of the proposed method for solving some benchmarks instances of TSPLib.

The traveling salesman problem (TSP), and the quadratic assignment problem (QAP) are two combinatorial optimization problems with a diverse set of applications. This research paper aims to apply the adaptation of discrete cat swarm optimization algorithm inspired by the natural behavior of cats to solve TSP and QAP. Simulated experiments were conducted on several benchmark instances taken from the OR-library. The results show the effectiveness of the proposed adaptation to solve real applications area based on the two-studied problems.

Combinatorial optimization problems are encountered in many areas of science and engineering. Most of these problems are too difficult to be solved optimally, and hence heuristics are used to obtain “good” solutions in reasonable time. One heuristic that has been successfully applied to a variety of problems is Simulated Annealing. The performance of Simulated Annealing depends on the appropriate choice of a key parameter, the annealing schedule. Researchers usually experiment with some manually created annealing schedules and then use the one that performs best in their algorithms. This work replaces this manual search by Genetic Programming, a method based on natural evolution. We demonstrate the potential of this new approach by optimizing the annealing schedule for a well-known combinatorial optimization problem, the Quadratic Assignment Problem. We introduce two new algorithms for solving the Quadratic Assignment Problem that perform extremely well and outperform existing Simulated Annealing algorithms.

This paper reviews the theory and applications of ant algorithms, new methods of discrete optimization based on the simulation of self-organized colony of biologic ants. The colony can be regarded as a multi-agent system where each agent is functioning independently by simple rules. Unlike the nearly primitive behavior of the agents, the behavior of the whole system happens to be amazingly reasonable. The ant algorithms have been extensively studied by European researchers from the mid-1990s. These algorithms have successfully been applied to solving many complex combinatorial optimization problems, such as the traveling salesman problem, the vehicle routing problem, the problem of graph coloring, the quadratic assignment problem, the problem of network-traffic optimization, the job-shop scheduling problem, etc. The ant algorithms are especially efficient for online optimization of processes in distributed nonstationary systems (for example, telecommunication network routing).

The planning problem of electrical power distribution networks, stated as a mixed nonlinear integer optimization problem, is solved using the ant colony system algorithm (ACS). The behavior of real ants has inspired the development of the ACS algorithm, an improved version of the ant system (AS) algorithm, which reproduces the technique used by ants to construct their food recollection routes from their nest, and where a set of artificial ants cooperate to find the best solution through the interchange of the information contained in the pheromone deposits of the different trajectories. This metaheuristic approach has proven to be very robust when applied to global optimization problems of a combinatorial nature, such as the traveling salesman and the quadratic assignment problem, and is favorably compared to other solution approaches such as genetic algorithms (GAs) and simulated annealing techniques. In this work, the ACS methodology is coupled with a conventional distribution system load-flow algorithm and adapted to solve the primary distribution system planning problem. The application of the proposed methodology to two real cases is presented: a 34.5-kV system with 23 nodes from the oil industry and a more complex 10-kV electrical distribution system with 201 nodes that feeds an urban area. The performance of the proposed approach outstands positively when compared to GAs, obtaining improved results with significant reductions in the solution time. The technique is shown as a flexible and powerful tool for the distribution system planning engineers.

We present in this paper a computational system whose goal is to optimize the automatic electronic component insertion process on a particular inserting machine, the Panasert AVK machine. First of all, we present an analysis of this optimization problem, showing that it corresponds to a certain kind of combination of two NP -hard type problems, the Traveling Salesman Problem (TSP) and the Quadratic Assignment Problem (QAP). We describe then the architecture of the system, called OPTIMA, that was built using a technique known as Asynchronous Teams (A-Teams). Finally, we present both the results obtained and the conclusions inferred, where we show the viability of this technique when applied to this class of problems.

Placement is a major step encountered during the design of very large scale integrated circuits. It is a generalization of the quadratic assignment problem with numerous constraints, several objectives, and a very noisy solution space. Besides the NP-hard nature of this problem, many circuit parameters such as area, interconnect delays, wire requirements, etc. can only be imprecisely estimated before completing the remaining design automation steps and committing the circuit to silicon. Further, the best placement is usually one that combines several desirable physical characteristics. There has not been a consensus on how to accommodate all these (conflicting) requirements in the search for near optimal feasible solutions. In this paper, we present a fuzzy simulated evolution (FSE) algorithm to tackle this problem. Identification of near optimal solutions is achieved through a novel goal-directed fuzzy search approach. This approach can be followed by other iterative (meta-) heuristics to find desirable solutions to optimization problems with noisy search space and possibly more than one objective. This approach is dominance preserving, i.e. if a solution A dominates another solution B with respect to all objective criteria, then A will surely have a higher membership in the fuzzy set of good solutions than solution B. Further, the approach scales well with larger problem instances and/or a larger number of objective criteria. Also, the operators of all stages of simulated evolution have been implemented using fuzzy logic to exploit the nature of fuzzy information of the problem domain. Experiments with benchmark tests demonstrate a noticeable improvement in solution quality.

In combinatorial optimization it is not rare to find problems whose mathematical structure is nearly the same, differing only in some aspect related to the motivating application. For example, many problems in machine scheduling and vehicle routing have equivalent formulations and only differ with respect to the optimization objective, or particular constraints. Moreover, while some problems receive a lot of attention from the research community, their close relatives receive hardly any attention at all. Given two closely related problems, it is intuitive that it may be effective to adapt state-of-the-art algorithms-initially introduced for the well-studied problem variant-to the less-studied problem variant. In this paper we provide an example based on the travelling salesman problem with time windows that supports this intuition. In this context, the well-studied problem variant minimizes the travel time, while the less-studied problem variant minimizes the makespan. Indeed, the results show that the algorithms that we adapt from travel-time minimization to makespan minimization significantly outperform the existing state-of-the-art approaches for makespan minimization.

A differential improvement modification to Hybrid Genetic Algorithms is proposed. The general idea is to perform more extensive improvement algorithms on higher quality solutions. Our proposed Differential Improvement (DI) approach is of rather general character. It can be implemented in many different ways. The paradigm remains invariant and can be easily applied to a wider class of optimization problems. Moreover, the DI framework can also be used within other Hybrid metaheuristics like Hybrid Scatter Search algorithms, Particle Swarm Optimization, or Bee Colony Optimization techniques. Extensive experiments show that the new approach enables to improve significantly the performance of Hybrid Genetic Algorithms without adding extra computer time. Additional experiments investigated the trade-off between the number of generations and the number of iterations of the improvement algorithm. These experiments yielded six new best known solutions to benchmark quadratic assignment problems. Many other variants of the proposed algorithm are suggested for future research.

A general method to reduce computing time for large combinatorial optimization problems by the use of a novel proposal is presented. It is based on reducing the problem complexity by the systematic application of vaccines, it is inspired in the concept of immunization derived from Artificial Immune Systems. The method can be applied practically to any combinatorial problem program solver such as genetic algorithms, memetic algorithms, artificial immune systems, ant colony optimization, the Dantzig-Fulkerson-Johnson algorithm, etc., providing optimal and suboptimal routes outperforming the selected algorithm itself. As a direct consequence of reducing problem complexity, the method provides a means to bring combinatorial optimization open problems that are too big to be treated by known techniques to a tractable point where acceptable solutions can be obtained. To demonstrate the proposed methodology the Traveling Salesman Problem for huge quantity of cities was used, we tested the method with modern evolutionary algorithms and the Concorde program. Comparative experiments that shows the effectiveness of the method are presented.

In this paper, we present a general framework for designing approximation schemes for combinatorial optimization problems in which the objective function is a combination of more than one function. Examples of such problems include those in which the objective function is a product or ratio of two linear functions, parallel machine scheduling problems with the makespan objective, robust versions of weighted multiobjective optimization problems, and assortment optimization problems with logit choice models. The main idea behind our approximation schemes is the construction of an approximate Pareto-optimal frontier of the functions that constitute the given objective. Using this idea, we give the first fully polynomial-time approximation schemes for the max-min resource allocation problem with a fixed number of agents, combinatorial optimization problems in which the objective function is the sum of a fixed number of ratios of linear functions, or the product of a fixed number of linear functions, and assortment optimization problems with logit choice model.

Black-box complexity is a complexity theoretic measure for how difficult a problem is to be optimized by a general purpose optimization algorithm. It is thus one of the few means trying to understand which problems are tractable for genetic algorithms and other randomized search heuristics. Most previous work on black-box complexity is on artificial test functions. In this paper, we move a step forward and give a detailed analysis for the two combinatorial problems minimum spanning tree and single-source shortest paths. Besides giving interesting bounds for their black-box complexities, our work reveals that the choice of how to model the optimization problem is non-trivial here. This in particular comes true where the search space does not consist of bit strings and where a reasonable definition of unbiasedness has to be agreed on., 26 pages. This is the full version of the one presented at the Genetic and Evolutionary Computation Conference (GECCO 2011)

We establish strong NP-hardness and in-approximability of the so-called representatives selection problem, a tool selection problem in the area of robust optimization. Our results answer a recent question of Dolgui and Kovalev (4OR Q J Oper Res 10:181–192, 2012). Keywords: Combinatorial optimization; Computational complexity; Robust optimization

We present a wide range of problems concerning minimum cost network flows, and give an overview of the classic linear single-commodity Minimum Cost Network Flow Problem (MCNFP) and some other closely related problems, either tractable or intractable. We also discuss state-of-the-art algorithmic approaches and recent advances in the solution methods for the MCNFP. Finally, optimization software packages for the MCNFP are presented. Keywords : Mathematical Programming, Combinatorial Optimization, Optimization Software. MSC: 65K05, 90C27, 90B10.

In large-scale computer communication networks (e.g. the nowadays Internet), the assignment of link capacity and the selection of routes are extremely complex network optimization problems. Efficient solutions to these problems are much sought after because such solutions could lead to considerable monetary savings and better utilization of the networks. Unfortunately, as indicated by much prior theoretical research, these problems belong to the class of nonlinear combinatorial optimization problems, which are mostly (if not all) NP-hard problems. Metaheuristics, such as genetic and simulated annealing algorithms, are widely applicable heuristic optimization strategies that have shown encouraging results for a large number of difficult combinatorial optimization problems. In this paper, we propose three different approaches for solving the routing and capacity assignment (RCA) problem. The first approach uses a GA. The second approach uses the SA algorithm. The last approach combines the GA with the SA to improve the performance of the GA. The paper also presents the experiments that we have conducted to evaluate the effectiveness of the proposed approaches compared to a one of the heuristic algorithms for solving the same problem. The results show that the hybrid approach is more efficient in finding good solutions to the RCA problem compared to other techniques.

In multi colony ant algorithms several colonies of ants cooperate in finding good solutions for an optimization problem. At certain time steps the colonies exchange information about good solutions. If the amount of exchanged information is not too large multi colony ant algorithms can be easily parallelized in a natural way by placing the colonies on different processors. In this paper we study the behaviour of multi colony ant algorithms with different kinds of information exchange between the colonies. Moreover we compare the behaviour of different numbers of colonies with a multi start single colony ant algorithm. As test problems we use the Traveling Salesperson problem and the Quadratic Assignment problem.

Assignment problem is considered a well-known optimization problem in manufacturing and management processes in which a decision maker's point of view is merged into a decision process and a valid solution is established. In this study, taking the complementary relations between expected value and variance in decision making and the synthesizing effect of random variables into consideration, a new model for random assignment problems is proposed; in which the characteristic of assignment problems are considered to present a concrete scheme based on genetic algorithms (denoted by SE @? GA-SAF, for short). We study the model's convergence using the Markov chain theory, and analyze its performance through simulation. All of these indicate that this solution model can effectively aid decision making in the assignment process, and that it possesses the desirable features such as interpretability and computational efficiency, as such it can be widely used in many aspects including manufacturing, operations, logistics, etc.

This paper deals with stability analysis in multi-objective combinatorial optimization problems. The stability radius of an efficient solution is defined as the maximal adjustment of the problem parameters such that this solution remains efficient. An algorithm based on inverse optimization is proposed to compute it. The adjustment is limited to the coefficients of the objective functions and measured by the Chebyshev norm. This approach is applied to randomly generated instances of the bi-objective knapsack problem and computational results are reported. Several illustrative examples are analyzed.

International audience; A composite service is usually specified by means of a process model that captures control-flow and data-flow relations between activities that are bound to underlying component services. In mainstream service orchestration platforms, this process model is executed by a centralized orchestrator through which all interactions are channeled. This architecture is not optimal in terms of communication overhead and has the usual problems of a single point of failure. In previous work, we proposed a method for executing composite services in a decentralized manner. However, this and similar methods for decentralized composite service execution do not optimize the communication overhead between the services participating in the composition. This paper studies the problem of optimizing the selection of services assigned to activities in a decentralized composite service, both in terms of communication overhead and overall quality of service, and taking into account collocation and separation constraints that may exist between activities in the composite service. This optimization problem is formulated as a quadratic assignment problem. The paper puts forward a greedy algorithm to compute an initial solution as well as a tabu search heuristic to identify improved solutions. An experimental evaluation shows that the tabu search heuristic achieves significant improvements over the initial greedy solution. It is also shown that the greedy algorithm combined with the tabu search heuristic scale up to models of realistic size.

The problem of optimal channel assignment has become increasingly important because of available frequency spectrum and increasing demand for cellular communication services. This has been shown to be an NP-complete optimization problem. Many heuristic approaches including neural network, simulated annealing and genetic algorithm have been used to solve it. In this paper we propose a novel and efficient channel assignment approach, particle swarm optimization, to seek a conflict-free channel assignment such that demand is achieved and the EMC constraints are fulfilled, while number of frequency channels is minimized. Simulations on eight well-known benchmark problems showed that the PSO can effectively generate the low-band results. © 2005 IEEE.

The human-computer cooperative approaches for handling the combinatorial optimization problems are introduced. In this paper we propose the human-computer cooperation approach for combinatorial optimization problems. Firstly, the initial solutions are seen as the sampling in human cognition by computer games. The games are developed for special combinatorial optimization problems. Then fuzzy decomposition decomposes the optimization problem into several sub-problems according to initial solutions by human. Moreover, local search strategy is given in conformational space with human strategy development capabilities, which also explores the space of possible search strategies. Last, the stochastic elements of the search in the traditional computational algorithms are gone with human intelligence during the fuzzy composition process. Human-computer cooperation approach can indeed lead to mutual advantage, and it can improve the problem-solving skills. We apply the proposed method to two-echelon vehicle routing problem to verify its effectiveness and usefulness.

Bi-level optimization problems are a class of challenging optimization problems, that contain two levels of optimization tasks. In these problems, the optimal solutions to the lower level problem become possible feasible candidates to the upper level problem. 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. In recent decades, it is observed that many efficient optimizations using modern advanced EAs have been achieved via the incorporation of domain specific knowledge. In such a way, the embedment of domain knowledge about an underlying problem into the search algorithms can enhance properly the evolutionary search performance. Motivated by this issue, we present in this paper a Memetic Evolutionary Algorithm for Bi-level Combinatorial Optimization (M-CODBA) based on a new recently proposed CODBA algorithm with transfer learning to enhance future bi-level evolutionary search. A realization of the proposed scheme is investigated on the Bi-CVRP and Bi-MDVRP problems. The experimental studies on well established benchmarks are presented to assess and validate the benefits of incorporating knowledge memes on bi-level evolutionary search. Most notably, the results emphasize the advantage of our proposal over the original scheme and demonstrate its capability to accelerate the convergence of the algorithm.

Frequency assignment, as a subclass of general assignment problem, is a non-deterministic polynomial-time hard (NP-hard) optimization problem. Main difficulty in these types of problems is the time required to find an optimum solution, since the solution time increases exponentially as the size of the problem grows. To solve the problem in a limited computation time, meta-heuristic methods are adopted. In this study, a frequency assignment problem with conflicting objectives is described. This multi-objective optimization problem is reduced to a single objective one using a scalarization approach. Genetic Algorithm and Particle Swarm Optimization are used to find a solution to the problem. Comparisons of the performances of alternative methods are carried out for the identified problem. Results show that the proposed methods can get a solution which is quite acceptable in terms of interference levels.

Evolutionary Computation Journal 19(4):597-637 A small number of combinatorial optimization problems have search spaces that correspond to elementary landscapes, where the objective function f is an eigenfunction of the Laplacian that describes the neighborhood structure of the search space. Many problems are not elementary; however, the objective function of a combinatorial optimization problem can always be expressed as a superposition of multiple elementary landscapes if the underlying neighborhood used is symmetric. This paper presents theoretical results that provide the foundation for algebraic methods that can be used to decompose the objective function of an arbitrary combinatorial optimization problem into a sum of subfunctions, where each subfunction is an elementary landscape. Many steps of this process can be automated, and indeed a software tool could be developed that assists the researcher in finding a landscape decomposition. This methodology is then used to show that the subset sum problem is a superposition of two elementary landscapes, and to show that the quadratic assignment problem is a superposition of three elementary landscapes. Spanish Ministry of Science and Innovation and FEDER under contract TIN2008-06491-C04-01 (the M∗ project). Andalusian Government under contract P07-TIC- 03044 (DIRICOM project). Air Force Office of Scientific Research, Air Force Materiel Command, USAF, under grant number FA9550-08-1-0422.

Quadratic Assignment Problem (QAP), like Vehicle Routing Problem, is one of those optimization problems that interests many researchers in the last decades. The Quay Management Problem is a specific problem which could be presented as a QAP which involves a double assignment of customers and products toward loading positions using lifting trucks. This study focuses on the routing problem while delivering the customers' demands. In this problem, lifting trucks will route around the storage sections to collect the products then deliver to the customers who are assigned to specific loading positions. The objective of minimizing the residence time for each customer is sought. This paper presents the problem and the proposed model.

In this paper, we explain the relations between combinatorial optimization and real algebraic geometry with a special focus to the quadratic assignment problem. We demonstrate how to write a quadratic optimization problem over discrete feasible set as a linear optimization problem over the cone of completely positive matrices. The latter formulation enables a hierarchy of approximations which rely on results from polynomial optimization, a sub-eld of real algebraic geometry.

This paper deals with an analysis of transformations between combinatorial optimization problems and proposes an approach to the fractal representation of the complexity classes structure. The investigation of fitness landscapes leads to the establishment of their key parameters. The study results discover that P and NP class problems can differ in properties of their landscapes.

In the case of some large statistical surveys, the set of units that will constitute the scope of the survey must be selected. We focus on the real case of a Census of Agriculture, where the units are farms. Surveying each unit has a cost and brings a different portion of the whole information. In this case, one wants to determine a subset of units producing the minimum total cost for being surveyed and representing at least a certain portion of the total information. Uncertainty aspects also occur, because the portion of information corresponding to each unit is not perfectly known before surveying it. The proposed approach is based on combinatorial optimization, and the arising decision problems are modeled as multidimensional binary knapsack problems. Experimental results show the effectiveness of the proposed approach.

This work was supported by FEDER funding through the Programa Operacional Factores de Competitividade (COMPETE) and by national funding through the Portuguese Science and Technology Foundation (FCT) in the scope of the project PTDC/EGE-GES/116676/2010 (Reference from COMPETE: FCOMP-01-0124-FEDER-020430), and by FCT within the project scope UID/CEC/00319/2013.

k -median and k -center are two well-known problems in facility location which play an important role in operation research, management science, clustering and computational geometry. To the best of our knowledge, although these problems have lots of applications, they have never been studied together simultaneously as a multi objective optimization problem. Multi-objective optimization has been applied in many fields of science where optimal decisions need to be taken in the presence of trade-offs between two or more conflicting objectives. In this paper we consider 1-median and 1-center two-objective optimization problem. We prove that \(\varOmega (n\log {n})\) is a lower bound for proposed problem in one and two dimensions in Manhattan metric. Also, by using the properties of farthest point Voronoi diagram, we present a deterministic algorithm which output the Pareto Front and Pareto Optimal Solutions in \(\mathcal {O}(n\log {n})\) time.

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 $L_p$-norm ($0 < p < 1$) regularization term to the objective function. The optimal solutions of the $L_p$-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 $L_p$ regularization algorithm with local refinements. The algorithm approximately solves a sequence of $L_p$ regularization subproblems by the projected gradient method using a nonmontone 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., This paper has been accepted for publication in SIAM Journal on Optimization

The paper presents results of further research on a software tool named ALMM Solver. The objective of the ALMM Solver is to solve combinatorial and discrete optimization problems including NP-hard problems.

The turbine balancing problem (TBP) is an NP-Hard combinatorial optimization problem arising in the manufacturing and maintenance of turbine engines. Exact solution methods for solving the TBP are not appropriate since the problem has to be solved in real time and the input data is itself inaccurate. In this paper the TBP is formulated as a quadratic assignment problem (QAP) and we propose a heuristic algorithm for solving the resulting problem. Computational results on a set of instances provided by Pratt & Whitney (P&W) and from the literature, indicate that the proposed algorithm outperforms the current methods used for solving the TBP, and has the best overall performance with respect to other heuristic algorithms in the literature.

We have proposed an optimization method for a combinatorial optimization problem using replicator equations. To improve the solution further, a deterministic annealing algorithm may be applied. During the annealing process, bifurcations of equilibrium solutions will occur and affect the performance of the deterministic annealing algorithm. In this paper, the bifurcation structure of the proposed model is analyzed in detail. It is shown that only pitchfork bifurcations occur in the annealing process, and the solution obtained by the annealing is the branch uniquely connected with the uniform solution. It is also shown experimentally that in many cases, this solution corresponds to a good approximate solution of the optimization problem. Based on the results, a deterministic annealing algorithm is proposed and applied to the quadratic assignment problem to verify its performance.

The maritime transportation is one of the important economic fields. It permits to exchange a huge volume of goods across the world every year. In order to ameliorate the productivity of this field, it was necessary to automate the port equipment. But this solution has some limits, particularly in optimization of handling goods operations. The ship can remain a long period of time waiting the loading or unloading operation. Several researchers had been interested in this problem; it was different modules in this field. In this paper, we are interested in assignment containers to AIV optimization problem; it includes also the AIV routing problem. We propose a resolution method; a mathematical model is made by analogy with the vehicle routing problem and the proposed approach is a genetic algorithm. An experimental calculus is made and the numerical results are acceptable.

Two criteria in a combinatorial problem are often combined in a weighted sum objective using a weighting parameter between 0 and 1. For special problem types, e.g., when one of the criteria is a bottleneck value, efficient algorithms are known that solve for a given value of the weighting parameter. We transform the underlying enumeration method into a parametric algorithm solving simultaneously for all values of the weighting parameter. Efficient implementations are presented for combinatorial problems with criteria as balanced optimization, min–sum with min–max, and min–sum with balanced optimization, considering the spanning tree, the linear assignment and the single machine scheduling problem. Further the new algorithmic scheme can easily incorporate a trade-off of the criteria by means of penalty functions, again without consequences for the algorithm and its complexity order.

Ant-Colony Optimization (ACO) is a popular swarm intelligence scheme known for its efficiency in solving combinatorial optimization problems. However, despite some extensions of this approach to continuous optimization, high-dimensional problems remain a challenge for ACO. This paper presents an ACO-based algorithm for numerical optimization capable of solving high-dimensional real-parameter optimization problems. The algorithm, called the Differential Ant-Stigmergy Algorithm (DASA), transforms a real-parameter optimization problem into a graph-search problem. The parameters' differences assigned to the graph vertices are used to navigate through the search space. We compare the algorithm results with the results of previous studies on recent benchmark functions and show that the DASA is a competitive continuous optimization algorithm that solves high-dimensional problems effectively and efficiently.

Discovering the conditions under which an optimization algorithm or search heuristic will succeed or fail is critical for understanding the strengths and weaknesses of different algorithms, and for automated algorithm selection. Large scale experimental studies - studying the performance of a variety of optimization algorithms across a large collection of diverse problem instances - provide the resources to derive these conditions. Data mining techniques can be used to learn the relationships between the critical features of the instances and the performance of algorithms. This paper discusses how we can adequately characterize the features of a problem instance that have impact on difficulty in terms of algorithmic performance, and how such features can be defined and measured for various optimization problems. We provide a comprehensive survey of the research field with a focus on six combinatorial optimization problems: assignment, traveling salesman, and knapsack problems, bin-packing, graph coloring, and timetabling. For these problems - which are important abstractions of many real-world problems - we review hardness-revealing features as developed over decades of research, and we discuss the suitability of more problem-independent landscape metrics. We discuss how the features developed for one problem may be transferred to study related problems exhibiting similar structures.

In this article, we deal with the inverse linear optimization problem under l2-norm defined as follows: for a given linear optimization problem LP(b), with the right-hand side vector b, and current operating plan x 0, we would like to perturb the right-hand side vector b to so that x 0 is an optimal solution of and is minimum. We prove that this inverse problem is equivalent to an optimization problem which contains some equilibrium constraints that makes it hard to solve. In order to solve this optimization problem, we employ the interior point approach behind LOQO and show that, at each iteration, the search direction is a descent direction for the l2 merit function. Therefore, an e-solution of the inverse problem can be computed using an extension of polynomial-time interior-point methods for linear and quadratic optimization problems. Finally, computational results of applying proposed approach on some generated inverse problems are given.

The standard quadratic optimization problem (StQP) refers to the problem of minimizing a quadratic form over the standard simplex. Such a problem arises from numerous applications and is known to be NP-hard. In this paper we focus on a special scenario of the StQP where all the elements of the data matrix Q are independently identically distributed and follow a certain distribution such as uniform or exponential distribution. We show that the probability that such a random StQP has a global optimal solution with k nonzero elements decays exponentially in k. Numerical evaluation of our theoretical finding is discussed as well.

This research deals with the path-based system optimal dynamic traffic assignment (SODTA) problem with uncertain demands that are assumed to be bounded by a prescribed uncertainty set. A robust optimization approach is adopted to address this problem. The objective is to minimize the total network travel time under the worst-case scenario defined by a pre-determined demand uncertainty set. We formulate the robust counterpart optimization problem of SODTA for a general uncertainty set and show that solving the robust SODTA problem is not more difficult than solving the deterministic SODTA problem for some specific types of uncertainty set. Moreover, a column generation-based algorithmic framework that embeds a scaled gradient projection algorithm is proposed to solve the SODTA problem. Numerical experiments were conducted to demonstrate the effectiveness of the algorithm and to examine the impact of different types of demand uncertainty set on solution quality.

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 k-salesmen Traveling Salesman Problem (TSP), where costs are evaluated for elements located at k-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 k-distance TSPs are well-solvable, so is the QAP obtained by their sum, where the solution of 1-distance TSPs dominates all the others.

Due to its versatility, copositive optimization receives increasing interest in the Operational Research community, and is a rapidly expanding and fertile field of research. It is a special case of conic optimization, which consists of minimizing a linear function over a cone subject to linear constraints. The diversity of copositive formulations in different domains of optimization is impressive, since problem classes both in the continuous and discrete world, as well as both deterministic and stochastic models are covered. Copositivity appears in local and global optimality conditions for quadratic optimization, but can also yield tighter bounds for NP-hard combinatorial optimization problems. Here some of the recent success stories are told, along with principles, algorithms and applications.