Simulated Annealing and Genetic Algorithms for the Facility Layout Problem: A Survey

The facility layout problem (FLP) has many practical applications and is known to be NP-hard. During recent decades exact and heuristic approaches have been proposed in the literature to solve FLPs. In this paper we review the most recent developments regardingsimulated annealing and genetic algorithms for solvingfacility layout problems approximately.     

Combinatorial optimization - Polyhedra and efficiency: A book review

We review the recent three-volume monograph authored by Alexander Schrijver, Combinatorial Optimization - Polyhedra and Efficiency, Springer-Verlag, 2003, ISBN 3-540-44389-4, 1881 pages (in a slip-case), price: € 89,95 .Received: November 2003, Revised: January 2004, AMS classification: 90C57, 68R10, 05C99     

Optimization of transit route network,vehicle headways and timetables for large-scale transit networks

This paper presents a metaheuristic method for optimizing transit networks, including route network design, vehicle headway, and timetable assignment. Given information on transit demand, the street network of the transit service area, and total fleet size, the goal is to identify a transit network that minimizes a passenger cost function. Transit network optimization is a complex combinatorial problem due to huge search spaces of route network, vehicle headways, and timetables. The methodology described in this paper includes a representation of transit network variable search spaces (route network, headway, and timetable); a user cost function based on passenger random arrival times, route network, vehicle headways, and timetables; and a metaheuristic search scheme that combines simulated annealing, tabu, and greedy search methods. This methodology has been tested with problems reported in the existing literature, and applied to a large-scale realistic network optimization problem. The results show that the methodology is capable of producing improved solutions to large-scale transit network design problems in reasonable amounts of time and computing resources.     

Globally Convergent Optimization Algorithms on Riemannian Manifolds: Uniform Framework for Unconstrained and Constrained Optimization

This paper proposes several globally convergent geometric optimization algorithms on Riemannian manifolds, which extend some existing geometric optimization techniques. Since any set of smooth constraints in the Euclidean space R ⁿ (corresponding to constrained optimization) and the R ⁿ space itself (corresponding to unconstrained optimization) are both special Riemannian manifolds, and since these algorithms are developed on general Riemannian manifolds, the techniques discussed in this paper provide a uniform framework for constrained and unconstrained optimization problems. Unlike some earlier works, the new algorithms have less restrictions in both convergence results and in practice. For example, global minimization in the one-dimensional search is not required. All the algorithms addressed in this paper are globally convergent. For some special Riemannian manifold other than R ⁿ , the new algorithms are very efficient. Convergence rates are obtained. Applications are discussed. This paper is based on part of the Ph.D Thesis of the author under the supervision of Professor Tits, University of Maryland, College Park, Maryland. The author is in debt to him for invaluable suggestions on earlier versions of this paper. The author is grateful to the Associate Editor and anonymous reviewers, who pointed out a number of papers that have been included in the references; they made also detailed suggestions that lead to significant improvements of the paper. Finally, the author thanks Dr. S.T. Smith for making available his Ph.D Thesis.     

Algorithms,genetics, and populations: The schemata theorem revisited

Models for the genetic evolution of natural populations have supplied the inspiration for the adaptive computer algorithms known as “genetic algorithms.” In its original form, a genetic algorithm simulates the evolution of a haploid population: Genetic variation is produced by mutation at a number of genetic loci in a chromosome, represented as a string of bits, and the variants in the various chromosomes are reshuffled by genetic recombination. In nature, the ability of a haploid individual to survive and reproduce is expressed as its fitness; in computer science the value of a string is measured by its ability to program a given task. The performance of genetic algorithms is evaluated in the “schemata theorem,” which we present and discuss in the context of the population genetics of multiple loci and propose a generalization of the theorem. © 1998 John Wiley & Sons, Inc.     

Multi-Item, Multi-Facility Supply Chain Planning: Models, Complexities, and Algorithms

We propose a planning model for products manufactured across multiple manufacturing facilities sharing similar production capabilities. The need for cross-facility capacity management is most evident in high-tech industries that have capital-intensive equipment and a short technology life cycle. We propose a multicommodity flow network model where each commodity represents a product and the network structure represents manufacturing facilities in the supply chain capable of producing the products. We analyze in depth the product-level (single-commodity, multi-facility) subproblem when the capacity constraints are relaxed. We prove that even the general-cost version of this uncapacitated subproblem is NP-complete. We show that there exists an optimization algorithm that is polynomial in the number of facilities, but exponential in the number of periods. We further show that under special cost structures the shortest-path algorithm could achieve optimality. We analyze cases when the optimal solution does not correspond to a source-to-sink path, thus the shortest path algorithm would fail. To solve the overall (multicommodity) planning problem we develop a Lagrangean decomposition scheme, which separates the planning decisions into a resource subproblem, and a number of product-level subproblems. The Lagrangean multipliers are updated iteratively using a subgradient search algorithm. Through extensive computational testing, we show that the shortest path algorithm serves as an effective heuristic for the product-level subproblem (a mixed integer program), yielding high quality solutions with only a fraction (roughly 2%) of the computer time.     

Quadratic harnesses, -commutations, and orthogonal martingale polynomials

We introduce the quadratic harness condition and show that integrable quadratic harnesses have orthogonal martingale polynomials with a three step recurrence that satisfies a -commutation relation. This implies that quadratic harnesses are essentially determined uniquely by five numerical constants. Explicit recurrences for the orthogonal martingale polynomials are derived in several cases of interest.

     

-isomorphisms, Jordan isomorphisms, and numerical range preserving maps

Let or , where is the algebra of a bounded linear operator acting on the Hilbert space , and is the set of self-adjoint operators in . Denote the numerical range of by It is shown that a surjective map satisfies

if and only if there is a unitary operator such that has the form

where is the transpose of with respect to a fixed orthonormal basis. In other words, the map or is a -isomorphism on and a Jordan isomorphism on . Moreover, if has finite dimension, then the surjective assumption on can be removed.

     

Biomimicry of Social Foraging Bacteria for Distributed Optimization: Models,Principles, and Emergent Behaviors

In this paper, we explain the social foraging behavior of E. coli and M. xanthus bacteria and develop simulation models based on the principles of foraging theory that view foraging as optimization. This provides us with novel models of their foraging behavior and with new methods for distributed nongradient optimization. Moreover, we show that the models of both species of bacteria exhibit the property identified by Grunbaum that postulates that their foraging is social in order to be able to climb noisy gradients in nutrients. This provides a connection between evolutionary forces in social foraging and distributed nongradient optimization algorithm design for global optimization over noisy surfaces.     

Finite Affine Groups: Cycle Indices, Hall–Littlewood Polynomials, and Probabilistic Algorithms

The study of asymptotic properties of the conjugacy class of a random element of the finite affine group leads one to define a probability measure on the set of all partitions of all positive integers. Four different probabilistic understandings of this measure are given—three using symmetric function theory and one using Markov chains. This leads to non-trivial enumerative results. Cycle index generating functions are derived and are used to compute the large dimension limiting probabilities that an element of the affine group is separable, cyclic, or semisimple and to study the convergence to these limits. The semisimple limit involves both Rogers–Ramanujan identities. This yields the first examples of such computations for a maximal parabolic subgroup of a finite classical group.     

Random series in using unconditional basic sequences and stable sequences: A result on almost sure almost everywhere convergence

Here we study the almost sure almost everywhere convergence of random series of the form in the Lebesgue spaces , where the 's are centered random variables, and the 's constitute an unconditional basic sequence or an stable sequence. We show that if one of these series converges in the norm topology almost surely, then it converges almost everywhere almost surely.

     

Artillerymen and mathematicians: Forest Ray Moulton and changes in American exterior ballistics, 1885–1934

Mathematical ballistics in the United States until the First World War was largely dependent on the work of European authors such as Francesco Siacci of Italy. The war brought with it a call to the American mathematical community for participation in ballistics problems. The community responded by sending mathematicians to work at newly formed ballistics research facilities at Aberdeen Proving Grounds and Washington, D.C. This paper focuses on the efforts of Forest Ray Moulton and details how he dealt with various aspects of a single problem: differential variations in the ballistic trajectory due to known factors.     

基于Projection Pursuit-RAGA-NK-GERT的质量绩效提升路径优化——以组织质量特异性免疫和产品生命周期为主导逻辑的解释框架

依据组织免疫和组织质量特异性免疫的相关理论,引入情境变量产品生命周期,构建基于组织质量监视、组织质量防御软要素、组织质量防御硬要素和组织质量记忆的质量绩效提升路径理论框架。使用基于RAGA的投影寻踪模型、适应度景观和NK模型对产品生命周期不同阶段的质量绩效提升路径进行实证分析,实证结果表明:产品生命周期不同阶段有不同的质量绩效提升路径,产品导入期遵循的质量绩效提升路径为组织质量监视→组织质量防御→组织质量记忆,产品成长期遵循的质量绩效提升路径为组织质量防御软要素→组织质量防御硬要素→组织质量监视→组织质量记忆,产品成熟期遵循的质量绩效提升路径为组织质量防御硬要素→组织质量防御软要素→组织质量监视→组织质量记忆,产品衰退期遵循的质量绩效提升路径为组织质量记忆→组织质量监视→组织质量防御。并建立产品生命周期不同阶段质量绩效提升路径优化的GERT网络,优化产品生命周期不同阶段的质量绩效提升路径。     

Corrigendum: The cover time of the giant component of a random graph,Random Structures and Algorithms 32 (2008), 401–439

The above paper gives an asymptotically precise estimate of the cover time of the giant component of a sparse random graph. The proof as it stands is not tight enough, and in particular, Eq. (64) is not strong enough to prove (65). The o(1) term in (64) needs to be improved to o(1/(lnn)²) for (65) to follow. The following section, which replaces Section 3.6, amends this oversight. The notation and definitions are from the paper. A further correction is needed. Property P2 claims that the conductance of the giant is whp , Ω(1/lnn). The proof of P2 in the appendix of the paper is not quite complete. A complete proof of Property P2 can be found in 1 , 2 . © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009