Multi-stage scheduling problems with precedence constraints

Abstract not available

Preface [Special Issue: International Symposium on Combinatorial Optimisation (CO2000)]

Preface [Special Issue containing a selection of papers presented at the International Symposium on Combinatorial Optimisation (CO2000) held at the University of Greenwich, London, from 12-14 July 2000.

Multilevel refinement for combinatorial optimisation problems

We consider the multilevel paradigm and its potential to aid the solution of combinatorial optimisation problems. The multilevel paradigm is a simple one, which involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found (sometimes for the original problem, sometimes the coarsest) and then iteratively refined at each level. As a general solution strategy, the multilevel paradigm has been in use for many years and has been applied to many problem areas (most notably in the form of multigrid techniques). However, with the exception of the graph partitioning problem, multilevel techniques have not been widely applied to combinatorial optimisation problems. In this paper we address the issue of multilevel refinement for such problems and, with the aid of examples and results in graph partitioning, graph colouring and the travelling salesman problem, make a case for its use as a metaheuristic. The results provide compelling evidence that, although the multilevel framework cannot be considered as a panacea for combinatorial problems, it can provide an extremely useful addition to the combinatorial optimisation toolkit. We also give a possible explanation for the underlying process and extract some generic guidelines for its future use on other combinatorial problems.

Multilevel refinement for combinatorial optimisation: boosting metaheuristic performance

The multilevel paradigm as applied to combinatorial optimisation problems is a simple one, which at its most basic involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found, usually at the coarsest level, and then iteratively refined at each level, coarsest to finest, typically by using some kind of heuristic optimisation algorithm (either a problem-specific local search scheme or a metaheuristic). Solution extension (or projection) operators can transfer the solution from one level to another. As a general solution strategy, the multilevel paradigm has been in use for many years and has been applied to many problem areas (for example multigrid techniques can be viewed as a prime example of the paradigm). Overview papers such as [] attest to its efficacy. However, with the exception of the graph partitioning problem, multilevel techniques have not been widely applied to combinatorial problems and in this chapter we discuss recent developments. In this chapter we survey the use of multilevel combinatorial techniques and consider their ability to boost the performance of (meta)heuristic optimisation algorithms.

[Conference report] Magic and mathematics: The life and work of John Dee. National Maritime Museum, Greenwich, 13-14 June 2003

Tony Mann provides a report of a two-day meeting "Magic and mathematics: The life and work of John Dee" held from 13-14 June 2003 at the National Maritime Museum, Greenwich.

[Book review] Mathematics and Culture II

Review of Mathematics and Culture II. Visual Perfection: Mathematics and Creativity, Michele Emmer (Ed.), Springer, 2005 ISBN: 978-3-540-21368-0

BSHM meetings: BMS History of Mathematics Splinter Group

Introduction to abstracts from papers given at BMS History of Mathematics Splinter Group, held 17 April 2007, in Swansea.

BSHM meetings: British Mathematics Colloquium

Report on the British Mathematics Colloquium, which took place in York, 25-28 March 2008. Also includes abstracts of the individual talks.

Multilevel approaches applied to the capacitated clustering problem

This paper presents two multilevel refinement algorithms for the capacitated clustering problem. Multilevel refinement is a collaborative technique capable of significantly aiding the solution process for optimisation problems. The central methodologies of the technique are filtering solutions from the search space and reducing the level of problem detail to be considered at each level of the solution process. The first multilevel algorithm uses a simple tabu search while the other executes a standard local search procedure. Both algorithms demonstrate that the multilevel technique is capable of aiding the solution process for this combinatorial optimisation problem.

[BSHM meetings] Topics in the history of financial mathematics: early commerce to chaos in modern stock markets

This account provides an overview of the study day, entitled 'Topics in the History of Financial Mathematics: Early commerce to chaos in modern stock markets,' held by the British Society for the History of Mathematics jointly with Gresham College, at Gresham College, London on 25th April 2008. The series of talks explored the development of mathematics and mathematical techniques in a commercial and financial context.

Reviews: making mathematics with needlework

Review of Making Mathematics with Needlework, edited by Sarah-Marie Belcastro and Carolyn Yackel, published by AK Peters Ltd, 2007 (ISBN 978-1-56881-331-8).

[Book review] Collaborative learning in mathematics

Review of: Collaborative Learning in Mathematics: A challenge to our beliefs and practices by Malcolm Swan, National Institute of Adult Continuing Education, paperback £24.95, ISBN 981-1-86201-311-7; hardback £44.95, ISBN 978-1-86201-316-2.