Optimization: principles and algorithms, by Michel Bierlaire
Heuristics

List of Octave codes related to Chapter 27 of [1]. More...

## Files

file  bestInsert.m
Identifies the best insertion in a tour for the TSP.

file  getTourList.m
Transforms a tour stored as a sequence of cities into a list of successors.

file  getTourSequence.m
Transform tour stored as list of successor, into a sequence of cities.

file  insertCity.m
Inserts a city in a tour for the TSP.

file  knapsackGreedy.m
Solves the knapsack problem using the greedy heuristic described in section 27.1.1 of [1].

file  ksLocalSearchDeterministic.m
Algorithm 27.3: local search for the knapsack problem.

file  ksLocalSearchRandom.m
Implementation of a variant of the local search algorithm with random neighbors for the knapsack problen.

file  ksRandomNeighbor.m
Algorithm 27.5: neighborhood for the knapsack problem.

file  ksSimulatedAnnealing.m
Algorithm 27.7: simulated annealing for the knapsack problem.

file  ksVns.m
Algorithm 27.5: VNS for the knapsack problem.

file  randomFromAtoB.m
Compute a random integer between A and B.

file  run2702greedy.m
Runs example 27.2 of [1], solving the problem using the greedy heuristic.

file  run2702localSearchDeterministic.m
Runs example 27.2 of [1], solving the problem using the local search method (Table 27.6)

file  run2702localSearchRandom.m
Runs example 27.2 of [1], solving the problem using the local search method with random neighbors.

file  run2702simAnn.m
Runs example 27.2 of [1], solving the problem using the simulated annealing method (see Section 27.4.1 of [1]).

file  run2702vns.m
Runs example 27.2 of [1], solving the problem using the VNS method.

file  run2703insertion.m
Runs example 27.3 of [1], solving the problem using the greedy heuristic (Algorithm 27.2, Table 27.2, Figure 27.4)

file  run2703localSearch.m
Runs Algorithm 27.3 on example 27.3 of [1], solving the TSP with local search (Figure 27.11, Table 27.7, Figure 27.12)

file  run2703nearestNeighrbor.m
Runs example 27.3 of [1], solving the problem using the greedy heuristic.

file  run2703simAnn.m
Runs example 27.3 of [1], solving the problem using simmulated annealing (Section 27.4.2 of [1] ).

file  run2703vns.m
Runs example 27.3 of [1], solving the problem using VNS (Section 27.3.2 of [1] ).

file  subtourLength.m
Calculate the length of a subtour of the TSP.

file  tspInsertion.m
Algorithm 27.2: insertion heuristic for TSP.

file  tspInsertionLocalSearch.m
Local search method for the TSP based on the insertion heuristic, as described in Section 27.3.2 of [1].

file  tspLocalSearch.m
Algorithm 27.3: local search for the TSP.

file  tspNearestNeighbor.m
Algorithm 27.1: nearest neighbor heuristic for TSP.

file  tspSimulatedAnnealing.m
Algorithm 27.7: simulated annealing for the TSP.

file  tspTourLength.m
Calculate the length of a tour of the TSP.

file  tspVns.m
Implements the VNS to solve the TSP, as described in Section 27.3.2 of [1].

file  twoOpt.m
Perform a 2-opt operation of a list of cities.

file  twoOptNeighborhood.m
Generate the 2-opt neightborhood for the TSP.

file  twoOptRandomNeighbor.m
Generate one random 2-opt neighbor for the TSP.

## Detailed Description

List of Octave codes related to Chapter 27 of [1].