MERCER ETM 645 - Local Improvement Algorithms (10 pages)

Previewing pages 1, 2, 3 of 10 page document View the full content.
View Full Document

Local Improvement Algorithms



Previewing pages 1, 2, 3 of actual document.

View the full content.
View Full Document
View Full Document

Local Improvement Algorithms

37 views


Pages:
10
School:
Mercer University
Course:
Etm 645 - Operations Research I

Unformatted text preview:

Local Improvement Algorithms Find a Solution x S Is this solution better than all its neighbors No Yes Stop Current x Local Optimal Find a better neighbor x Note These slides adapted from Y Fathi North Carolina State University lecture notes IE589D Local Improvement Algorithms Issue 1 What to use as the initial solution x Options a Heuristic b Randomly generated Which option is better Local Improvement Algorithms Issue 2 What defines a neighbor or neighborhood Definition Given a discrete optimization problem a neighborhood structure is a mapping which defines for each x S a set N x S of solutions that are close in some sense N x is said to be the neighborhood of x What does close mean Local Improvement Algorithms Examples of Neighborhoods Adjacent basic feasible solution in the simplex method the commonality between neighbors is that all basic variables are the same except for one A neighbor to a strictly binary problem is one in which all the values of the variable are the same except one 1 0 0 1 1 0 1 is a neighbor of 1 0 0 1 1 1 1 also a neighbor of 1 1 0 1 1 0 1 Local Improvement Algorithms Examples of Neighborhoods cont Pair wise interchange for a scheduling problem Schedule 1 3 4 2 5 7 6 is a neighbor of 3 1 4 2 5 7 6 1 3 2 4 5 7 6 1 3 4 2 5 6 7 Three way interchange for a scheduling problem Schedule 1 3 4 2 5 7 6 is a neighbor of 3 4 1 2 5 7 6 1 3 2 5 4 7 6 1 3 4 2 5 6 7 Is this last one strictly a neighbor Local Improvement Algorithms Examples of Neighborhoods cont 2 opt For TSP 1 1 2 6 3 5 4 1 2 3 4 5 6 1 6 2 5 3 4 1 2 5 4 3 6 1 Local Improvement Algorithms Issue 3 Search Strategy Examples steepest descent optimal adjacency first improvement better adjacency Find local optimal for one neighborhood and then try next e g pair wise interchange followed by threeway interchange How do you evaluate which technique works best Local Improvement Algorithms Issue 4 Evaluation Function How do you know the adjacent or neighboring solution is better Speed need efficient



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Local Improvement Algorithms and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Local Improvement Algorithms and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?