CAREER: Mixed-Integer Optimization under Joint Chance Constraints

职业：联合机会约束下的混合整数优化

• 批准号: 1055668
• 负责人: Simge Kucukyavuz
• 金额: $ 40万
• 依托单位: Ohio State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-08-01 至 2017-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1055668&HistoricalAwards=false
• 关键词: CAREER; Mixed; Integer; Optimization; under

The research objective of this Faculty Early Career Development (CAREER) project is to advance models, theory and algorithms to solve a difficult class of optimization problems called chance-constrained mixed-integer programs (CC-MIP). Although CC-MIPs are ubiquitous in practice, operations research theory and algorithms provide limited guidance for this class of problems. CC-MIPs include quality of service or reliability constraints; they are dynamic, contain uncertain data, and involve discrete decisions. The resulting multi-stage stochastic mixed-integer programs are challenging both theoretically and computationally. The service level requirements are modeled with joint chance constraints, which are non-convex. In addition, the deterministic equivalents of CC-MIPs are very large-scale MIPs. To overcome these challenges, this research aims to develop a unified theory and computational methodology, utilizing extended formulations, polyhedral combinatorics, and decomposition algorithms. The research will be pursued in four major thrusts: (1) chance-constrained mixed-integer programs, (2) dynamic chance-constrained problems, (3) chance-constrained problems with special structures, and (4) chance-constrained problems with technology uncertainty. The results from this research will advance decision-making tools in several sectors that operate under uncertain environments and high service level expectations, such as energy, telecommunications, finance, emergency management, and distribution systems. For example, the modeling framework and strong cutting planes for joint chance constraints may be incorporated into existing open-source MIP modeling languages and software to improve their ability to solve CC-MIPs that arise in practice. The educational goals of this award are to develop novel programs that will arm the next generation of students with skills to incorporate uncertainty into optimization theory, models and solution methods, and to attract women and other under-represented groups to pursue advanced research in this field. In pursuit of these goals, case studies will be developed from application areas to highlight the importance of incorporating uncertainty into decision-making processes, and tutorials will be given through various fora to disseminate the research results to a broader audience.

这个教师早期职业发展（CAREER）项目的研究目标是推进模型，理论和算法，以解决一类困难的优化问题，称为机会约束混合整数规划（CC-MIP）。 虽然CC-MIP在实践中是普遍存在的，运筹学理论和算法提供了有限的指导，这类问题。 CC-MIP包括服务质量或可靠性约束，它们是动态的，包含不确定的数据，并涉及离散的决策。由此产生的多阶段随机混合整数规划在理论和计算上都具有挑战性。服务水平的需求建模与联合机会约束，这是非凸的。此外，CC-MIP的确定性等价物是非常大规模的MIP。为了克服这些挑战，本研究的目的是开发一个统一的理论和计算方法，利用扩展配方，多面体组合学和分解算法。本研究将在四个主要方向进行：（1）机会约束混合整数规划，（2）动态机会约束问题，（3）特殊结构的机会约束问题，（4）技术不确定性的机会约束问题。这项研究的结果将推动在不确定环境和高服务水平期望下运营的几个部门的决策工具，如能源，电信，金融，应急管理和配电系统。例如，用于联合机会约束的建模框架和强切割平面可以被并入现有的开源MIP建模语言和软件中，以提高它们解决实践中出现的CC-MIP的能力。 该奖项的教育目标是开发新颖的计划，将武装下一代学生的技能，将不确定性纳入优化理论，模型和解决方案的方法，并吸引妇女和其他代表性不足的群体在这一领域进行先进的研究。为了实现这些目标，将从应用领域开展案例研究，以突出将不确定性纳入决策过程的重要性，并将通过各种论坛提供指导，向更广泛的受众传播研究成果。