Sequence Grammars for Very Large Scale Neighborhood Search

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

Statistics/OR/Math Finance Seminar

Agustin Bompadre, Caltech


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).

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