Applying GIS and Combinatorial Optimization to Fiber Deployment Plans

A decision-support system for the Fiber Deployment Plan problem is developed for the telephone cable network design in the telecommunications industry. The system employs a Geographic Information System (GIS) and uses combinatorial optimization techniques as its components. A mathematical combinatorial optimization model is formulated for the problem and a heuristic solution procedure is developed for the model. A GIS within the ESRI Arc/INFO and ArcView environment is used to provide data needed to build the mathematical combinatorial optimization model and to furnish an interface between the users and computers in data input and in solution result display. Combinatorial optimization techniques are used in the heuristic solution procedure to find good solutions for the optimization model. The developed decision-support system has been used to real life problems and has resulted in tremendous improvements in the telephone cable network design process. The user is completely satisfied with the performance of the system.     

二维混合布局问题的组合优化模型及算法

本文以卫星仪器舱布局优化设计问题为背景，分别以矩形和圆形为各种仪器的表征图元，建立二维混合布局的组合优化模型，并给出其主要性质和算法     

Lock-Gain Based Graph Partitioning

We propose a new heuristic for the graph partitioning problem. Based on the traditional iterative improvement framework, the heuristic uses a new type of gain in selecting vertices to move between partitions. The new type of gain provides a good explanation for the performance difference of tie-breaking strategies in KL-based iterative improvement graph partitioning algorithms. The new heuristic performed excellently. Theoretical arguments supporting its efficacy are also provided. As the proposed heuristic is considered a good candidate for local optimization engines in metaheuristics, we combined it with a genetic algorithm as a sample case and obtained a surprising result that even the average results over 1,000 runs equalled the best known for most graphs.     

Analysis of Random Restart and Iterated Improvement for Global Optimization with Application to the Traveling Salesman Problem

The optimization method employing iterated improvement with random restart (I2R2) is studied. Associated with each instance of an I2R2 search is a fundamental polynomial, in which the coefficient p_k is the probability of starting a search k improvement steps from a local minimum. The positive root of f can be used to calculate the convergence and speedup properties of that instance.Since the coefficients of f are naturally related to the search, it is possible to estimate them online if an a priori estimate of the size of the goal basin is available, for example by analysis or prior experience. In this case, the runtime statistical estimate of converges many times faster than the estimates of the coefficients themselves.The foregoing is illustrated with an application to the traveling salesman problem (TSP) using the k-change as the improvement discipline. Among other things, it is shown that a k-change improvement can be affected by k 2-changes, that =1 for convex city sets, and that good estimates of can be made from a reduced TSP related to the given one.This research was partially supported by the National Sciences and Engineering Research Council of Canada (NSERC) in the form of a discovery grant. The authors thank the referees for helpful suggestions and timeliness.     

Metaheuristics in Combinatorial Optimization

The emergence of metaheuristics for solving difficult combinatorial optimization problems is one of the most notable achievements of the last two decades in operations research. This paper provides an account of the most recent developments in the field and identifies some common issues and trends. Examples of applications are also reported for vehicle routing and scheduling problems.     

Case-Based Reasoning for Repetitive Combinatorial Optimization Problems, Part II: Numerical Results

This paper presents numerical results from the application of a case-based reasoning approach to several repetitive operations research problems. These experiments are applications of the ideas presented in the previous framework paper, Part I. The three combinatorial optimization problems explored in this paper are the knapsack problem, the travelling salesman problem and the uncapacitated plant location problem. These numerical experiments permit a comparison of the performance of this technique across these three problem classes as well as with the traditional solution algorithms.     

离散变量结构优化设计的组合算法*

本文首先给出了离散变量优化设计局部最优解的定义,然后提出了一种综合的组合算法.该算法采用分级优化的方法,第一级优化首先采用计算效率很高且经过随机抽样性能实验表明性能较高的启发式算法─—相对差商法,求解离散变量结构优化设计问题近似最优解 X ;第二级采用组合算法,在 X 的离散邻集内建立离散变量结构优化设计问题的(-1,0.1)规划模型,再进一步将其化为(0,1)规划模型,应用定界组合算法或相对差商法求解该(0,1)规划模型,求得局部最优解.解决了采用启发式算法无法判断近似最优解是否为局部最优解这一长期未得到解决的问题,提高了计算精度,同时,由于相对差商法的高效率与高精度,以上综合的组合算法的计算效率也还是较高的.     

Circular colorings of edge‐weighted graphs

The notion of (circular) colorings of edge‐weighted graphs is introduced. This notion generalizes the notion of (circular) colorings of graphs, the channel assignment problem, and several other optimization problems. For instance, its restriction to colorings of weighted complete graphs corresponds to the traveling salesman problem (metric case). It also gives rise to a new definition of the chromatic number of directed graphs. Several basic results about the circular chromatic number of edge‐weighted graphs are derived. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 107–116, 2003     

Combinatorial Optimization Problems in Ultrametric Spaces

We study the solutions of some known combinatorial optimization problems including the minimum matching problem, the minimum spanning tree problem, and the traveling salesman problem in d-dimensional p-adic spaces. It appears that the greedy algorithms yield the optimal solutions of these problems in the ultrametric space, which allows obtaining explicit expressions for the estimates of their averages. We study the asymptotic behavior of these averages as the number of points increases infinitely and find some similarities to the Euclidean case, as well as new, unexpected properties.     

The Cross-Entropy Method for Combinatorial and Continuous Optimization

We present a new and fast method, called the cross-entropy method, for finding the optimal solution of combinatorial and continuous nonconvex optimization problems with convex bounded domains. To find the optimal solution we solve a sequence of simple auxiliary smooth optimization problems based on Kullback-Leibler cross-entropy, importance sampling, Markov chain and Boltzmann distribution. We use importance sampling as an important ingredient for adaptive adjustment of the temperature in the Boltzmann distribution and use Kullback-Leibler cross-entropy to find the optimal solution. In fact, we use the mode of a unimodal importance sampling distribution, like the mode of beta distribution, as an estimate of the optimal solution for continuous optimization and Markov chains approach for combinatorial optimization. In the later case we show almost surely convergence of our algorithm to the optimal solution. Supporting numerical results for both continuous and combinatorial optimization problems are given as well. Our empirical studies suggest that the cross-entropy method has polynomial in the size of the problem running time complexity.     

用列队竞争算法解旅行商问题

给出了列队竞争算法解组合优化问题的框架和确定变异邻域的两条原则。用列队竞争算法解旅行商问题获得了满意的结果,显示出列队竞争算法良好的全局搜索性能。     

Matrix representation and gradient flows for NP-hard problems

Over the past decade, a number of connections between continuous flows and numerical algorithms were established. Recently, Brockett and Wong reported a connection between gradient flows on the special orthogonal groupLO(n) and local search solutions for the assignment problem. In this paper, we describe a uniform formulation for certain NP-hard combinatorial optimization problems in matrix form and examine their connection with gradient flows onLO(n). For these problems, there is a correspondence between the so-called 2-opt solutions and asymptotically stable critical points of an associated gradient flow.     

A Stochastic Minimum Cross-Entropy Method for Combinatorial Optimization and Rare-event Estimation*

We present a new method, called the minimum cross-entropy (MCE) method for approximating the optimal solution of NP-hard combinatorial optimization problems and rare-event probability estimation, which can be viewed as an alternative to the standard cross entropy (CE) method. The MCE method presents a generic adaptive stochastic version of Kull-backs classic MinxEnt method. We discuss its similarities and differences with the standard cross-entropy (CE) method and prove its convergence. We show numerically that MCE is a little more accurate than CE, but at the same time a little slower than CE. We also present a new method for trajectory generation for TSP and some related problems. We finally give some numerical results using MCE for rare-events probability estimation for simple static models, the maximal cut problem and the TSP, and point out some new areas of possible applications.AMS 2000 Subject Classification: 65C05, 60C05, 68W20, 90C59*This reseach was supported by the Israel Science Foundation (grant no 191-565).     

Random Tours in the Traveling Salesman Problem: Analysis and Application

Random solutions to the traveling salesman problem (TSP) exhibit statistical regularities across problem instances. These patterns can assist heuristic search for good solutions by providing easy estimates of the length of the optimal tour.     

Pareto Simulated Annealing for Fuzzy Multi-Objective Combinatorial Optimization

The paper presents a metaheuristic method for solving fuzzy multi-objective combinatorial optimization problems. It extends the Pareto simulated annealing (PSA) method proposed originally for the crisp multi-objective combinatorial (MOCO) problems and is called fuzzy Pareto simulated annealing (FPSA). The method does not transform the original fuzzy MOCO problem to an auxiliary deterministic problem but works in the original fuzzy objective space. Its goal is to find a set of approximately efficient solutions being a good approximation of the whole set of efficient solutions defined in the fuzzy objective space. The extension of PSA to FPSA requires the definition of the dominance in the fuzzy objective space, modification of rules for calculating probability of accepting a new solution and application of a defuzzification operator for updating the average position of a solution in the objective space. The use of the FPSA method is illustrated by its application to an agricultural multi-objective project scheduling problem.     

蚁群遗传混合算法

将蚁群遗传混合算法分别求解离散空间的和连续空间优化问题.求解旅行商问题的混合算法是以遗传算法为整个算法的框架,利用了蚁群算法中的信息素特性的进行交叉操作;根据旅行商问题的特点,给出了4种变异策略;针对遗传算法存在的过早收敛问题,加入2-0pt方法对问题求解进行了局部优化.与模拟退火算法、标准遗传算法和标准蚁群算法进行比较,4种混合算法效果都比较好,策略D的混合算法效果最好.求解连续空间优化问题是以蚁群算法为整个算法的框架,加入遗传算法的交叉操作和变异操作,用测试函数验证了混合蚁群算法的正确性.     

求解旅行商问题的一种改进粒子群算法

本文研究了求解旅行商问题的粒子群算法。针对标准粒子群算法在求解旅行商问题过程中容易出现早熟和停滞现象的缺点,提出了一种改进的粒子群算法。首先,在初始种群的选取过程中,利用改进的贪婪策略直接获得具有较高性能的初始种群以提高算法的搜索效率。其次,通过引入次优吸引子,使粒子在搜索过程中可以更加充分地利用群体的信息来提高自身的性能,有效抑制收敛过程中的停滞现象,提高算法的搜索能力。最后为了验证所提出的方法的有效性和可行性,对TSPLIB标准库中的多个实例进行了测试,并给出了数值结果。     

一类含有调和数的组合和

本文给出了含有调和数的一类组合和的求和公式．该公式有二熟知特例．     

Tabu Machine: A New Neural Network Solution Approach for Combinatorial Optimization Problems

A new artificial neural network solution approach is proposed to solve combinatorial optimization problems. The artificial neural network is called the Tabu Machine because it has the same structure as the Boltzmann Machine does but uses tabu search to govern its state transition mechanism. Similar to the Boltzmann Machine, the Tabu Machine consists of a set of binary state nodes connected with bidirectional arcs. Ruled by the transition mechanism, the nodes adjust their states in order to search for a global minimum energy state. Two combinatorial optimization problems, the maximum cut problem and the independent set problem, are used as examples to conduct a computational experiment. Without using overly sophisticated tabu search techniques, the Tabu Machine outperforms the Boltzmann Machine in terms of both solution quality and computation time.