Lagrangian heuristics for quadratic optimisation problems
(LANCS clusters: Optimisation, Heuristic Understanding)
with Adam Letchford
This research topic is concerned with optimisation problems that have quadratic constraints and/or objective functions. A vast array of problems, from a variety of disciplines, are of this kind.
A standard technique in optimisation is Lagrangian relaxation, in which constraints are dropped from the problem, but penalised in the objective function. This technique can be used to compute bounds for a variety of optimisation problems, including quadratic problems. Interestingly, it is sometimes possible to modify the solution to a relaxed problem to make it feasible for the original problem. In this way, one obtains a “Lagrangian heuristic”. The goal of this research project is to devise Lagrangian heuristics for certain quadratic optimisation problems, implement them in computer software, and perform computational experiments on a range of test instances.
Applicants for this research project need to have good qualifications in mathematics or a related discipline, and have experience with computer programming. Experience with LaTeX and/or MatLab would also be desirable, but are not essential as training can be given.
Return to the Optimisation Research Centre page.
