A New Computationally Efficient Approach for Discrete Optimization in Hierarchical Decision-Making

分层决策中离散优化的一种新的高效计算方法

• 批准号: 1642514
• 负责人: Bo Zeng
• 金额: $ 15.62万
• 依托单位: University of Pittsburgh
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2018-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1642514&HistoricalAwards=false
• 关键词: New; Computationally; Efficient; Approach; Discrete

Bilevel optimization is a framework to model a hierarchical decision system where two decision makers interact in a sequential way when they pursue their own objectives. It is currently applied to study and support many real decision-making problems where centralized control is not applicable, including those arising from government policy design, economics, social science, defense and security. However, it is computationally challenging to make such decisions. In particular, bilevel optimization with discrete decisions in the lower level remains computationally unsolved. This research will produce a novel and efficient algorithm paradigm to compute bilevel discrete optimization problems, including unstructured formulations and popular interdiction models. Various analytical insights and algorithm enhancements will be investigated and developed. Results will be further incorporated into publicly available and professional optimization solvers to provide decision support to users in government agencies, military forces and other societal organizations with different analytical backgrounds. Teaching and learning materials will be designed to disseminate research results. Graduate and undergraduate students will benefit through lectures and research experiences. Therefore, broad and positive impacts will be produced in the U.S. government policy making, economy, education, and defense and security areas.The solution scheme from this research will include non-traditional reformulations of bilevel mixed integer program (MIP) that yield relaxations theoretically stronger than existing ones. It will also involve a new decomposition framework that progressively explores solution space and strengthens bounds. Advanced relaxation techniques, branch-and-bound strategies and strong valid inequalities, along with integration of fast heuristics and popular optimization algorithms, will be studied, developed and evaluated. If successful, the intellectual merit of this research will include: (i) the first general, complete and empirically verified algorithmic procedure with a comprehensive analysis will become available to compute bilevel MIP problems; (ii) the solution capability will be substantially improved to solve instances from practice; (iii) integration methods with other efficient computing approaches will be developed and demonstrated to address different variants of bilevel MIP and large-scale applications; (iv) a new algorithm philosophy will enrich existing literature on optimization and algorithm design; (v) modeling and computing packages will be implemented and provided for public access and rapid prototyping.

双层优化是一个框架来模拟一个分层决策系统，其中两个决策者在追求自己的目标时以顺序的方式进行交互。它目前被应用于研究和支持许多真实的决策问题，其中集中控制是不适用的，包括那些产生于政府政策设计，经济学，社会科学，国防和安全。 然而，做出这样的决定在计算上是具有挑战性的。特别是，在较低级别的离散决策的双层优化仍然是计算上未解决的。这项研究将产生一个新的和有效的算法范式来计算双层离散优化问题，包括非结构化配方和流行的阻断模型。将研究和开发各种分析见解和算法增强。结果将进一步纳入公开和专业的优化求解器，为政府机构，军队和其他具有不同分析背景的社会组织的用户提供决策支持。将设计教学材料，以传播研究成果。研究生和本科生将通过讲座和研究经验受益。因此，广泛和积极的影响，将产生在美国政府的政策制定，经济，教育，国防和安全领域。本研究的解决方案将包括非传统的双层混合整数规划（MIP）的重新制定，产生理论上比现有的松弛。它还将涉及一个新的分解框架，逐步探索解决方案空间并加强边界。先进的松弛技术，分支定界策略和强有效的不等式，沿着快速算法和流行的优化算法的集成，将被研究，开发和评估。 如果成功的话，本研究的智力价值将包括：（i）第一个通用的，完整的和经验验证的算法程序与全面的分析将成为可用于计算双层MIP问题：（ii）解决方案的能力将大大提高，以解决来自实践的例子;（iii）将开发和演示与其他有效计算方法的集成方法，以解决两级MIP的不同变体和大规模应用; ㈣一种新的算法哲学将丰富关于最优化和算法设计的现有文献; ㈤将实施建模和计算包，供公众查阅和快速制作原型。