Enhancing decomposition techniques using large-neighbourhood search to solve large-scale optimisation problems

优化是当今社会的基本组成部分。许多服务的规划、管理和运营都依赖于优化，以实现高效、经济的服务交付。随着服务需求的不断增长，对高效运营的需求变得越来越重要。运输是研究和开发优化技术的主要受益者。其好处是通过提高铁路运营效率降低了成本，通过更好地分配飞机增加了航空公司提供的服务，通过更好地整合机组人员和飞机改善了航空公司和铁路运营商的准时表现。然而，保持降低成本和提供高效运营的能力受到我们解决日益复杂的优化问题的能力的限制。运输和其他行业的进一步发展将通过研究和开发的最优化问题的解决方案的技术交付。本研究的目的是改善目前的最优化技术，以扩大可解决的问题超出目前的限制域。研究将借鉴当前的研究两个密切相关的领域的数学优化-混合整数规划（MIP）和分解技术。大邻域搜索的不精确MIP求解方法对于寻找优化问题的好解是有价值的。而Benders分解的精确分解技术大大简化了问题的形式，提供了一种有效的求解方法。大邻域搜索的最新发展将被用来显着增强Benders分解的解决方案算法。本计画将利用整合这两种方法的协同效应，以扩展目前解决大规模最佳化问题的能力。本计画将研究如何加强Benders的分解，并找出有效运用平行计算基础架构的策略。该奖学金将实现以下目标：1）生产一个软件包，用于将Benders的分解应用于一般的大规模优化问题。一个增强的求解器将开发通过集成的本德斯分解与大邻域搜索。由此产生的软件将能够解决大规模的优化问题，从工业和制药业。2）开发新的并行化计划的本德分解使用大邻域搜索算法的框架。并行化方案将利用现代计算架构来显著减少解决方案的运行时间。此外，算法的开发将为未来的并行计算研究奠定基础。开发的软件将提供工具，将Benders的分解应用于学术界和工业界出现的优化问题。这将通过运输、生物信息学和气候科学领域的跨学科合作项目得到证明。特别是，将研究中断后航班时间表的恢复，将应用优化技术分析病毒序列，并采用新的算法来识别收敛到急流中的强风。为了促进知识向工业界和更广泛的学术界的转移，现有的软件和解决方案算法将免费提供给学术界使用。

Optimisation is a fundamental part of today's society. The planning, management and operation of many services rely on optimisation for efficient and cost effective delivery of services. With an ever growing demand for services, the need for efficient operations is becoming more critical.Transportation is a major beneficiary of research and development of optimisation techniques. The benefits are observed in a reduction of costs through the more efficient running of railways, an increase in the provided services by airlines through better allocation of aircraft and an improvement in the on-time performance of airlines and railway operators through the better integration of crew and aircraft. However, the ability to maintain reduced costs and deliver efficient operations is limited by our capacity to solve optimisation problems of ever growing complexity. Further advances in transportation and other industries will be delivered through the research and development of solution techniques for optimisation problems.The aim of this research is to improve current optimisation techniques to extend the domain of solvable problems beyond current limits. The research will draw upon current research of two closely related fields of mathematical optimisation---mixed integer programming (MIP) and decomposition techniques. The inexact MIP solution approach of large-neighbourhood search is valuable for finding good solutions to optimisation problems. While the exact decomposition technique of Benders' decomposition greatly simplifies problem formulations and provides an effective solution approach. The recent developments in large-neighbourhood search will be employed to significantly enhance the solution algorithm of Benders' decomposition. This project will exploit synergies from the integration these two methods to extend current capabilities for solving large-scale optimisation problems.This project will investigate the enhancement of Benders' decomposition and identify strategies to effectively employ parallel computing infrastructure. The fellowship will achieve the following:1) The production of a software package for applying Benders' decomposition to general large-scale optimisation problems. An enhanced solver will be developed through the integration of Benders' decomposition with large-neighbourhood search. The resulting software will be capable of solving large-scale optimisation problems from industry and academia.2) The development of novel parallelisation schemes for Benders' decomposition using the framework of large-neighbourhood search heuristics. The parallelisation schemes will exploit modern computing architecture to significantly reduce solution run times. Further, the algorithmic development will lay the ground work for future parallel computing research.The developed software will provide tools to apply Benders' decomposition to optimisation problems arising in academia and industry. This will be demonstrated through interdisciplinary collaborative projects in transportation, bioinformatics and climate science. In particular, the recovery of flight schedules after disruption will be investigated, optimisation techniques will be applied to analyse viral sequences and novel algorithms will be employed to identify of strong winds that converge into the jet streams. To facilitate the transfer of knowledge to industry and the wider academic community the available software and solution algorithms will be made freely available for academic use.