Optimization Methods - Recitation 9

Recitation 9 1 Heuristic Metho ds Integer programming problems in general are hard problems, which cannot be easily solved to optimality. Heuristic methods allow us to obtain good feasible solutions with a reasonable amount of computational time. Local search heuristics are widely used. General framework for local search is as follows. 1. Start with a feasible solution. 2. Identify the neighbourhood. 3. Move to a ‘better’ feasible solution within the neighbourhood. Generally, the local search heuristics will result in a local optimum, which is sometimes the global optimum. The movement in step 3 is method dependent and maybe problem dependent. 1.1 Simulated Annealing � Neighbours are selected randomly with probability pn , where n∈N pn = 1. The decision to move depends on the objective cost and the annealing probability: � c(y)−c(x) py (x)e− T c(y) > c(x) pxy = py (x) The temperature schedule T is selected based on some rules, such as T (t) = a < 1. 1.2 C log t or T (t) = Cat , where Other methods There are many local search heuristics out there (some are beter than other for some specific problems). Among them are tabu search, genetic algorithm (a little bit different approach). Ant colony optimization is another one. 1. Tabu search elements: tabu list (list of moves or characters of moves that have been used), intensification (finer neighbourhood), and diversification (coarser neighborhood). 2. Genetic algorithm elements: chromosome (representation of solution), selection, crossover, and mutation. 3. Ant colony optimization: pheromone trail and heuristic desirability. 1 2 Dynamic Programming 2.1 Dynamic Programming Elements 1. State xk , the most important element 2. Control uk ∈ U (xk ) 3. Randomness wk 4. Dynamic xk+1 = fk (xk , uk , wk ) � � � −1 g (x , u , w ) 5. Additive cost EW gN (xN ) + N k k k k i=1 2.2 Bellman’s Principle of Optimality Here we want to find the total minimum cost over a period of N stages in the future. The cost of the final stage is gN (xN ). At a stage k with the state xk , we need to decide on how much control uk we need so that the total cost from that stage to the final one is optimal. The recursion formula is then: Jk (xk ) = min uk ∈U (xk ) {Ewk (gk (xk , uk , wk ) + Jk+1 (fk (xk , uk , wk )))} The total minmum cost is J0 (x0 ), which can be calculated backwards recursively. In general, a recursive formula needs two elements: 1. Initial condition f0 = f 2. Recursive formula fk+1 = gk (fk ) 2.3 Examples Knapsack problem Two recursive formulations with different state definitions: 1. F (w) is the optimal cost with w as the weight limit, then we need to find F (W ), where: (a) F (w) = 0 if w < mini wi (b) F (w) = maxi=1,m {F (w − wi ) + pi } if w ≥ mini wi 2. Fi (w) is the optimal cost with w as the weight limit while using only the first i items, then we need to find Fm (W ), where: (a) F0 (w) = 0 if w ≥ 0, F0 (w) = −∞ if w < 0 (b) Fi+1 (w) = max {Fi (w), Fi (w − wi+1 ) + pi+1 } if w > 0 2