Solving Rectilinear Planar Location Problems with Barriers by a Polynomial Partitioning

This paper considers planar location problems with rectilinear distance and barriers where the objective function is any convex, nondecreasing function of distance. Such problems have a non-convex feasible region and a nonconvex objective function. Based on an equivalent problem with modified barriers, derived in a companion paper [3], the non convex feasible set is partitioned into a network and rectangular cells. The rectangular cells are further partitioned into a polynomial number of convex subcells, called convex domains, on which the distance function, and hence the objective function, is convex. Then the problem is solved over the network and convex domains for an optimal solution. Bounds are given that reduce the number of convex domains to be examined. The number of convex domains is bounded above by a polynomial in the size of the problem.     

求解病态线性方程组的模拟退火算法

病态方程组的条件数较大,当输入数据有微小扰动或计算过程中的舍入误差都可能引起输出数据的很大扰动,使得解严重失真,因此求解此类方程组是相当困难的.本文尝试使用模拟退火算法来求解病态线性方程组,得到了较好的结果,并与传统的求解方法作了简单的比较.     

A Controlled Random Search Technique Incorporating the Simulated Annealing Concept for Solving Integer and Mixed Integer Global Optimization Problems

In this paper, a computational algorithm, named RST2ANU algorithm, has been developed for solving integer and mixed integer global optimization problems. This algorithm, which primarily is based on the original controlled random search approach of Price [22i], incorporates a simulated annealing type acceptance criterion in its working so that not only downhill moves but also occasional uphill moves can be accepted. In its working it employs a special truncation procedure which not only ensures that the integer restrictions imposed on the decision variables are satisfied, but also creates greater possibilities for the search leading to a global optimal solution. The reliability and efficiency of the proposed RST2ANU algorithm has been demonstrated on thirty integer and mixed integer optimization problems taken from the literature. The performance of the algorithm has been compared with the performance of the corresponding purely controlled random search based algorithm as well as the standard simulated annealing algorithm. The performance of the method on mathematical models of three realistic problems has also been demonstrated.     

On the Applicability of Lower Bounds for Solving Rectilinear Quadratic Assignment Problems in Parallel

The quadratic assignment problem (QAP) belongs to the hard core of NP-hard optimization problems. After almost forty years of research only relatively small instances can be solved to optimality. The reason is that the quality of the lower bounds available for exact methods is not sufficient. Recently, lower bounds based on decomposition were proposed for the so called rectilinear QAP that proved to be the strongest for a large class of problem instances. We investigate the strength of these bounds when applied not only at the root node of a search tree but as the bound function used in a Branch-and-Bound code solving large scale QAPs.     

A Distributed Evolutionary Simulated Annealing Algorithm for Combinatorial Optimisation Problems

In this paper, the Evolutionary Simulated Annealing (ESA) algorithm, its distributed implementation (dESA) and its application to two combinatorial problems are presented. ESA consists of a population, a simulated annealing operator, instead of the more usual reproduction operators used in evolutionary algorithms, and a selection operator. The implementation is based on a multi island (agent) system running on the Distributed Resource Machine (DRM), which is a novel, scalable, distributed virtual machine based on Java technology. As WAN/LAN systems are the most common multi-machine systems, dESA implementation is based on them rather than any other parallel machine. The problems tackled are well-known combinatorial optimisation problems, namely, the classical job-shop scheduling problem and the uncapacitated facility location problem. They are difficult benchmarks, widely used to measure the efficiency of metaheuristics with respect to both the quality of the solutions and the central processing unit (CPU) time spent. Both applications show that dESA solves problems finding either the optimum or a very near optimum solution within a reasonable time outperforming the recent reported approaches for each one allowing the faster solution of existing problems and the solution of larger problems.     

On Simulated Annealing and Nested Annealing

Simulated Annealing is a family of randomized algorithms used to solve many combinatorial optimization problems. In practice they have been applied to solve some presumably hard (e.g., NP-complete) problems. The level of performance obtained has been promising [2,5,6,14]. The success of this heuristic technique has motivated analysis of this algorithm from a theoretical point of view. In particular, people have looked at the convergence of this algorithm. They have shown (see e.g., [10]) that this algorithm converges in the limit to a globally optimal solution with probability 1. However few of these convergence results specify a time limit within which the algorithm is guaranteed to converge (with some high probability, say). We present, for the first time, a simple analysis of SA that will provide a time bound for convergence with overwhelming probability. The analysis will hold no matter what annealing schedule is used. Convergence of Simulated Annealing in the limit will follow as a corollary to our time convergence proof. In this paper we also look at optimization problems for which the cost function has some special properties. We prove that for these problems the convergence is much faster. In particular, we give a simpler and more general proof of convergence for Nested Annealing, a heuristic algorithm developed in [12]. Nested Annealing is based on defining a graph corresponding to the given optimization problem. If this graph is small separable, they [12] show that Nested Annealing will converge faster. For an arbitrary optimization problem, we may not have any knowledge about the separability of its graph. In this paper we give tight bounds for the separability of a random graph. We then use these bounds to analyze the expected behavior of Nested Annealing on an arbitrary optimization problem. The separability bounds we derive in this paper are of independent interest and have the potential of finding other applications.     

通过求解输运方程计算壁面距离

壁面距离在当代湍流模化中仍然扮演着关键角色,然而苦于遍历计算壁面距离的高昂代价,该文考虑了求解偏微分方程的途径．基于Eikonal方程构造出类Euler形式的输运方程,这样,可以直接利用求解Euler和Navier-Stokes方程的CFD程序使用的高效数值格式和部分代码．基于北航的MI-CFD(CFD for missles)数值平台,详尽地介绍了该输运方程在直角坐标下的求解过程．使用隐式LUSGS时间推进和迎风空间离散,发现该方程具有鲁棒快速的收敛特性．为了保证精度,网格度量系数必须也迎风插值计算．讨论了初始条件和边界条件的特殊处理．成功应用该壁面距离求解方法计算了几个含1-1对应网格和重叠网格的复杂外形．     

General Purpose Simulated Annealing

This paper reports on an attempt to write a general purpose simulated annealing algorithm, capable of finding good solutions to problems expressed as pure 0-1 integer linear programs. Computational results are given to support the claim that the resulting program might be a useful addition to the arsenal of techniques for researchers and practitioners wishing to tackle certain types of large scale 0-1 ILPs.     

A Simulated Annealing Approach to Bicriteria Scheduling Problems on a Single Machine

In this paper, we apply a simulated annealing approach to two bicriteria scheduling problems on a single machine. The first problem is the strongly NP-hard problem of minimizing total flowtime and maximum earliness. The second one is the NP-hard problem of minimizing total flowtime and number of tardy jobs. We experiment on different neighbourhood structures as well as other parameters of the simulated annealing approach to improve its performance. Our computational experiments show that the developed approach yields solutions that are very close to lower bounds and hence very close to the optimal solutions of their corresponding problems for the minimization of total flowtime and maximum earliness. For the minimization of total flowtime and number tardy, our experiments show that the simulated annealing approach yields results that are superior to randomly generated schedules.     

A Simulated Annealing Approach to the Solution of Flexible Labour Scheduling Problems

This paper presents a new solution approach to the discontinuous labour tour scheduling problem where the objective is to minimize the number of full-time employees required to satisfy forecast demand. Previous heuristic approaches have often limited the number of allowable tours by restricting labour scheduling flexibility in terms of shift length, shift start-times, days-off, meal-break placement, and other factors. These restrictions were essential to the tractability of the heuristic approaches but often resulted in solutions that contained a substantial amount of excess labour. In this study, we relaxed many of the restrictions on scheduling flexibility assumed in previous studies. The resulting problem environment contained more than two billion allowable tours, precluding the use of previous heuristic methods. Consequently, we developed a simulated annealing heuristic for solving the problem. An important facet of this new approach is an ‘intelligent’ improvement routine which eliminates the need for long run-times typically associated with simulated annealing algorithms. The simulated annealing framework does not rely on a special problem structure and our implementation rapidly converged to near-optimal solutions for all problems in the test environment.     

Aspiration Based Simulated Annealing Algorithm

An aspiration based simulated annealing algorithm for continuousvariables has been proposed. The new algorithm is similar to the one givenby Dekkers and Aarts (1991) except that a kind of memory is introduced intothe procedure with a self-regulatory mechanism. The algorithm has beenapplied to a set of standard global optimization problems and a number ofmore difficult, complex, practical problems and its performance comparedwith that of the algorithm of Dekkers and Aarts (1991). The new algorithmappears to offer a useful alternative to some of the currently availablestochastic algorithms for global optimization.     

Expected Distances in Distribution Problems

In many problems in distribution management it is necessary to take account of the expected distances that result from dispatching vehicles to meet customer demand. For example, in mathematical models for determining the optimal location of depots, the sum of radial distances (between customers and the depot), or the sum of the weighted distances, is used as a measure of the delivery "costs". Since actual delivery operations from the depot usually consist of truck-routes with each truck delivering to more than one customer at a time, it is important to know to what extent the above simplification is valid, namely to find a relationship between the actual route-distances and the sum of the radial distances.This paper makes use of an algorithm which plans optimal or near optimal routes to estimate this relationship by solving a large number of randomly generated problems. The discrepancies between the two methods are shown to be significant under certain circumstances.     

Solving Problems with Min-Type Functions by Disjunctive Programming

We consider applications of disjunctive programming to global optimization and problems with equilibrium constraints. We propose a modification of the algorithm of F. Beaumont for disjunctive programming problems and show its numerical efficiency.     

An Efficient Algorithm for Solving the Rectilinear Multifacility Location Problem

One of the efficient methods for solving large rectilinear multifacilitylocation problems is the Direct Search method. The only drawbackof this method lies in the following difficulty. In some situations,when t new facilities are located together at one point, thenumber of arithmetic operations which are needed to establishoptimality is proportional to t²2^t. Therefore the method needsa prohibitive amount of computation time whenever t exceeds,say, 20. This paper gives a simple remedy for this problem.The paper states and proves a new necessary and sufficient optimalitycondition. This condition transforms the problem of computinga descent direction into a constrained linear least-squaresproblem. The latter problem is solved by a relaxation methodthat takes advantage of its special structure. The new techniqueis incorporated into the Direct Search method. This yields animproved algorithm that handles efficiently very large clusters.Numerical results are included.     

Simulated Annealing for noisy cost functions

We generalize a classical convergence result for the Simulated Annealing algorithm to a stochastic optimization context, i.e., to the case where cost function observations are disturbed by random noise. It is shown that for a certain class of noise distributions, the convergence assertion remains valid, provided that the standard deviation of the noise is reduced in the successive steps of cost function evaluation (e.g., by repeated observation) with a speed O(k ^- ), where is an arbitrary constant larger than one.     

Analysis of Static Simulated Annealing Algorithms

Generalized hill climbing (GHC) algorithms provide a framework for modeling local search algorithms to address intractable discrete optimization problems. This paper introduces a measure for determining the expected number of iterations to visit a predetermined objective function level, given that an inferior objective function level has been reached in a finite number of iterations. A variation of simulated annealing (SA), termed static simulated annealing (S²A), is analyzed using this measure. S²A uses a fixed cooling schedule during the algorithm execution. Though S²A is probably nonconvergent, its finite-time performance can be assessed using the finite-time performance measure defined in this paper.     

Solving Partition Problems with Colour-Bipartitions

Polar, monopolar, and unipolar graphs are defined in terms of the existence of certain vertex partitions. Although it is polynomial to determine whether a graph is unipolar and to find whenever possible a unipolar partition, the problems of recognizing polar and monopolar graphs are both NP-complete in general. These problems have recently been studied for chordal, claw-free, and permutation graphs. Polynomial time algorithms have been found for solving the problems for these classes of graphs, with one exception: polarity recognition remains NP-complete in claw-free graphs. In this paper, we connect these problems to edge-coloured homomorphism problems. We show that finding unipolar partitions in general and finding monopolar partitions for certain classes of graphs can be efficiently reduced to a polynomial-time solvable 2-edge-coloured homomorphism problem, which we call the colour-bipartition problem. This approach unifies the currently known results on monopolarity and extends them to new classes of graphs.     

An Interactive Method for 0-1 Multiobjective Problems Using Simulated Annealing and Tabu Search

This paper presents an interactive method for solving general 0-1 multiobjective linear programs using Simulated Annealing and Tabu Search. The interactive protocol with the decision maker is based on the specification of reservation levels for the objective function values. These reservation levels narrow the scope of the search in each interaction in order to identify regions of major interest to the decision maker. Metaheuristic approaches are used to generate potentially nondominated solutions in the computational phases. Generic versions of Simulated Annealing and Tabu Search for 0-1 single objective linear problems were developed which include a general routine for repairing unfeasible solutions. This routine improves significantly the results of single objective problems and, consequently, the quality of the potentially nondominated solutions generated for the multiobjective problems. Computational results and examples are presented.     

Image Restoration Using Modifications of Simulated Annealing

Abstract

This article uses a modified version of the simulated annealing algorithm to restore degraded spatial patterns. Standard simulated annealing is used to find an image that is a posterior mode when the number of images under consideration precludes sequential search for a maximum. I incorporate jumping probabilities of the annealing algorithm without randomization. The convergence of our algorithm is proven under a practical annealing schedule. The same idea is also implemented to improve the performance of other modifications of simulated annealing. These include forcing proportions of labels in an image, using posterior marginals, and incorporating an edge process. This article also studies nonlinear presmoothing of the observations.