New Hierarchies, Cutting Planes, and Algorithms for Mixed Integer Optimization
用于混合整数优化的新层次结构、割平面和算法
基本信息
- 批准号:1913294
- 负责人:
- 金额:$ 10万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2019
- 资助国家:美国
- 起止时间:2019-08-01 至 2020-07-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Mathematical optimization problems arise in many applications in diverse fields in science and engineering. A large portion of these problems require discrete decisions to be made, where some of the unknowns are restricted to take only integer values. There continues to be a pressing need to further improve the performance of the state-of-the-art for solving mixed integer problems, especially when the unknowns in the problem are constrained through nonlinear relationships. This research project develops new mathematics for optimizing mixed integer problems. The overall impact will be visible through the implementation of new and sophisticated algorithms for solving these problems. An auxiliary algorithm will be developed to aid our main algorithm and it will also be applicable to optimization in decision theory, game theory, and cryptography. The algorithms will be empirically tested on benchmark problems, and used to solve an application in oil and gas industry and a fundamental problem in statistical learning that is widely-used for predictive analytics. Research from this project will be integrated into classroom through the development of a new graduate course that teaches algebraic and combinatorial methods in discrete optimization. The award will provide support for graduate student training through research.The primary research objective of this project in computational mathematics is to derive novel polyhedral relaxations for the feasible regions of mixed integer problems (MIPs) through an innovative interpretation of discrete feasible regions arising from ordered sets of integral vectors under some monomial ordering. The research activities involve developing a rich body of knowledge about cutting planes, valid inequalities, and polyhedral relaxations for MIPs, approximation algorithms for MIPs, and using discretization methods to efficiently approximate MIPs with polynomial constraints. Thus, this project will establish new connections between computational algebra, combinatorics, and mathematical optimization. One of our methods for generating cutting planes using a monomial order generalizes and strengthens the cutting planes derived from the well-known split disjunctions. The theory we develop does not depend explicitly on the algebraic representation of the feasible set, therefore making it applicable to all classes of MIP and presenting a very different approach than many of the existing studies that explicitly depend on the linearity of the constraints.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
数学优化问题在科学和工程的不同领域的许多应用中出现。这些问题中的很大一部分需要离散决策,其中一些未知数被限制为仅取整数值。仍然迫切需要进一步提高解决混合整数问题的最新技术的性能,特别是当问题中的未知数通过非线性关系受到约束时。本研究项目开发了优化混合整数问题的新数学。通过实施新的复杂算法来解决这些问题,整体影响将是可见的。一个辅助算法将被开发,以帮助我们的主要算法,它也将适用于决策论,博弈论和密码学的优化。这些算法将在基准问题上进行经验测试,并用于解决石油和天然气行业的应用以及广泛用于预测分析的统计学习中的基本问题。从这个项目的研究将通过一个新的研究生课程,教离散优化的代数和组合方法的发展融入课堂。该项目的主要研究目标是通过对离散可行域的创新解释,为混合整数问题(MIP)的可行域推导出新颖的多面体松弛方法,这些可行域是由一些单项序下的有序积分向量集产生的。研究活动涉及开发有关切割平面,有效不等式和多面体松弛MIP,MIP近似算法,以及使用离散化方法有效地近似MIP与多项式约束的丰富知识。因此,这个项目将建立计算代数,组合学和数学优化之间的新联系。我们的方法之一,用于生成切割平面使用单项式的顺序推广和加强切割平面来自著名的分裂析取。我们开发的理论并不明确依赖于可行集的代数表示,因此,它适用于所有类别的MIP,并提出了一个非常不同的方法,比许多现有的研究,明确取决于线性的限制。这个奖项反映了NSF的法定使命,并已被认为是值得支持的评估使用基金会的智力价值和更广泛的影响审查的搜索.
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Akshay Gupte其他文献
Computing the Edge Expansion of a Graph Using Semidefinite Programming
使用半定规划计算图的边展开
- DOI:
10.1007/978-3-031-60924-4_9 - 发表时间:
2024 - 期刊:
- 影响因子:2.4
- 作者:
Akshay Gupte;Melanie Siebenhofer;Angelika Wiegele - 通讯作者:
Angelika Wiegele
Convex hulls of superincreasing knapsacks and lexicographic orderings
- DOI:
10.1016/j.dam.2015.08.010 - 发表时间:
2016-03-11 - 期刊:
- 影响因子:
- 作者:
Akshay Gupte - 通讯作者:
Akshay Gupte
Multilinear Formulations for Computing a Nash Equilibrium of Multi-Player Games
用于计算多人博弈纳什均衡的多线性公式
- DOI:
10.4230/lipics.sea.2023.12 - 发表时间:
2022 - 期刊:
- 影响因子:0
- 作者:
Miriam Fischer;Akshay Gupte - 通讯作者:
Akshay Gupte
Glycated Hemoglobin Trajectories and Their Association With Treatment Outcomes Among Patients With Pulmonary TB in India: A Prospective Cohort Study
印度肺结核患者糖化血红蛋白变化轨迹及其与治疗结局的关联:一项前瞻性队列研究
- DOI:
10.1016/j.chest.2023.08.026 - 发表时间:
2024-02-01 - 期刊:
- 影响因子:8.600
- 作者:
Geeta Pardeshi;Vidya Mave;Sanjay Gaikwad;Dileep Kadam;Madhusudan Barthwal;Tushar Sahasrabudhe;Arjun Kakrani;Nikhil Gupte;Sachin Atre;Sona Deshmukh;Jonathan E. Golub;Akshay Gupte - 通讯作者:
Akshay Gupte
Akshay Gupte的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Akshay Gupte', 18)}}的其他基金
Collaborative Research: 2018 Mixed Integer Programming Workshop Poster Session, Greenville, South Carolina, June 18-21, 2018
协作研究:2018 年混合整数编程研讨会海报会议,南卡罗来纳州格林维尔,2018 年 6 月 18 日至 21 日
- 批准号:
1841292 - 财政年份:2018
- 资助金额:
$ 10万 - 项目类别:
Standard Grant
相似海外基金
Collaborative Research: Constraining the Role of the Antarctic Slope Current on Tracer Exchange at the Antarctic Margin using Model Hierarchies
合作研究:利用模型层次结构约束南极坡流对南极边缘示踪剂交换的作用
- 批准号:
2319828 - 财政年份:2024
- 资助金额:
$ 10万 - 项目类别:
Standard Grant
Collaborative Research: Constraining the Role of the Antarctic Slope Current on Tracer Exchange at the Antarctic Margin using Model Hierarchies
合作研究:利用模型层次结构约束南极坡流对南极边缘示踪剂交换的作用
- 批准号:
2319829 - 财政年份:2024
- 资助金额:
$ 10万 - 项目类别:
Standard Grant
Elucidation of Characteristics and Functions of Rituals of Japanese New Religions : To Reconsider Their Worldviews and Hierarchies
日本新宗教仪式的特征和功能的阐释:重新考虑他们的世界观和等级制度
- 批准号:
22KJ1273 - 财政年份:2023
- 资助金额:
$ 10万 - 项目类别:
Grant-in-Aid for JSPS Fellows
'RITUAL FRACTURE': DISMANTLING PATRIARCHAL HIERARCHIES THROUGH A QUEER, ANTI-CASTE, ECOFEMINIST RITUAL POETICS
“仪式断裂”:通过酷儿、反种姓、生态女性主义的仪式诗学来瓦解父权等级制度
- 批准号:
2891647 - 财政年份:2023
- 资助金额:
$ 10万 - 项目类别:
Studentship
Cultural Hierarchies in Health: Does inherited sociocultural position (biraderi) shape diet and nutrition among British Pakistani children?
健康中的文化等级:继承的社会文化地位(biraderi)是否影响了英属巴基斯坦儿童的饮食和营养?
- 批准号:
ES/X012816/1 - 财政年份:2023
- 资助金额:
$ 10万 - 项目类别:
Research Grant
'RITUAL FRACTURE': DISMANTLING PATRIARCHAL HIERARCHIES THROUGH A QUEER, ANTI-CASTE, ECOFEMINIST RITUAL POETICS
“仪式断裂”:通过酷儿、反种姓、生态女性主义的仪式诗学来瓦解父权等级制度
- 批准号:
2904689 - 财政年份:2023
- 资助金额:
$ 10万 - 项目类别:
Studentship
CAREER: Programming Heterogeneous Memory Hierarchies
职业:异构内存层次结构编程
- 批准号:
2239373 - 财政年份:2023
- 资助金额:
$ 10万 - 项目类别:
Continuing Grant
Neural processing of status signals in social hierarchies
社会等级中状态信号的神经处理
- 批准号:
10646570 - 财政年份:2023
- 资助金额:
$ 10万 - 项目类别:
Dynamic task scheduling strategies for deep memory hierarchies in the future
未来深度内存层次结构的动态任务调度策略
- 批准号:
22KJ0677 - 财政年份:2023
- 资助金额:
$ 10万 - 项目类别:
Grant-in-Aid for JSPS Fellows
Hierarchies of spatiotemporal anticipation in the human brain
人脑中时空预期的层次结构
- 批准号:
10558919 - 财政年份:2023
- 资助金额:
$ 10万 - 项目类别: