A columnar competitive model for solving combinatorial optimization problems

The major drawbacks of the Hopfield network when it is applied to some combinatorial problems, e.g., the traveling salesman problem (TSP), are invalidity of the obtained solutions, trial-and-error setting value process of the network parameters and low-computation efficiency. This letter presents a columnar competitive model (CCM) which incorporates winner-takes-all (WTA) learning rule for solving the TSP. Theoretical analysis for the convergence of the CCM shows that the competitive computational neural network guarantees the convergence to valid states and avoids the onerous procedures of determining the penalty parameters. In addition, its intrinsic competitive learning mechanism enables a fast and effective evolving of the network. The simulation results illustrate that the competitive model offers more and better valid solutions as compared to the original Hopfield network.     

Probability Collectives: A multi-agent approach for solving combinatorial optimization problems

Complex systems generally have many components. It is not possible to understand such complex systems only by knowing the individual components and their behavior. This is because any move by a component affects the further decisions/moves by other components and so on. In a complex system, as the number of components grows, complexity also grows exponentially, making the entire system to be seen as a collection of subsystems or a Multi-Agent System (MAS). The major challenge is to make these agents work in a coordinated way, optimizing their local utilities and contributing the maximum towards optimization of the global objective. This paper discusses the theory of Collective Intelligence (COIN) using the modified version of Probability Collectives (PC) to achieve the global goal. The paper successfully demonstrated this approach by optimizing the Rosenbrock function in which the coupled variables are seen as autonomous agents working collectively to achieve the function optimum. To demonstrate the PC approach on combinatorial optimization problems, two test cases of the Multi-Depot Multiple Traveling Salesmen Problem (MDMTSP) with 3 depots, 3 vehicles and 15 nodes are solved. In these cases, the vehicles are considered as autonomous agents collectively searching the minimum cost path. PC is successfully accompanied with insertion, elimination and swapping heuristic techniques. The optimum results to the Rosenbrock function and both the MDMTSP test cases are obtained at reasonable computational costs.     

Analysis of mathematical models and methods of solving combinatorial optimization problems on game-type permutations

The paper is concerned with an optimization problem on game-type permutations, where one or both players have combinatorial constraints on their strategies. A mathematical model of such problems is constructed and analyzed. A modified graphical method is proposed to solve (2xn)-and (mx2)-dimensional problems. High-dimensional problems are reduced to linear programming and combinatorial optimization problems. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 103–114, November–December 2007.     

Combining multi-core and GPU computing for solving combinatorial optimization problems

In this paper, we revisit the design and implementation of Branch-and-Bound (B&B) algorithms for solving large combinatorial optimization problems on GPU-enhanced multi-core machines. B&B is a tree-based optimization method that uses four operators (selection, branching, bounding and pruning) to build and explore a highly irregular tree representing the solution space. In our previous works, we have proposed a GPU-accelerated approach in which only a single CPU core is used and only the bounding operator is performed on the GPU device. Here, we extend the approach (LL-GB&B) in order to minimize the CPU–GPU communication latency and thread divergence. Such an objective is achieved through a GPU-based fine-grained parallelization of the branching and pruning operators in addition to the bounding one. The second contribution consists in investigating the combination of a GPU with multi-core processing. Two scenarios have been explored leading to two approaches: a concurrent (RLL-GB&B) and a cooperative one (PLL-GB&B). In the first one, the exploration process is performed concurrently by the GPU and the CPU cores. In the cooperative approach, the CPU cores prepare and off-load to GPU pools of tree nodes using data streaming while the GPU performs the exploration. The different approaches have been extensively experimented on the Flowshop scheduling problem. Compared to a single CPU-based execution, LL-GB&B allows accelerations up to (×$\times$160) for large problem instances. Moreover, when combining multi-core and GPU, we figure out that using RLL-GB&B is not beneficial while PLL-GB&B enables an improvement up to 36% compared to LL-GB&B.     

A quantum-inspired Tabu search algorithm for solving combinatorial optimization problems

In this study, we propose a novel quantum-inspired evolutionary algorithm (QEA), called quantum inspired Tabu search (QTS). QTS is based on the classical Tabu search and characteristics of quantum computation, such as superposition. The process of qubit measurement is a probability operation that increases diversification; a quantum rotation gate used to searching toward attractive regions will increase intensification. This paper will show how to implement QTS into NP-complete problems such as 0/1 knapsack problems, multiple knapsack problems and the traveling salesman problem. These problems are important to computer science, cryptography and network security. Furthermore, our experimental results on 0/1 knapsack problems are compared with those of other heuristic algorithms, such as a conventional genetic algorithm, a Tabu search algorithm and the original QEA. The final outcomes show that QTS performs much better than other heuristic algorithms without premature convergence and with more efficiency. Also on multiple knapsack problems and the traveling salesman problem QTS verify its effectiveness.     

Diversity-adaptive parallel memetic algorithm for solving large scale combinatorial optimization problems

Parallel memetic algorithms (PMAs) are a class of modern parallel meta-heuristics that combine evolutionary algorithms, local search, parallel and distributed computing technologies for global optimization. Recent studies on PMAs for large-scale complex combinatorial optimization problems have shown that they converge to high quality solutions significantly faster than canonical GAs and MAs. However, the use of local learning for every individual throughout the PMA search can be a very computationally intensive and inefficient process. This paper presents a study on two diversity-adaptive strategies, i.e., (1) diversity-based static adaptive strategy (PMA-SLS) and (2) diversity-based dynamic adaptive strategy (PMA-DLS) for controlling the local search frequency in the PMA search. Empirical study on a class of NP-hard combinatorial optimization problem, particularly large-scale quadratic assignment problems (QAPs) shows that the diversity-adaptive PMA converges to competitive solutions at significantly lower computational cost when compared to the canonical MA and PMA. Furthermore, it is found that the diversity-based dynamic adaptation strategy displays better robustness in terms of solution quality across the class of QAP problems considered. Static adaptation strategy on the other hand requires extra effort in selecting suitable parameters to suit the problems in hand.     

求解组合优化问题的鱼群算法的收敛性证明

为了证明求解组合优化问题的人工鱼群算法的全局收敛性,将人工鱼群算法的搜索空间定义为离散空间,其中的每个点即为一个人工鱼的位置状态,其食物浓度即为该点的目标函数值。根据食物浓度大小将整个离散空间集合分为若干个非空子集;将所有人工鱼集合也对应划分为若干个非空子集。在人工鱼的觅食、聚群和追尾过程中,人工鱼从一个位置状态转移到任意一个位置状态的转移概率可以计算出来;人工鱼移动过程中的每个位置状态对应于有限Markov链上的一个状态,且满足可归约随机矩阵的稳定性条件,据此证明了工鱼群算法具有全局收敛性。     

A noisy chaotic neural network for solving combinatorial optimization problems: stochastic chaotic simulated annealing

Recently Chen and Aihara have demonstrated both experimentally and mathematically that their chaotic simulated annealing (CSA) has better search ability for solving combinatorial optimization problems compared to both the Hopfield-Tank approach and stochastic simulated annealing (SSA). However, CSA may not find a globally optimal solution no matter how slowly annealing is carried out, because the chaotic dynamics are completely deterministic. In contrast, SSA tends to settle down to a global optimum if the temperature is reduced sufficiently slowly. Here we combine the best features of both SSA and CSA, thereby proposing a new approach for solving optimization problems, i.e., stochastic chaotic simulated annealing, by using a noisy chaotic neural network. We show the effectiveness of this new approach with two difficult combinatorial optimization problems, i.e., a traveling salesman problem and a channel assignment problem for cellular mobile communications.     

Multipoint cubic surrogate function for sequential approximate optimization

Multipoint cubic approximations are investigated as surrogate functions for nonlinear objective and constraint functions in the context of sequential approximate optimization. The proposed surrogate functions match actual function and gradient values, including the current expansion point, thus satisfying the zero and first-order necessary conditions for global convergence to a local minimum of the original problem. Function and gradient information accumulated from multiple design points during the iteration history is used in estimating a reduced Hessian matrix and selected cubic terms in a design subspace appropriate for problems with many design variables. The resulting approximate response surface promises to accelerate convergence to an optimal design within the framework of a trust region algorithm. The hope is to realize computational savings in solving large numerical optimization problems. Numerical examples demonstrate the effectiveness of the new multipoint surrogate function in reducing errors over large changes in design variables.     

Extended Hopfield models for combinatorial optimization

The extended Hopfield neural network proposed by Abe et al. (1992) for solving combinatorial optimization problems with equality and/or inequality constraints has the drawback of being frequently stabilized in states with neurons of ambiguous classification as active or inactive. We introduce in the model a competitive activation mechanism and we derive a new expression of the penalty energy allowing us to reduce significantly the number of neurons with intermediate level of activations. The new version of the model is validated experimentally on the set covering problem. Our results confirm the importance of instituting competitive activation mechanisms in Hopfield neural-network models.     

A polyhedral approach to solving multicriterion combinatorial optimization problems over sets of polyarrangements

Multicriterion discrete optimization problems over feasible combinatorial sets of polyarrangements are considered. Structural properties of feasible domains and different types of efficient solutions are investigated. Based on the ideas of Euclidean combinatorial optimization and the major criterion method, a polyhedral approach to the solution of the problems is developed and substantiated. Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 118-126, May-June 2009.     

Multi-criteria human resource allocation for solving multistage combinatorial optimization problems using multiobjective hybrid genetic algorithm

Multi-criteria human resource allocation involves deciding how to divide human resource of limited availability among multiple demands in a way that optimizes current objectives. In this paper, we focus on multi-criteria human resource allocation for solving multistage combinatorial optimization problem. Hence we tackle this problem via a multistage decision-making model. A multistage decision-making model is similar to a complex problem solving, in which a suitable sequence of decisions is to be found. The task can be interpreted as a series of interactions between a decision maker and an outside world, at each stage of which some decisions are available and their immediate effect can be easily computed. Eventually, goals would be reached due to the found of optimized variables. In order to obtain a set of Pareto solutions efficiently, we propose a multiobjective hybrid genetic algorithm (mohGA) approach based on the multistage decision-making model for solving combinatorial optimization problems. According to the proposed method, we apply the mohGA to seek feasible solutions for all stages. The effectiveness of the proposed algorithm was validated by its application to an illustrative example dealing with multiobjective resource allocation problem.     

An efficient class of direct search surrogate methods for solving expensive optimization problems with CPU-time-related functions

In this paper, we characterize a new class of computationally expensive optimization problems and introduce an approach for solving them. In this class of problems, objective function values may be directly related to the computational time required to obtain them, so that, as the optimal solution is approached, the computational time required to evaluate the objective is significantly less than at points farther away from the solution. This is motivated by an application in which each objective function evaluation requires both a numerical fluid dynamics simulation and an image registration process, and the goal is to find the parameter values of a predetermined reference image by comparing the flow dynamics from the numerical simulation and the reference image through the image comparison process. In designing an approach to numerically solve the more general class of problems in an efficient way, we make use of surrogates based on CPU times of previously evaluated points, rather than their function values, all within the search step framework of mesh adaptive direct search algorithms. Because of the expected positive correlation between function values and their CPU times, a time cutoff parameter is added to the objective function evaluation to allow its termination during the comparison process if the computational time exceeds a specified threshold. The approach was tested using the NOMADm and DACE MATLAB? software packages, and results are presented.     

Approximation algorithms for combinatorial multicriteria optimization problems

The computational complexity of combinatorial multiple objective programming problems is investigated. NP-completeness and # P -completeness results are presented. Using two definitions of approximability, general results are presented, which outline limits for approximation algorithms. The performance of the well-known tree and Christofides' heuristics for the traveling salesman problem is investigated in the multicriteria case with respect to the two definitions of approximability.     

Bound sets for biobjective combinatorial optimization problems

In this paper we introduce the concept of bound sets for multiobjective discrete optimization. We prove general results on lower and upper bound sets for combinatorial optimization problems with multiple objectives. We present general algorithms for constructing lower and upper bound sets for biobjective problems and provide numerical results on five different problem types.     

Four-layer framework for combinatorial optimization problems domain

Four-layer framework for combinatorial optimization problems/models domain is suggested for applied problems structuring and solving: (1) basic combinatorial models and multicriteria decision making problems (e.g., clustering, knapsack problem, multiple choice problem, multicriteria ranking, assignment/allocation); (2) composite models/procedures (e.g., multicriteria combinatorial problems, morphological clique problem); (3) basic (standard) solving frameworks, e.g.: (i) Hierarchical Morphological Multicriteria Design (HMMD) (ranking, combinatorial synthesis based on morphological clique problem), (ii) multi-stage design (two-level HMMD), (iii) special multi-stage composite framework (clustering, assignment/location, multiple choice problem); and (4) domain-oriented solving frameworks, e.g.: (a) design of modular software, (b) design of test inputs for multi-function system testing, (c) combinatorial planning of medical treatment, (d) design and improvement of communication network topology, (e) multi-stage framework for information retrieval, (f) combinatorial evolution and forecasting of software, devices. The multi-layer approach covers ‘decision cycle’, i.e., problem statement, models, algorithms/procedures, solving schemes, decisions, decision analysis and improvement.     

Measuring instance difficulty for combinatorial optimization problems

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.