Optimization methods

Optimization methods

1. Exact methods (classical search techniques)

   • Simplex method
   • Plane cuts
   • Branch and Bound

2. Approximate Algorithms

   • Heuristics
     • Local search
       • Start with an initial solution
         • try to replace with better solutions in the neighborhood until reach the local optimal
         • Neighborhood N(s)
           • Hill climbing algorithms
             • Max objective function
           • Set of solutions that can be reached by a simple move
             • Move = simple operation
               • K-opt moves for TSP(travelling sale process)
               • Production scheduling
                 • Swap moves(jobs)
                 • Insert move
     • Greedy construction heuristic
       • Initially adding an empty solution with appropriate solution components
       • For ex: Shortest processing time (SPT), Nearest neighbor heuristic
   • Meta-heuristic (Modern heuristic methods)
     • Population based approaches
       • Genetic algorithms
     • Single solution approachs
       • Tabu search
       • Simulated Annealing