Enhancing decomposition techniques using large-neighbourhood search to solve large-scale optimisation problems
Enhancing decomposition techniques using large-neighbourhood search to solve large-scale optimisation problems
批准号:
EP/P003060/2
负责人:
Stephen Maher
金额:
$11.21万
依托单位:
依托单位国家:
英国
项目类别:
Fellowship
财政年份:
2019
资助国家:
英国
项目状态:
已结题
起止时间:
2019 至 --
中文摘要
优化是当今社会的基本组成部分。许多服务的规划、管理和运作都依赖于优化服务的效率和成本效益。随着对服务的需求不断增长,对高效运营的需求变得越来越重要。交通运输是优化技术研究和发展的主要受益者。这些好处包括:通过提高铁路的运行效率,降低成本;通过更好地分配飞机,增加航空公司提供的服务;通过更好地整合机组人员和飞机,提高航空公司和铁路运营商的准点率。然而,由于我们解决日益复杂的优化问题的能力有限,维持低成本和提供高效运营的能力受到了限制。运输和其他行业的进一步发展将通过研究和开发优化问题的解决方案技术来实现。这项研究的目的是改进当前的优化技术,以扩展可解决问题的领域,超越当前的限制。该研究将借鉴当前数学优化两个密切相关领域的研究——混合整数规划(MIP)和分解技术。大邻域搜索的非精确MIP求解方法对于寻找优化问题的良好解具有重要的价值。而Benders分解的精确分解技术则大大简化了问题的表述,提供了一种有效的求解方法。本文将采用大邻域搜索的最新进展来显著改进Benders分解的求解算法。该项目将利用整合这两种方法的协同作用,扩展当前解决大规模优化问题的能力。该项目将研究增强bender的分解,并确定有效使用并行计算基础设施的策略。该奖学金将实现以下目标:1)制作一个软件包,用于将Benders分解应用于一般的大规模优化问题。将Benders分解与大邻域搜索相结合,开发出一种增强的求解器。由此产生的软件将能够解决来自工业界和学术界的大规模优化问题。2)基于大邻域搜索启发式框架的Benders分解并行化方案的发展。并行化方案将利用现代计算架构来显著减少解决方案的运行时间。此外,算法的发展将为未来的并行计算研究奠定基础。开发的软件将提供工具,将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.
期刊论文(5)
专著(0)
科研奖励(0)
会议论文
登录
查看更多内容
DOI:
10.1016/j.cor.2022.105719
发表时间:
2022-02
期刊:
Comput. Oper. Res.
影响因子:
--
作者:
[E. Reynolds;Stephen J. Maher]
通讯作者:
E. Reynolds;Stephen J. Maher
Avoiding redundant columns by adding classical Benders cuts to column generation subproblems
通过向列生成子问题添加经典的 Benders 切割来避免冗余列
DOI:
--
发表时间:
2019
期刊:
影响因子:
--
作者:
[Luebbecke ME]
通讯作者:
Luebbecke ME
DOI:
--
发表时间:
2021-04
期刊:
ArXiv
影响因子:
--
作者:
[Stephen J. Maher;T. Ralphs;Y. Shinano]
通讯作者:
Stephen J. Maher;T. Ralphs;Y. Shinano
DOI:
10.1016/j.ejor.2020.08.037
发表时间:
2021-04-16
期刊:
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
影响因子:
6.4
作者:
[Maher, Stephen J.]
通讯作者:
Maher, Stephen J.
Enhancing decomposition techniques using large-neighbourhood search to solve large-scale optimisation problems
-
批准号:EP/P003060/1
-
项目类别:Fellowship
-
资助金额:$33.76万
-
财政年份:2017
-
负责人:Stephen Maher
-
依托单位:
国内基金
海外基金
长白山垂直带土壤动物多样性及其在凋落物分解和元素释放中的贡献
-
批准号:41171207
-
项目类别:面上项目
-
资助金额:85.0万元
-
批准年份:2011
-
负责人:殷秀琴
-
依托单位:
松嫩草地土壤动物多样性及其在凋落物分解中作用和物质能量收支研究
-
批准号:40871120
-
项目类别:面上项目
-
资助金额:45.0万元
-
批准年份:2008
-
负责人:殷秀琴
-
依托单位: