During the 1990’s, there has been a growing interest in local search. OR practitioners are finding local search to be a useful technique for tackling a wide range of problems. Moreover, researchers are designing new local search methods and improving existing methods. The Local Search Special Interest Group was established in 1999 to provide a forum through which these groups of practitioners and researchers can meet.

The Special Interest Group covers local search in its broadest sense. Thus, in addition to the classical local search techniques such as simulated annealing, tabu search and genetic algorithms, related methods such as constraint satisfaction and neural networks also lie within the range of interests of the Special Interest Group.

The aims of the Special Interest Group are:

1. To stimulate the development and application of local search methods through meetings attended by academics and operational research practitioners.
2. To provide a forum for the exchange of ideas on local search.
3. To inform members of the latest developments in local search.

There will be a regular series of meetings. Although many of these will be based in London, a significant number are to be held at other locations. Some meetings will be joint with regional societies or with other special interest Groups.

For the latest on the Local Search Special Interest Group, why not join the mailing list. Receive the news by email and circulate any messages of your own.

Workshop & Research Meeting on Competitive Location Problems
Organised jointly by Prof Said Salhi (Centre for Logistics & Heuristic Optimisation, Kent Business School, University of Kent, UK, and the Local Search Interest Group of the Operational Research Society) and Prof Blas Pelegrin (Dept of Stats & OR, Faculty of Mathematics, and the Operational Research Group of the University of Murcia, Spain). Sponsored Partly by the European Development Fund (ERDF) and the Spanish Ministry of Science and innovation.
Date: March 24-25, 2010
Venue: Kent Business School (KBS), University of Kent, Canterbury.

• Wednesday 24th March (Board Room, KBS)
  Session 1 (10.00-12.00): Heuristic/Exact Methods for Competitive Location Problems
  - Exact branch-and-bound methods and heuristic algorithms for competitive location problems (Jose Fernández, Dpt. of Statistics and Operational Research, University of Murcia, Spain)
  - Solving the location-price problem with capacities (Pascual Fernández, Dpt. of Statistics and Operational Research, University of Murcia, Spain)
  Session 2 (15.00-17.00): The Maxcap Problem
  - Robustness analysis for the maxcap problem (S.Salhi, Kent Business School, University of Kent)
  - The maxcap problem with prices (Frank Plastria, Vrij Universiteit Brussel, Belgium)
• Thursday 25th March (SR1, KBS)
  Session 3 (10-12):Nash Equilibria in Competitive Location
  - On Nash equilibra in continuous design-location & horizontal co-operation. (Eligius Hendrix, Wageningen University, The Netherlands)
  - On Nash equilibia and Weber problem (Blas Pelegrin, Dpt. of Statistics and Operational Research, University of Murcia, Spain)

LANCS Initiative: Putting Theory into Practice
Workshop on Understanding Heuristics
Organised by the School of Mathematics, Cardiff University (Dr J.Thompson) and Local Search ORS special interest group (Prof S. Salhi, Kent)
Date/Time: Wednesday &Thursday, 13th and 14th January 2010
Venue: School of Mathematics, Cardiff University

Purpose
Present current research already underway in this area
Consider general insights into how we might “understand heuristics”
Discuss the directions research in this cluster should proceed
Develop small research groups and projects that will bring different researchers together
Confirmed Speakers and Subject Areas:
Prof Anatoly Zhijlgavsky ( Cardiff University) - Stochastic Global Optimization and Population Based Algorithms and Markov Chains
Prof Mike Wright ( Lancaster) - Parameter Optimization
Dr Adam Prugel-Bennett (Southampton) - Phase Transition Analysis
Prof Chingbu Chu  ( Troyes) - Worst Case Analysis
Dr Xiang Song ( Cardiff) - The use of Bounds in understanding heuristics
Dr Jingpeng Li ( Nottingham) - A Markov Chain Model on Evolutionary Squeaky Wheel Optimization
Prof Said Salhi ( Kent) - Integration of heuristic and exact methods: Application to location and routing problems

New Heuristics for Some Routing Problems
Speaker: Professor M.Grazia Speranza (University of Brescia – Italy)
Date/Time: Wednesday 18th February 2009
Venue: Symposium Room ( Kent Business School), University of Kent, Canterbury, CT2 7PE

Abstract: In this talk I will present several heuristic approaches for different routing problems. Feasible and infeasible tabu search and variable neighbourhood search meta heuristics will be presented for two routing problems with profits, namely the capacitated team orienteering and profitable tour problems. An optimization-based heuristic for the split delivery vehicle routing problem will be described; the heuristic uses the information collected during a tabu search heuristic to improve the solution obtained by the tabu search. Finally, a hybrid heuristic for an inventory routing problem will be proposed that embeds mixed integer linear programming models into a tabu search scheme to explore promising parts of the solution space. Computational results will show the effectiveness of the different heuristics.
This talk is jointly organised by the ORS Local Search Group and the Centre for Heuristic Optimisation (CHO). For more information contact Professor Said Salhi.

Guided Local Search in Workforce Scheduling
Speaker: Professor Edward Tsang ( University of Essex) Email: edward@essex.ac.uk
Date/Time: Friday 27th June 2008 at 4pm
Venue: Room: 1N1.4.1 ( Network Building, Square 1), Department of Computer Science, University of Essex.

• Abstract: Guided Local Search is a simple meta-heuristic search algorithm. Its effectiveness has been demonstrated in a number of problems, including classical problem such as the travelling salesman problem and applications such as the vehicle routing problem. In this talk, I shall explain its application in a workforce scheduling problem. Applications drive research: they help to highlight where research should be focussed on. This application goes beyond heuristic search. Like all real-life applications, modelling is crucial. However, models can only be evaluated properly when efficiency and versatility optimization methods are available. We demonstrate that Guided Local Search can be a reliable method in the tools box. Although this research is motivated by BT’s problem, the solution is intended to be general. Guided Local Search is a general method which has been studied thoroughly. I shall go through some of those studies in this talk

Application of Evolutionary Heuristics to the Protein Folding Problem
Speaker: Prof Roy L Johnston, School of Chemistry, University of Birmingham
Date/Time: Wednesday the 23rd January 2008 at 2pm
Venue: The Symposium, Kent Business School, University of Kent, Canterbury

• Abstract:
  The protein folding problem refers to the prediction of the 3-D folded structure of a protein based on knowledge of its primary structure, i.e. the 1-D sequence of amino acids from which it is composed.  In this talk, I will introduce various models which have been proposed for studying this multidimensional problem.  I will then present the results of applying genetic algorithms, ant colony optimization and artificial immune systems to search for the lowest energy folding conformations of various model proteins.  Finally, I will describe recent work involving the coupling of principal component analysis and disconnectivity tree diagrams to enable the visualisation of hyperdimensional energy landscapes.

Variable Neighborhood Search (followed by our General Meeting) (presentation available, 3.33MB)
Speaker: Nenad Mladenovic, Brunel University
Date/Time: Thursday 8th March 2007 18:00-20:00
Venue: Room A422 ( College Building), City University, Northampton Square , London EC1V OHB (Use the St John Street entrance) http://www.city.ac.uk/maps/northamptonsquare/index.html

• Abstract: Variable Neighborhood Search (VNS) is a metaheuristic for solving optimization problems. It is based on systematic changes of the neighborhood structure within a search that may be performed in a deterministic fashion (variable neighborhood descent, VND) or randomly (reduced VNS). Basic VNS combines random selection of a point in a shaking or perturbation step followed by a deterministic local search from that point. There are several extensions and hybrids of the basic VNS scheme suggested in the literature: if VND is used instead of local search, we have general VNS; the variable neighborhood decomposition search (VNDS) method extends the basic VNS into a two-level VNS scheme based upon decomposition of the problem; the skewed VNS allows moves to a slightly worse but far solutions, etc. New applications of VNS will also be presented.

Title: An Introduction to Stochastic Diffusion Processes (presentation available, 331KB)
Speaker: Dr Mark Bishop Affiliation: Department of Computing, Goldsmiths College
Date/Time: Wednesday 10th January 2007 - 2pm
Venue: Room 207, School of Computing & Informatics, Clifton Campus, Nottingham Trent University, Nottingham, NG11 8NS (http://www.ntu.ac.uk/coin/)

• Abstract:
  The Stochastic Diffusion Search is an efficient probabilitistic multi-agent global search and optimisation technique that has been applied to such diverse problems as site selection for wireless networks, mobile robot self-localisation, object recognition and text search. Additionally, a hybrid SDS/neural network technique has been used to track eyes in video sequences. Previous analysis of SDS has investigated its convergence and resource allocation using Markov Chains and Ehrenfest Urn models under a variety of noise conditions. This presentation will discuss generic Stochastic Diffusion Processes in human and ant systems, outline a simple 'best-fit-search'/'discrete-optimisation' stochastic diffusion algorithm and its convergence criteria.

Heuristic Optimisation for Portfolios with Transaction Costs (presentation available, 578KB)
Speaker: Dietmar Maringer, University of Essex
Date: 1st December 2005 from 18:00 - 20:00
Venue: Room 2005, Cass Business School, City University, 105 Bunhill Row, London EC1Y 8YZ
Information: http://www.cass.city.ac.uk/about/location/index.html

• Abstract: In portfolio theory, markets are mostly assumed to be perfect and frictionless. This allows focusing on the basic underlying mechanics and keeps the optimisation models simple and approachable. In real life, however, investors face all sorts of additional constraints, including integer constraints and transaction costs. Including these constraints would bring the portfolio management models closer to real life problems -- yet exceeds the limits of many a traditional optimisation approach. To solve this dilemma between solvability and getting as close to real life problems as possible, an alternative type of optimisation techniques is needed, e.g. heuristic optimisation techniques.
• A crucial feature of heuristic optimisation methods is that they do not (or not entirely) rely on deterministic procedures, but also incorporate stochastic elements. Typically, a heuristic optimisation technique starts off with a random solution and then iteratively suggest random changes which are accepted or rejected according to some rule, which might be deterministic or, again, stochastic. The main advantage of these methods is that they are very flexible and therefore can be applied to all sorts of problems.
• In this talk, I will introduce two of the simplest, but nonetheless highly effective heuristic optimisation techniques, namely Simulated Annealing and Threshold Accepting. These methods will then be compared to a more complex approach, Genetic Algorithms, and then be applied to the portfolio optimisation problem under transaction costs and integer constraints.
• Our results imply that the heuristic optimisation is well apt to solve demanding problems in financial management -- and that the type transaction costs has a substantial effect on the portfolio structure.

A Joint Talk between The OR Society Local Search Study Group (in association with the School of Mathematics, University of Cardiff) and SWORDS.
ANT COLONY OPTIMISATION (presentation available, 810KB)
Speaker: Dr Jonathan Thompson, Department of Mathematics, University of Cardiff
Date: Tuesday 26th October 2004

• Ant colony optimisation (ACO) is an evolutionary search procedure based on the way that ant colonies co-operate in locating shortest routes to food sources. Early implementations focussed on the travelling salesman and other routing problems but it is now being applied to an increasingly diverse range of combinatorial optimisation problems. This talk will give an overview of ACO and demonstrate its effectiveness on both non-routing problems, specifically timetabling and scheduling problems, and dynamic problems (the dynamic vehicle routing problem). A number of enhancements and modifications to the original algorithm are introduced and shown to produce competitive results.

The use of Meta-Heuristics in Data Mining (presentation available)
Speaker: Dr George D Smith, School of Computer Science, University of East Anglia
Date: 5th March 2004

• Meta-Heuristics form a family of search algorithms used in tackling large, complex combinatorial optimisation problems. The family includes simulated annealing, tabu search, guided local search, GRASP, evolutionary algorithms and ant colony optimisation. At UEA, we have a team of researchers developing and applying meta-heuristics to applications in data mining. Two case studies will be presented: the first is an application of simulated annealing to induce covering rules in a classification problem, the second is the application of genetic programming to construct (evolve) new and highly predictive features from the given predicting attribute set.

No Optimisation without Representation: Principled Design for Local Search (presentation available)
Speaker: Dr Andrew Tuson, Department of Computing, City University and CISA, Edinburgh University
Date: 5th December 2003 3.45 (for 4pm start)

• Though local search optimisers are clearly effective, their design is often rather ad hoc in practice. More specifically, though it is generally agreed that incorporating domain knowledge is needed to produce effective optimisers, how to achieve this is still an open question. This talk outlines a semi-formal knowledge based approach for acquiring and representing domain knowledge to local search optimisers.

Joint with LASEORS
An Introduction to Artificial Immune Systems (presentation available)
Dr Jonathon Timmis, (see www.cs.kent.ac.uk/people/staff/jt6/)
22nd October 2003

• The immune system is highly distributed, highly adaptive, self-organising in nature, maintains a memory of past encounters and has the ability to continually learn about new encounters. From a computational point of view, the immune system has much to offer by way of inspiration to computer scientists and engineers alike. As computational problems become more complex, increasingly, people are seeking out novel approaches to these problems, often turning to nature for inspiration. A great deal of attention is now being paid to the vertebrae immune system as a potential source of inspiration, where it is thought that different insights and alternative solutions can be gleaned, over and above other biologically inspired methods. This talk will provide an overview of this exciting emerging area of research, namely Artifical Immune Systems and highlight potential uses of this new paradigm in a variety of application areas ranging from data mining, fault tolerance and optimisation.

An investigation into a new class of routing with backhauling: Some results using ant systems.
Said Salhi, Reader in Heuristic Optimisation, Birmingham University
Thursday 30 January 2003

• Venue: Room 3P5 in 'P' Block, Faculty of Computing, Engineering and
  Mathematical Sciences, Frenchay campus, Coldharbour Lane. University of the West of England, Bristol, BS16 1QY.

Multilevel local search for combinatorial optimisation problems
Chris Walshaw, University of Greenwich
Wednesday 20 Nov 2002

• We consider the multilevel paradigm and its potential to aid the solution of combinatorial optimisation problems. The multilevel paradigm involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found (sometimes for the original problem, sometimes at the coarsest level) and then iteratively refined at each level, coarsest to finest. As a general solution strategy the multilevel procedure has been in use for many years and has been applied to many problem areas (most notably via multigrid solvers). However, withthe exception of graph partitioning, multilevel techniques have not been widely applied to combinatorial problems.
• In this talk we address the use of multilevel ideas for such problems where the refinement is carried out by local search algorithms 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 meta-heuristic. The results provide compelling evidence that, although the multilevel framework cannot be considered as a panacea for combinatorial problems, it can provide a valuable addition to the combinatorial optimisation toolkit. We also give a probable explanation for the underlying process and extract some generic guidelines for its future use.
• The AGM will follow the talk.

A Practical Algorithm for the Examination Timetabling Problem
Michael Carter, University of Toronto
Monday 15 July 2002

• University examination timetabling is a difficult combinatorial problem. Carter and Laporte have developed a heuristic algorithm based on a limited backtracking scheme. The method has been implemented at the University of Toronto (Engineering), Carleton University (Ottawa), Ecole des Hautes Etudes Commerciales (Montreal), the London School of Economics, the University of Western Ontario (London, Ontario), the University of Limerick (Ireland) and the University of Otego (New Zealand). Despite the fact that all of these schools have quite different requirements, they are all using the same program with a user interface that allows the scheduler to tailor the procedure to their specific issues.

Scheduling in cricket and lessons learned
Mike Wright, Lancaster University
Wednesday 22 May 2002 at 2pm at Lancaster University Management School

• This paper will give a brief outline of the author's computer systems used to timetable county cricket fixtures and allocate umpires in England. The methods used are home-made variants of a well-known metaheuristic technique. The talk will touch upon problem formulation, objective functions, neighbourhood structures and the search process. Difficulties and opportunities will be highlighted which should be relevant to the solution of a variety of other types of combinatorial problem.

UK Local Search Group and EU/ME, the EUropean chapter on MEtaheuristics (EURO Working Group)
First Joint Seminar on Metaheuristics
Wednesday, November 28, 2001 City University, London, UK

• The timetable is as follows.

	10.30 - 11.00	Coffee
	11.00 - 11.50	Some applications of variable neighbourhood search Khalil Hindi (Brunel University, UK)
	12.00 - 12.40	The impact of the data structures in the algorithm implementation for the travelling salesman problem Dorabela Gamboa (Universidade Portucalense, Porto, Portugal)
	12.40 - 13.50	Lunch
	13.50 - 14.50	What more can metaheuristics do than finding good solutions? Pierre Hansen (University of Montreal, Canada)
	14.50 - 15.30	Modified genetic algorithm Sigitas Buda (Institute of Mathematics and Informatics, Vilnius, Lithuania)
	15.30 - 16.00	Tea or coffee
	16.00 - 16.40	A new ant colony algorithm using direct inter-individual communication aimed at continuous optimization Johann Dreo (Universite de Paris XII, France)
	16.40 - 17.15	Discussion

• There is no registration fee. However, participants will be expected to pay on arrival a small charge of about £10 to cover the cost of catering (lunch, coffee, etc.).
• The seminar is held at City University, Northampton Square, London. Directions on finding City University are available on the web site www.city.ac.uk/aboutcity/campusmap.htm

Hunting big game in fitness landscapes
Colin Reeves, Coventry University
Tuesday 16th January 2001, 2.30pm University of Nottingham

• Neighbourhood search (NS) is a popular method for finding good solutions to combinatorial optimisation problems (COPs). Individual neighbourhoods induce different fitness landscapes, replete with ‘hills’, ‘valleys’, ‘ridges’ etc., but simple NS only climbs one hill - a local optimum. While at least one hill will be globally optimal, experience shows that most of the time we don’t find it, and the fitness of the one we do climb may be quite poor. 
• It would be helpful if we could have some idea of how many local optima there really are in a particular fitness landscape. In this talk I shall demonstrate how this problem can be formulated as an analogy of a well-known problem in ecology - estimating the numbers of an animal species in a well-defined area. Some theoretical results will be explained, and experimental evidence used to assess the plausibility of this approach