Solving the post enrolment course timetabling problem by ant colony optimization

In this work we present a new approach to tackle the problem of Post Enrolment Course Timetabling as specified for the International Timetabling Competition 2007 (ITC2007), competition track 2. The heuristic procedure is based on Ant Colony Optimization (ACO) where artificial ants successively construct solutions based on pheromones (stigmergy) and local information. The key feature of our algorithm is the use of two distinct but simplified pheromone matrices in order to improve convergence but still provide enough flexibility for effectively guiding the solution construction process. We show that by parallelizing the algorithm we can improve the solution quality significantly. We applied our algorithm to the instances used for the ITC2007. The results document that our approach is among the leading algorithms for this problem; in all cases the optimal solution could be found. Furthermore we discuss the characteristics of the instances where the algorithm performs especially well.     

A stochastic gradient type algorithm for closed-loop problems

We focus on the numerical solution of closed-loop stochastic problems, and propose a perturbed gradient algorithm to achieve this goal. The main hurdle in such problems is the fact that the control variables are infinite-dimensional, due to, e.g., the information constraints. Alternatively said, control variables are feedbacks, i.e., functions. Such controls have hence to be represented in a finite way in order to solve the problem numerically. In the same way, the gradient of the criterion is itself an infinite-dimensional object. Our algorithm replaces this exact (and unknown) gradient by a perturbed one, which consists of the product of the true gradient evaluated at a random point and a kernel function which extends this gradient to the neighbourhood of the random point. Proceeding this way, we explore the whole space iteration after iteration through random points. Since each kernel function is perfectly known by a small number of parameters, say N, the control at iteration k is perfectly known as an infinite-dimensional object by at most N × k parameters. The main strength of this method is that it avoids any discretization of the underlying space, provided that we can sample as many points as needed in this space. Moreover, our algorithm can take into account the possible measurability constraints of the problem in a new way. Finally, the randomized strategy implemented by the algorithm causes the most probable parts of the space to be the most explored ones, which is a priori an interesting feature. In this paper, we first prove two convergence results of this algorithm in the strongly convex and convex cases, and then give some numerical examples showing the interest of this method for practical stochastic optimization problems. In Memoriam: Jean-Sébastien Roy passed away July 04, 2007. He was 33 years old.     

An implicit Euler scheme with non-uniform time discretization for heat equations with multiplicative noise

We present an algorithm for solving stochastic heat equations, whose key ingredient is a non-uniform time discretization of the driving Brownian motion W. For this algorithm we derive an error bound in terms of its number of evaluations of one-dimensional components of W. The rate of convergence depends on the spatial dimension of the heat equation and on the decay of the eigenfunctions of the covariance of W. According to known lower bounds, our algorithm is optimal, up to a constant, and this optimality cannot be achieved by uniform time discretizations. AMS subject classification (2000)  60H15, 60H35, 65C30     

Computing the variance of tour costs over the solution space of the TSP in polynomial time

We give an O(n ²) time algorithm to find the population variance of tour costs over the solution space of the n city symmetric Traveling Salesman Problem (TSP). The algorithm has application in both the stochastic case, where the problem is specified in terms of edge costs which are pairwise independently distributed random variables with known mean and variance, and the numeric edge cost case. We apply this result to provide empirical evidence that, in a range of real world problem sets, the optimal tour cost correlates with a simple function of the mean and variance of tour costs.     

Finding an Oriented Hamiltonian Path in a Tournament

We present an O(n²) algorithm for finding a specified oriented path of order at least n in a tournament of order n. Using this algorithm, we present an O(n²) algorithm that finds a specified oriented path from a given vertex if one exists.     

A probabilistic interpretation and stochastic particle approximations of the 3-dimensional Navier-Stokes equations

We develop a probabilistic interpretation of local mild solutions of the three dimensional Navier-Stokes equation in the L^p spaces, when the initial vorticity field is integrable. This is done by associating a generalized nonlinear diffusion of the McKean-Vlasov type with the solution of the corresponding vortex equation. We then construct trajectorial (chaotic) stochastic particle approximations of this nonlinear process. These results provide the first complete proof of convergence of a stochastic vortex method for the Navier-Stokes equation in three dimensions, and rectify the algorithm conjectured by Esposito and Pulvirenti in 1989. Our techniques rely on a fine regularity study of the vortex equation in the supercritical L^p spaces, and on an extension of the classic McKean-Vlasov model, which incorporates the derivative of the stochastic flow of the nonlinear process to explain the vortex stretching phenomenon proper to dimension three. Supported by Fondecyt Project 1040689 and Nucleus Millennium Information and Randomness ICM P01-005.     

Solving the Vehicle Routing Problem with Stochastic Demands using the Cross-Entropy Method

An alternate formulation of the classical vehicle routing problem with stochastic demands (VRPSD) is considered. We propose a new heuristic method to solve the problem, based on the Cross-Entropy method. In order to better estimate the objective function at each point in the domain, we incorporate Monte Carlo sampling. This creates many practical issues, especially the decision as to when to draw new samples and how many samples to use. We also develop a framework for obtaining exact solutions and tight lower bounds for the problem under various conditions, which include specific families of demand distributions. This is used to assess the performance of the algorithm. Finally, numerical results are presented for various problem instances to illustrate the ideas.     

A Deterministic Algorithm for Approximating the Mixed Discriminant and Mixed Volume, and a Combinatorial Corollary

Abstract. We present a deterministic polynomial-time algorithm that computes the mixed discriminant of an n -tuple of positive semidefinite matrices to within an exponential multiplicative factor. To this end we extend the notion of doubly stochastic matrix scaling to a larger class of n -tuples of positive semidefinite matrices, and provide a polynomial-time algorithm for this scaling. As a corollary, we obtain a deterministic polynomial algorithm that computes the mixed volume of n convex bodies in R ⁿ to within an error which depends only on the dimension. This answers a question of Dyer, Gritzmann and Hufnagel. A ``side benefit' is a generalization of Rado's theorem on the existence of a linearly independent transversal.     

Decomposition of test sets in stochastic integer programming

 We study Graver test sets for linear two-stage stochastic integer programs and show that test sets can be decomposed into finitely many building blocks whose number is independent on the number of scenarios of the stochastic program. We present a finite algorithm to compute the building blocks directly, without prior knowledge of test set vectors. Once computed, building blocks can be employed to solve the stochastic program by a simple augmentation scheme, again without explicit knowledge of test set vectors. Finally, we report preliminary computational experience. Received: March 14, 2002 / Accepted: March 27, 2002 Published online: September 27, 2002 Key words. test sets – stochastic integer programming – decomposition methods Mathematics Subject Classification (2000): 90C15, 90C10, 13P10     

An efficient string sorting algorithm for weighing matrices of small weight

In this paper, we demonstrate that the search for weighing matrices of small weights constructed from two circulants can be viewed as a string sorting problem together with a linear time algorithm to locate common strings in two sorted arrays. We also introduce a sparse encoding of the periodic autocorrelation function vector, based on concepts from Algorithmic Information Theory, also known as Kolmogorov complexity, that allows us to speed up the algorithm considerably. Finally, we use these ideas to find new weighing matrices W(2 · n, 9) constructed from two circulants, for many values of n in the range 100 ≤  n ≤  300. These matrices are given here for the first time. We also discuss briefly a connection with Combinatorial Optimization.     

Tabu Search When Noise is Present: An Illustration in the Context of Cause and Effect Analysis

In the field of combinatorial optimization, it may be possible to more accurately represent reality through stochastic models rather than deterministic ones. When randomness is present in a problem, algorithm designers face new difficulties which complicate their task significantly. Finding a proper mathematical formulation and a fast evaluation of the objective function are two major issues. In this paper we propose a new tabu search algorithm based on sampling and statistical tests. The algorithm is shown to perform well in a stochastic environment where the quality of feasible solutions cannot be computed easily. This new search principle is illustrated in the field of cause and effect analysis where the true cause of an undesirable effect needs to be eliminated. A set of n potential causes is identified and each of them is assumed to be the true cause with a given probability. The time to investigate a cause is a random variable with a known probability distribution. Associated with each cause is the reward obtained if the cause is really the true cause. The decision problem is to sequence the n potential causes so as to maximize the expected reward realized before a specified time horizon.     

The randomized algorithm for finding an eigenvector of the stochastic matrix with application to PageRank

The problem of finding the eigenvector corresponding to the largest eigenvalue of a stochastic matrix has numerous applications in ranking search results, multi-agent, consensus, networked control and data mining. The power method is a typical tool for its solution. However randomized methods could be competitors vs standard ones; they require much less calculations for one iteration and are well tailored for distributed computations. We propose a new randomized algorithm and provide upper bound for its rate of convergence which is O(lnN/n), where N is the dimension and n is the number of iterations. The bound looks promising because lnN is not large even for very high dimensions. The algorithm is based on the mirror-descent method for convex stochastic optimization. Applications to PageRank problem are discussed. Published in Russian in Doklady Akademii Nauk, 2009, Vol. 426, No. 6, pp. 734–737. Presented by Academician S.N. Vasil’ev February 9, 2009 The article was translated by the authors.     

Multiset Permutations and Loopless Generation of Ordered Trees with Specified Degree Sequence

An ordered tree with specified degree sequence and n internal nodes has a_i nodes of degree i, where a₀ = 1 + ∑_i = 1(i − 1)a_i and n = ∑_i = 0a_i. This paper presents the first loopless algorithm for generating all ordered trees with specified degree sequence. It uses a new version of the algorithm for generating multiset permutations. When a_k = N, a₀ = (k − 1)N + 1, and all other a_i's are 0, all N node k-ary trees are generated.     

The Valuation of American Options with Stochastic Stopping Time Constraints

Abstract

This paper concerns the pricing of American options with stochastic stopping time constraints expressed in terms of the states of a Markov process. Following the ideas of Menaldi et al., we transform the constrained into an unconstrained optimal stopping problem. The transformation replaces the original payoff by the value of a generalized barrier option. We also provide a Monte Carlo method to numerically calculate the option value for multidimensional Markov processes. We adapt the Longstaff–Schwartz algorithm to solve the stochastic Cauchy–Dirichlet problem related to the valuation problem of the barrier option along a set of simulated trajectories of the underlying Markov process.     

Existence and global attractiveness of a pseudo almost periodic solution in p-th mean sense for stochastic evolution equation driven by a fractional Brownian motion

In this work, we establish a new concept of pseudo almost periodic processes in p-th mean sense using the measure theory. We use the μ-ergodic process to define the spaces of μ-pseudo almost periodic process in the p-th mean sense. We establish many interesting results on the functional space of such processes like completeness and composition theorems. The main objective of this paper is to use those results and some stochastic analysis approaches to study the existence, the uniqueness and the global attractiveness for a μ-pseudo almost periodic mild solution to a class of abstract stochastic evolution equations driven by fractional Brownian motion. We provide an example to illustrate our results.     

Estimation of an optimal solution of a LP problem with unknown objective function

We consider a linear programming problem with unknown objective function. Random observations related to the unknown objective function are sequentially available. We define a stochastic algorithm, based on the simplex method, that estimates an optimal solution of the linear programming problem. It is shown that this algorithm converges with probability one to the set of optimal solutions and that its failure probability is of order inversely proportional to the sample size. We also introduce stopping criteria for the algorithm. The asymptotic normality of some suitably defined residuals is also analyzed. The proposed estimation algorithm is motivated by the stochastic approximation algorithms but it introduces a generalization of these techniques when the linear programming problem has several optimal solutions. The proposed algorithm is also close to the stochastic quasi-gradient procedures, though their usual assumptions are weakened.Mathematics Subject Classification (2000): 90C05, 62L20, 90C15Acknowledgments. I would like to thank two unknown referees for their fruitful suggestions that have helped to improve the paper.     

Control Improvement for Jump-Diffusion Processes with Applications to Finance

We consider stochastic control problems with jump-diffusion processes and formulate an algorithm which produces, starting from a given admissible control π, a new control with a better value. If no improvement is possible, then π is optimal. Such an algorithm is well-known for discrete-time Markov Decision Problems under the name Howard’s policy improvement algorithm. The idea can be traced back to Bellman. Here we show with the help of martingale techniques that such an algorithm can also be formulated for stochastic control problems with jump-diffusion processes. As an application we derive some interesting results in financial portfolio optimization.     

An alternative procedure for selecting a good value for the parameter <Emphasis Type="Italic">c</Emphasis> in RBF-interpolation

The impact of the scaling parameter c on the accuracy of interpolation schemes using radial basis functions (RBFs) has been pointed out by several authors. Rippa (Adv Comput Math 11:193–210, 1999) proposes an algorithm based on the idea of cross validation for selecting a good such parameter value. In this paper we present an alternative procedure, that can be interpreted as a refinement of Rippa’s algorithm for a cost function based on the euclidean norm. We point out how this method is related to the procedure of maximum likelihood estimation, which is used for identifying covariance parameters of stochastic processes in spatial statistics. Using the same test functions as Rippa we show that our algorithm compares favorably with cross validation in many cases and discuss its limitations. Finally we present some computational aspects of our algorithm.     

Hybrid Population-Based Algorithms for the Bi-Objective Quadratic Assignment Problem

We present variants of an ant colony optimization (MO-ACO) algorithm and of an evolutionary algorithm (SPEA2) for tackling multi-objective combinatorial optimization problems, hybridized with an iterative improvement algorithm and the robust tabu search algorithm. The performance of the resulting hybrid stochastic local search (SLS) algorithms is experimentally investigated for the bi-objective quadratic assignment problem (bQAP) and compared against repeated applications of the underlying local search algorithms for several scalarizations. The experiments consider structured and unstructured bQAP instances with various degrees of correlation between the flow matrices. We do a systematic experimental analysis of the algorithms using outperformance relations and the attainment functions methodology to asses differences in the performance of the algorithms. The experimental results show the usefulness of the hybrid algorithms if the available computation time is not too limited and identify SPEA2 hybridized with very short tabu search runs as the most promising variant. This research was mainly done while Luís Paquete and Thomas Stützle were with the Intellectics Group at the Computer Science Department of Darmstadt University of Technology, Germany