(Mixed) Integer and Combinatorial Optimization: New Convexification Techniques
(混合)整数和组合优化:新的凸化技术
基本信息
- 批准号:1263239
- 负责人:
- 金额:$ 47.5万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2013
- 资助国家:美国
- 起止时间:2013-06-01 至 2016-05-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
The objective of this research project is to investigate new ideas that could potentially further accelerate the revolution in integer programming. This project will investigate more efficient convexification techniques: a new cutting plane paradigm that generates a pool of points from which cuts can be produced, and a theory of cut-generating functions, both aimed at finding deeper cuts more efficiently. Integer programming has experienced a revolution in the last two decades that has greatly advanced our ability to solve practical problems in engineering, manufacturing, transportation, telecommunication, finance, marketing and many other areas of economic activity. According to recently performed extensive testing, integer programming solvers are now close to a billion times faster than they were twenty years ago. Better integer programming algorithms (including their linear programming components) account for a speedup of about half a million times, the rest of the improvement (by a factor of about 1600) coming from faster computers. A key element of this transformation was a breakthrough in the use of cutting planes in the early nineties, including the design of the lift-and-project cuts and the ensuing revival of the Gomory mixed integer cuts, two projects carried out by the principal investigators with previous NSF support.Progress in the ability to solve large-scale mixed integer linear programs will affect problem solving and improve efficiency of operations in an extremely broad range of activities that include industrial production, supply chain management, logistics, transportation, electricity production, airport operations, telecommunication networks, health care applications such as scheduling intensive care units and determining radiation dosage, combinatorial auctions, finance and economics. The widespread impact of tools developed in this project will contribute to technological excellence and strengthen US technological leadership.
这个研究项目的目标是研究可能进一步加速整数规划革命的新想法。这个项目将研究更有效的凸化技术:一个新的切割平面范例,产生一个点池,从这些点可以产生切割,和切割生成函数的理论,都旨在更有效地找到更深的切割。 在过去的二十年里,编程经历了一场革命,极大地提高了我们解决工程、制造、运输、电信、金融、营销和许多其他经济活动领域实际问题的能力。根据最近进行的广泛测试,整数编程求解器现在比二十年前快了近十亿倍。更好的整数规划算法(包括它们的线性规划部分)可以加速大约50万倍,其余的改进(大约1600倍)来自更快的计算机。这一转变的一个关键因素是90年代初切割平面的使用取得了突破,包括升降和投影切割的设计以及随后的戈莫里混合整数切割的复兴,两个项目进行的主要研究人员与以前的国家科学基金会的支持。进展的能力,以解决大-规模混合整数线性规划将影响问题解决并提高包括工业生产,供应链管理,物流,运输,电力生产、机场运营、电信网络、医疗保健应用(如调度重症监护病房和确定辐射剂量)、组合拍卖、金融和经济。该项目开发的工具的广泛影响将有助于技术卓越并加强美国的技术领导地位。
项目成果
期刊论文数量(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 }}
Egon Balas其他文献
Robert G. Jeroslow 1942–1988
- DOI:
10.1007/bf01531066 - 发表时间:
2013-10-22 - 期刊:
- 影响因子:1.000
- 作者:
Egon Balas - 通讯作者:
Egon Balas
Job Shop Scheduling With Deadlines
- DOI:
10.1023/a:1009750409895 - 发表时间:
1998-12-01 - 期刊:
- 影响因子:1.100
- 作者:
Egon Balas;Giuseppe Lancia;Paolo Serafini;Alkiviadis Vazacopoulos - 通讯作者:
Alkiviadis Vazacopoulos
Integer programming and convex analysis: Intersection cuts from outer polars
- DOI:
10.1007/bf01584553 - 发表时间:
1972-02-01 - 期刊:
- 影响因子:2.500
- 作者:
Egon Balas - 通讯作者:
Egon Balas
On the relationship between standard intersection cuts, lift-and-project cuts, and generalized intersection cuts
- DOI:
10.1007/s10107-015-0975-1 - 发表时间:
2016-01-14 - 期刊:
- 影响因子:2.500
- 作者:
Egon Balas;Tamás Kis - 通讯作者:
Tamás Kis
Logical Constraints as Cardinality Rules: Tight Representation
- DOI:
10.1023/b:joco.0000031413.33955.62 - 发表时间:
2004-06-01 - 期刊:
- 影响因子:1.100
- 作者:
Egon Balas - 通讯作者:
Egon Balas
Egon Balas的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Egon Balas', 18)}}的其他基金
Mixed Integer Optimization: New Cut Generation Paradigms
混合整数优化:新的切割生成范式
- 批准号:
1560828 - 财政年份:2016
- 资助金额:
$ 47.5万 - 项目类别:
Standard Grant
Integer and Combinatorial Optimization: Intersection Cuts from Multiple Rows
整数和组合优化:从多行进行交集切割
- 批准号:
1024554 - 财政年份:2010
- 资助金额:
$ 47.5万 - 项目类别:
Standard Grant
Mixed Integer and Combinatorial Optimization: Lift-and-Project and Polyhedral Combinatorics
混合整数和组合优化:提升投影和多面体组合
- 批准号:
0653419 - 财政年份:2007
- 资助金额:
$ 47.5万 - 项目类别:
Standard Grant
Polyhedral and Graph Theoretic Methods in Mixed Integer and Combinatorial Optimization
混合整数和组合优化中的多面体和图论方法
- 批准号:
0352885 - 财政年份:2004
- 资助金额:
$ 47.5万 - 项目类别:
Continuing Grant
Integer and Combinatorial Optimization: Polyhedral and Graph Theoretic Methods
整数和组合优化:多面体和图论方法
- 批准号:
0098427 - 财政年份:2001
- 资助金额:
$ 47.5万 - 项目类别:
Continuing Grant
Combinatorial Optimization and Integer Programming: Polyhedral Analysis and Algorithms
组合优化和整数规划:多面体分析和算法
- 批准号:
9802773 - 财政年份:1998
- 资助金额:
$ 47.5万 - 项目类别:
Continuing Grant
GIG: Algorithms, Combinatorics & Optimization: An Interdisciplinary Ph.D. Program
GIG:算法、组合学
- 批准号:
9509581 - 财政年份:1995
- 资助金额:
$ 47.5万 - 项目类别:
Continuing Grant
Polyherdral Methods in Integer and Combinatorial Optimization
整数和组合优化中的多面体方法
- 批准号:
9424348 - 财政年份:1995
- 资助金额:
$ 47.5万 - 项目类别:
Continuing Grant
Integer and Combinatorial Optimization: Polyhedral Methods and Algorithms
整数和组合优化:多面体方法和算法
- 批准号:
9201340 - 财政年份:1992
- 资助金额:
$ 47.5万 - 项目类别:
Continuing Grant
Second Integer Programming and Combinatorial Optimization Conference; Pittsburgh, PA; May 25-27, 1992
第二届整数规划与组合优化会议;
- 批准号:
9114298 - 财政年份:1991
- 资助金额:
$ 47.5万 - 项目类别:
Standard Grant
相似海外基金
NSF Student Travel Grant for 2019 Integer Programming and Combinatorial Optimization (IPCO)
NSF 2019 年整数规划和组合优化 (IPCO) 学生旅费补助金
- 批准号:
1856307 - 财政年份:2019
- 资助金额:
$ 47.5万 - 项目类别:
Standard Grant
Integer and Combinatorial Optimization: Intersection Cuts from Multiple Rows
整数和组合优化:从多行进行交集切割
- 批准号:
1024554 - 财政年份:2010
- 资助金额:
$ 47.5万 - 项目类别:
Standard Grant
Mixed Integer and Combinatorial Optimization: Lift-and-Project and Polyhedral Combinatorics
混合整数和组合优化:提升投影和多面体组合
- 批准号:
0653419 - 财政年份:2007
- 资助金额:
$ 47.5万 - 项目类别:
Standard Grant
Polyhedral and Graph Theoretic Methods in Mixed Integer and Combinatorial Optimization
混合整数和组合优化中的多面体和图论方法
- 批准号:
0352885 - 财政年份:2004
- 资助金额:
$ 47.5万 - 项目类别:
Continuing Grant
Integer and Combinatorial Optimization: Polyhedral and Graph Theoretic Methods
整数和组合优化:多面体和图论方法
- 批准号:
0098427 - 财政年份:2001
- 资助金额:
$ 47.5万 - 项目类别:
Continuing Grant
Combinatorial Commutative Algebra and Integer Programming
组合交换代数和整数规划
- 批准号:
0100141 - 财政年份:2001
- 资助金额:
$ 47.5万 - 项目类别:
Standard Grant
Combinatorial Optimization and Integer Programming: Polyhedral Analysis and Algorithms
组合优化和整数规划:多面体分析和算法
- 批准号:
9802773 - 财政年份:1998
- 资助金额:
$ 47.5万 - 项目类别:
Continuing Grant
Polyherdral Methods in Integer and Combinatorial Optimization
整数和组合优化中的多面体方法
- 批准号:
9424348 - 财政年份:1995
- 资助金额:
$ 47.5万 - 项目类别:
Continuing Grant
Integer and Combinatorial Optimization: Polyhedral Methods and Algorithms
整数和组合优化:多面体方法和算法
- 批准号:
9201340 - 财政年份:1992
- 资助金额:
$ 47.5万 - 项目类别:
Continuing Grant
Second Integer Programming and Combinatorial Optimization Conference; Pittsburgh, PA; May 25-27, 1992
第二届整数规划与组合优化会议;
- 批准号:
9114298 - 财政年份:1991
- 资助金额:
$ 47.5万 - 项目类别:
Standard Grant