PhD project: Theory and Applications of
Semi-Lagrangian Relaxation
Many important problems in Operational Research, such as selecting optimal locations for warehouses or factories, can be formulated as integer programs. When these problems involve many variables or constraints, finding an exact solution can be difficult and time-consuming. A popular method called Lagrangian Relaxation (LR) helps by simplifying these problems to provide practical, approximate solutions more quickly. Once an approximate solution is found, it can be fine-tuned using simple techniques, known as heuristics, to make it fit the original requirements. This approach helps estimate both lower and upper limits for the optimal solution, providing useful guidance. LR has been applied successfully to a wide range of problems and has a well-developed theory.
A newer approach, Semi-Lagrangian Relaxation (SLR), builds on LR to provide even stronger estimates for these limits and can sometimes eliminate the gap between them, while still reducing the problem’s complexity and, therefore, the computer processing compared with the original problem. Although promising, SLR is still relatively under-researched. This project aims to deepen understanding of SLR by testing it with new applications and benchmark datasets and evaluating its effectiveness. It will also identify ways to enhance the method by exploring how problem-reduction techniques and heuristics can be used in conjunction.
