Enhancing the Solvability of Discrete and Continuous Nonconvex Programs with Applications to Production, Design, and Operational Problems

通过在生产、设计和操作问题中的应用来增强离散和连续非凸程序的可解性

• 批准号: 0552676
• 负责人: Hanif Sherali
• 金额: $ 32.06万
• 依托单位: Virginia Polytechnic Institute and State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-09-01 至 2009-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0552676&HistoricalAwards=false
• 关键词: Enhancing; Solvability; Discrete; Continuous; Nonconvex

This project deals with theoretical and algorithmic developments, as well as computational implementation issues related to the Reformulation-Linearization/Convexification Technique (RLT). In the context of 0-1 and general discrete mixed-integer programs, a dynamic Lagrangian relaxation strategy will be developed to automatically generate judicious RLT-enhanced reformulations. Specializations for minimax problems will also be investigated. Extensions to general integer or discrete programs, including the development of a new class of Chvatal-Gomory Tier Cuts, as well as extensions to convex-constrained problems will be studied. In the arena of continuous nonconvex factorable programming problems, various RLT constraint generation and filtering strategies for constructing tight manageable relaxations will be developed, including a new class of semidefinite cuts for enhancing the model representation. Applications arising in national airspace planning and air-traffic management, production scheduling, engineering design under uncertainty, and wireless communication network design will be explored. The study of these applications will encompass polyhedral analyses of certain combinatorial optimization problems such as the generalized vertex packing problem and the asymmetric traveling salesman problem.The results of this study will advance concepts and offer insights into problem structures and modeling strategies, as well as provide a construct for generating tight relaxations leading to effective procedures for solving the above types of problems. The contributions will advance optimization theory as well as impact the aforementioned application domains. In particular, the air-traffic management application proposed for study will be investigated in cooperation with the Federal Aviation Administration (FAA), and will benefit society by reducing delays and related airline costs, as well as by enhancing the safety and operational efficiency of the national airspace. Students from across the College of Engineering will be involved in this research effort, and the technology generated by this project will be disseminated via public domain software.

该项目涉及理论和算法的发展，以及与重构线性化/凸化技术（RLT）相关的计算实现问题。 在0-1和一般的离散混合整数规划的背景下，动态拉格朗日松弛策略将自动生成明智的RLT增强的重新配方。专业化的极小极大问题也将进行调查。扩展到一般整数或离散程序，包括开发一类新的Chvatal-Gomory层切割，以及扩展到凸约束问题将进行研究。 在竞技场的连续非凸可因式分解规划问题，各种RLT约束生成和过滤策略，用于构建紧密管理松弛将开发，包括一类新的半定切割，以提高模型的表示。将探讨在国家空域规划和空中交通管理，生产调度，不确定性下的工程设计和无线通信网络设计中的应用。这些应用的研究将包括多面体分析的某些组合优化问题，如广义顶点包装问题和非对称旅行商problem.本研究的结果将推进概念，并提供深入了解问题的结构和建模策略，以及提供一个构造产生紧密松弛导致有效的程序来解决上述类型的问题。这些贡献将推动优化理论的发展，并影响上述应用领域。特别是，将与联邦航空管理局（FAA）合作研究拟议研究的空中交通管理应用，并将通过减少延误和相关的航空公司成本以及提高国家空域的安全和运营效率来造福社会。 来自工程学院的学生将参与这项研究工作，该项目产生的技术将通过公共领域软件传播。