Theory and applications of semi-Lagrangian relaxation.

Many important real-world problems, like scheduling routes or selecting optimal locations for warehouses, have lots of constraints and can become very complicated to solve, especially when they are large-scale. Solving them exactly can take a lot of time or require more computer memory than is available. Lagrangian Relaxation (LR) is a classic approach that helps make these problems easier to tackle. The idea is to focus on the "easier" constraints first and gradually adjust for the more "challenging" ones afterwards. This method has been used successfully in a wide range of fields and has a strong theoretical foundation.
A newer approach called semi-Lagrangian Relaxation (SLR) builds on the LR method to provide even more accurate estimates for solutions. In some cases, it can even close the gap between bounds. Although promising, SLR is still relatively underexplored. This project aims to deepen our understanding of SLR by testing it on new problems, evaluating how effective it is and improving SLR in the existing literature.

In partnership with Northwestern University.