When

Start: 04/01/2010 - 4:15pm

End : 04/01/2010 - 5:15pm

End : 04/01/2010 - 5:15pm

Category

Statistics/OR/Math Finance Seminar

Speaker

Agustin Bompadre, Caltech

Abstract

Local search heuristics are among the most popular

approaches to solve hard optimization problems. Among them, Very Large

Scale Neighborhood Search techniques present a good balance between

the quality of local optima and the time to search a neighborhood. In

this talk, we present a language to generate exponentially large

neighborhoods for sequencing problems using grammars. We show

efficient generic dynamic programming solvers that determine the

optimal neighbor in a neighborhood generated by a grammar for

sequencing problems such as the Traveling Salesman Problem or the

Linear Ordering Problem. This framework unifies a variety of previous

results on exponentially large neighborhood for the Traveling Salesman

Problem and generalizes them to other sequencing problems. This is

joint work with Jim Orlin (MIT).

Where

Harvey Mudd College
Seminar Room
3rd Floor, Sprague
Refreshments at 4