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

使用大邻域搜索增强分解技术来解决大规模优化问题

• 批准号: EP/P003060/2
• 负责人: Stephen Maher
• 金额: $ 11.21万
• 依托单位: UNIVERSITY OF EXETER
• 依托单位国家: 英国
• 项目类别: Fellowship
• 财政年份: 2019
• 资助国家: 英国
• 起止时间: 2019 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FP003060%2F2
• 关键词: Enhancing; decomposition; techniques; using; large

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.

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

项目成果

A data-driven, variable-speed model for the train timetable rescheduling problem

• DOI: 10.1016/j.cor.2022.105719
• 发表时间: 2022-02
• 期刊: Comput. Oper. Res.
• 作者: E. Reynolds;Stephen J. Maher

Avoiding redundant columns by adding classical Benders cuts to column generation subproblems

通过向列生成子问题添加经典的 Benders 切割来避免冗余列

• 发表时间: 2019
• 作者: Luebbecke ME

Assessing the Effectiveness of (Parallel) Branch-and-bound Algorithms

• 发表时间: 2021-04
• 期刊: ArXiv
• 作者: Stephen J. Maher;T. Ralphs;Y. Shinano

Implementing the branch-and-cut approach for a general purpose Benders' decomposition framework

• DOI: 10.1016/j.ejor.2020.08.037
• 发表时间: 2021-04-16
• 期刊: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
• 影响因子: 6.4
• 作者: Maher, Stephen J.