# MERCER ETM 645 - Local Improvement Algorithms (10 pages)

Previewing pages 1, 2, 3 of 10 page document
View Full Document

## Local Improvement Algorithms

Previewing pages 1, 2, 3 of actual document.

View Full Document
View Full Document

## Local Improvement Algorithms

50 views

Pages:
10
School:
Mercer University
Course:
Etm 645 - Operations Research I
##### Operations Research I Documents
• 3 pages

• 2 pages

• 14 pages

• 10 pages

• 12 pages

• 12 pages

• 6 pages

• 15 pages

• 22 pages

• 12 pages

• 10 pages

• 2 pages

• 3 pages

• 11 pages

• 6 pages

• 3 pages

• 2 pages

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

Unlocking...