Optimization: principles and algorithms, by Michel Bierlaire
Algorithms

List of algorithms presented in the book [1]. More...

## Files

file  machineEpsilon.m
Algorithm 7.1: calculation of the machine epsilon.

file  newtonNVariables.m
Algorithm 7.3: Newton's method, n variables.

file  newtonOneVariable.m
Algorithm 7.2: Newton's method, one variable.

file  newtonFinDiffNVariables.m
Algorithm 8.3: Newton's method with finite differences, n variables.

file  newtonFinDiffOneVariable.m
Algorithm 8.1: Newton's method with finite differences, one variable.

file  secantNVariables.m
Algorithm 8.4: Newton's secant method, n variables.

file  secantOneVariable.m
Algorithm 8.2: Newton's secant method, one variable.

Algorithm 9.2: Conjugate gradient algorithm for quadratic problems.

Algorithm 9.1: Direct resolution of quadratic problems.

file  newtonLocal.m
Algorithm 10.1: Local Newton for optimization.

Algorithm 10.2: Local Newton for optimization using the quadratic model.

file  goldenSection.m
Exact line search using golden section.

file  initLineSearch.m
Algorithm 11.2: Initialization of the exact line search.

file  lineSearch.m
Algorithm 11.5: Line search algorithm.

file  modifiedCholesky.m
Algorithm 11:7: Modified Cholesky factorization.

file  newtonLineSearch.m
Algorithm 11:8 Newton's method with line search .

Algorithm 11.3: Exact line search using quadratic interpolation.

file  steepestDescent.m
Algorithm 11.6: Steepest descent algorithm.

file  steepestDescentCauchy.m
Steepest descent algorithm, calculating the Cauchy point at each iteration.

file  dogleg.m
Algorithm 12.2: Dogleg method to find an approximation of the trust region subproblem.

file  intersectionTrustRegion.m
Algorithm 12.1: Calculation of the intersection with the trust region.

file  newtonTrustRegion.m
Algorithm 12.4: Newton's method with trust region.

Algorithm 12.3: Truncated conjugate gradients method to find an approximation of the trust region subproblem.

file  bfgs.m
Algorithm 13.1: BFGS method with line search.

file  symmetricRankOne.m
Algorithm 13.2: SR1 method with trust region region.

file  gaussNewton.m
Algorithm 14.1: Gauss-Newton method.

file  kalmanFilter.m
Algorithms 14.2 and 14.3: Kalman filter update.

Algorithm 15.1: Nelder-Mead algorithm.

file  torczon.m
Algorithm 15.2: Torczon algorithm.

file  pivoting.m
Algorithm 16.3: Pivoting of the simplex tableau.

file  simplex.m
Algorithm 16.2: Simplex methos.

file  simplexTableau.m
Algorithm 16.4: Phase II simplex algorithm with tableau.

file  twoPhasesSimplex.m
Algorithm 16.5: Two phases simplex algorithm with tableau to solve a linear optimization problem in standard from.

file  vertexEnumeration.m
Algorithm 16.1: Vertex enumeration Implementation of algorithm 16.1 of [1].

file  constrainedNewton.m
Algorithm 17.2: preconditioned projected gradient, or constrained Newton.

file  dikin.m
Algorithm 17.3: Dikin's method.

Algorithm 17.1: projected gradient Implementation of algorithm 17.1 of [1].

file  longSteps.m
Algorithm 18.4: long steps interior point algorithm.

file  predictorCorrector.m
Algorithm 18.3: Predictor-corrector interior point algorithm.

file  restrictedSteps.m
Algorithm 18.2: Interior point algorithm with restricted steps.

file  augmentedLagrangian.m
Algorithm 19.1: augmented Lagrangian algorithm.

file  globalSqp.m
Algorithm 20.2: global SQP algorithm.

file  localSqp.m
Algorithm 20.1: local SQP algorithm.

file  circulationDecomposition.m
Algorithm 21.2: circulation decomposition.

file  flowDecomposition.m
Algorithm 21.3: flow decomposition.

file  jarnikPrim.m
Algorithm 21.4: Jarnik-Prim.

file  nodeDivergence.m
Compute the divergence of a flow vector (Definition 21.13 of [1])

file  prepareNetwork.m
Prepares the network for efficient access to the data.

file  simpleCycle.m
Algorithm 21.1: Generation of a simple cycle flow from a circulation.

file  incidenceMatrix.m
Provide the incidence matrix of the network for the teanshipment problem.

file  transhipment.m
Solve a transhipment problem with bound constraints.

file  transhipmentTransform.m
Transform a transhipment problem into a problem in standard form.

file  dijkstra.m
Algorithm 23.2: Dijkstra.

file  enumeratePaths.m
Enumerate all simple paths between two nodes.

file  shortestPath.m
Algorithm 23.1: shortest paths.

file  fordFulkerson.m
Algorithm 24.2: Ford-Fulkerson.

file  unsaturatedPath.m
Algorithm 24.1: unsaturated path.

file  knapsackExact.m
Solves the knapsack problem using integer optimization.

file  tspExact.m
Write the Traveling Salesman Problem (TSP) as an integer optimization problem in standard form.

file  gomory.m
Algorithm 26.3: Gomory cuts for linear optimization.

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  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 algorithms presented in the book [1].

Copyright 2015-2016 Michel Bierlaire