Research in Large-Scale Integer Programming

大规模整数规划研究

• 批准号: 9700285
• 负责人: George Nemhauser
• 金额: $ 50.1万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-07-15 至 2001-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9700285&HistoricalAwards=false
• 关键词: Research; Large; Scale; Integer; Programming

9700285 Nemhauser This research involves the development of solution methods for mixed-integer programming problems. The objective of a mixed-integer programming problem is to maximize a function subject to linear inequality (or equality) constraints and integrality restrictions on some or all of the variables. The goals of the research are to develop new methodology, algorithms, and prototype software for solving this class of programming problems. The research addresses two specific problem domains, stochastic integer programming and set partitioning, which have heretofore not received much attention. The researchers will investigate linear programming-based approximation methods, parallel integer programming, and decomposition techniques as methodologies for obtaining robust solutions to these difficult combinatorial problems. The research results are to be implemented in openly distributed software systems, and will thus be accessible throughout the research community. Mixed-integer programs have broad application in solving problems that arise in logistics and distribution, production planning, aircraft (flight and crew) scheduling, and resource allocation. It is likely that tremendous progress in the size of problems that can be solved and in the time it takes to solve them will come from parallel computing, and thus this research has high potential to improve decision-making in such large-scale systems.

9700285 Nemhauser这项研究涉及混合整数规划问题的求解方法的发展。混合整数规划问题的目标是最大化一个函数，该函数对部分或全部变量具有线性不等式(或等式)约束和完整性约束。研究的目标是开发新的方法、算法和原型软件来解决这类编程问题。这项研究解决了两个具体的问题领域，随机整数规划和集合划分，到目前为止还没有得到太多的关注。研究人员将研究基于线性规划的近似方法、并行整数规划和分解技术，作为获得这些困难组合问题的稳健解的方法。研究成果将在开放的分布式软件系统中实施，因此将在整个研究界获得。混合整数规划在解决物流配送、生产计划、飞机(飞行和机组)调度、资源分配等问题中有着广泛的应用。并行计算很可能在可以解决的问题的大小和解决这些问题所需的时间方面取得巨大的进步，因此这项研究在改善如此大规模的系统中的决策方面具有很高的潜力。