Optimization: principles and algorithms, by Michel Bierlaire

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 2opt operation of a list of cities.  
file  twoOptNeighborhood.m 
Generate the 2opt neightborhood for the TSP.  
file  twoOptRandomNeighbor.m 
Generate one random 2opt neighbor for the TSP.  
List of Octave codes related to Chapter 27 of [1].