Skip to content

Local search

Part 4 · Heuristic algorithms · Chapter 31 · Lecture notes, volume 4 (PDF) · Slides (1/2) · Slides (2/2) · Exercises: Local search · App: TSP: nearest neighbour and 2-opt

Prerequisites

Objectives

At the end of this chapter you will be able to:

  • define the neighbourhoods of the KP, the BPP, the TSP and \(P\,||\,C_{\max}\);

  • execute a local search with the first improvement and the best improvement rules;

  • evaluate a move incrementally, in \(O(1)\) for the 2-opt move;

  • escape a plateau with an auxiliary objective, and handle infeasible solutions with a penalty;

  • combine neighbourhoods (variable neighbourhood descent) and restarts (multi-start).

31.1 Local search

Definition 31.1: Local search

Given a neighbourhood \(N\), a local search (denoted by \(LS\)) is an improvement heuristic. It starts from a feasible solution and, at every iteration, looks in the neighbourhood of the current solution for a better solution. If it finds one, it moves to it and repeats; if no neighbour is better, the current solution is a local optimum with respect to \(N\), and the search stops.

  • The neighbourhood \(N(S)\) of a feasible solution \(S\), the move from \(S\) to a neighbour and the local optimum with respect to \(N\) are defined in the chapter «Heuristic algorithms: definitions».

A local search improves a feasible solution by moving from a solution to a better neighbour, and it stops in a local optimum with respect to \(N\).

  • Overview

    Local search

    Open

  • 31.2 The problems, the assumptions and the starting solutions

    Open

  • Local search: the scheme · Neighbourhoods for the four problems

    KP: flip and swap · BPP: move and swap · TSP: 2-opt and Or-opt · P\,||\,Cmax: move and swap · Summary

    Open

  • 31.5 First improvement and best improvement

    Best improvement · Comparison

    Open

  • 31.6 Evaluating a move incrementally

    Open

  • 31.7 TSP: 2-opt and Or-opt

    The Or-opt local search · First and best improvement on a medium instance · 3-opt and Lin–Kernighan

    Open

  • 31.8 \(P\,||\,C_{\max}\): move and swap

    The swap local search

    Open

  • 31.9 Flat landscapes and auxiliary objectives

    The auxiliary objective · The move local search for the BPP · The swap local search for the BPP · Properties of the auxiliary objective · Examples

    Open

  • 31.10 KP: feasibility and penalties

    Penalizing the excess weight

    Open

  • 31.11 Variable neighbourhood descent

    Open

  • 31.12 Multi-start local search

    What local search gives, and what it does not

    Open

  • Typical mistakes · In summary

    In summary

    Open

Next: 31.2 The problems, the assumptions and the starting solutions

Exercises on this chapter: Local search

In the interactive lab: TSP: nearest neighbour and 2-opt.