Discrete and Continuous Nonconvex Optimization with Applications to Production, Distribution, and Design Problems

离散和连续非凸优化及其在生产、分销和设计问题中的应用

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

9812047Sherali This grant provides funding for the development and study of a new methodology, the Reformulation-Linearization/Convexification Technique (RLT), for generating tight relaxations that can be used to construct exact solution methods as well as to design powerful heuristic procedures for large classes of discrete combinatorial and continuous nonconvex programming problems. For linear mixed-integer 0-1 problems, specialized RLT relaxations that are enhanced by conditional logic implications will be developed and embedded within a dynamic Lagrangian Relaxation constraint generation scheme. In the context of continuous nonconvex programs, new theoretically convergent and computationally effective global optimization RLT approaches will be developed to solve a wide class of factorable nonlinear programs. Extensions and specializations for minimax problems that arise in situations dealing with multiple criteria and equity issues, and for general integer/discrete problems will also be explored. In order to effectively cope with the size and structure of the relaxations that are typically generated by RLT, various Lagrangian dual, aggregation, penalty function, trust region, and conjugate/deflected subgradient methods will be investigated. These ideas and methods will be applied to design novel approaches to solve a variety of location-allocation problems, telecommunication and pipe-network design problems, machine scheduling problems, and air traffic control management problems. If successful, the results of this research will lead to the development of a new comprehensive technology that unifies many important concepts and offers insights into problem structures and modeling strategies. Operations Research analysts and practitioners will be able to use this methodology to construct tight model representations, generate strong valid inequalities, and design effective procedures for solving hard, discrete and continuous, nonconvex problems that arise often in practice. The research canl contribute toward the design of various computational tools that may be incorporated in public domain software for solving such classes of problems.

小行星9812047 这笔赠款提供资金的开发和研究的一种新的方法，重新制定线性化/凸化技术（RLT），产生紧松弛，可用于构建精确的解决方案的方法，以及设计强大的启发式程序的大类离散组合和连续的非凸规划问题。对于线性混合整数0-1问题，将开发通过条件逻辑含义增强的专用RLT松弛，并嵌入动态拉格朗日松弛约束生成方案中。在连续非凸规划的背景下，新的理论上收敛和计算有效的全局优化RLT方法将被开发来解决广泛的一类可因子分解的非线性规划。在处理多个标准和公平问题的情况下出现的极大极小问题，以及一般整数/离散问题的扩展和专业化也将进行探讨。 为了有效地科普的大小和结构的松弛，通常产生的RLT，各种拉格朗日对偶，聚合，罚函数，信赖域，共轭/偏转次梯度法将进行调查。这些想法和方法将被应用于设计新的方法来解决各种位置分配问题，电信和管道网络设计问题，机器调度问题，空中交通管制管理问题。 如果成功的话，这项研究的结果将导致一种新的综合技术的发展，该技术将许多重要的概念统一起来，并提供对问题结构和建模策略的见解。运筹学分析师和从业者将能够使用这种方法来构建紧密的模型表示，生成强有效的不等式，并设计有效的程序来解决实践中经常出现的困难，离散和连续，非凸问题。这项研究可以有助于设计各种计算工具，可以纳入公共领域的软件来解决这类问题。