A Unifying Approach for Discrete and Continuous Nonconvex Optimization with Applications to Operational and Design Problems

本研究项目关注的是一个统一的解决方案的方法，即重新制定线性化/凸化技术（RLT），已开发的大类离散组合和连续非凸规划问题产生紧松弛。在这个项目中解决的各种贡献涉及一般的理论和算法概念的发展，以及几个重要的应用程序的专门程序，沿着广泛的计算测试伴随着相关的实施问题的调查。 对于线性混合整数0-1的问题，我们探索设计有效的RLT松弛，增强条件逻辑的影响，并嵌入在一个动态拉格朗日松弛约束生成方案。 在连续非凸问题的背景下，我们提出了各种策略的研究，以产生紧密的管理松弛设计计算有效的全局优化RLT方法来解决广泛的一类可因子分解的非线性程序。为了有效地科普的大小和结构的松弛，通常产生的RLT，各种拉格朗日对偶/松弛，聚合，罚函数，信赖域，共轭/偏转次梯度法建议进行调查。这些想法提出了进一步探讨的背景下，各种具体的应用，包括雷达脉冲和位图问题，机器调度问题，两阶段随机混合整数问题，涉及整数追索权的决定，船舶设计问题，以及各种业务和战略规划的空中交通管理问题，在机场以及在航路空域。 离散和连续的非凸规划问题出现在许多实际操作，战略规划，系统或工程设计应用。 最近已经取得了一些进展，在解决这类问题的算法的发展。这些方法的核心是驱动求解过程的线性（或凸）规划松弛序列，这些算法的成功在很大程度上取决于这些松弛的强度或紧密度。本研究项目关注的是一个统一的解决方案的方法，即Reformulation-Linearization/Convexification Technique（RLT），已开发用于生成紧松弛不仅构建精确的解决方案算法，而且还设计强大的启发式程序的大类离散组合和连续非凸规划问题。 本项目中涉及的各种贡献涉及一般理论和算法概念的开发，以及几个重要应用的专门程序。本研究的影响将是开发一种综合技术，该技术统一了许多重要概念，并提供了对问题结构和建模策略的见解，并提供了一种用于产生紧密放松的结构。

This research project is concerned with a unifying solution approach, namely the Reformulation-Linearization/Convexification Technique (RLT), that has been developed for generating tight relaxations for large classes of discrete combinatorial and continuous nonconvex programming problems. The various contributions addressed in this project involve the development of both general theoretical and algorithmic concepts, as well as specialized procedures for several important applications, along with the investigation of related implementation issues accompanied by extensive computational tests. For linear mixed-integer 0-1 problems we explore the design of effective RLT relaxations, enhanced by conditional logic implications, and embedded within a dynamic Lagrangian relaxation constraint generation scheme. In the context of continuous nonconvex problems, we propose the study of various strategies for generating tight manageable relaxations for devising computationally effective global optimization RLT approaches to solve a wide class of factorable nonlinear programs. In order to effectively cope with the size and structure of the relaxations that are typically generated by RLT, various Lagrangian dual/relaxation, aggregation, penalty function, trust region, and conjugate/deflected subgradient methods are suggested for investigation. These ideas are proposed to be further explored in the context of a variety of specific applications including radar pulsing and bit-mapping problems, machine scheduling problems, two-stage stochastic mixed-integer problems involving integer recourse decisions, ship design problems, and various operational and strategic planning air traffic management problems faced at airports as well as in the enroute airspace. Discrete and continuous nonconvex programming problems arise in a host of practical operational, strategic planning, and system or engineering design applications. Several recent advances have been made in the development of algorithms for solving such classes of problems. At the heart of these approaches is a sequence of linear (or convex) programming relaxations that drive the solution process, and the success of such algorithms is strongly dependent on the strength or tightness of these relaxations. This research project is concerned with a unifying solution approach, namely the Reformulation-Linearization/Convexification Technique (RLT), that has been developed for generating tight relaxations for not only constructing exact solution algorithms, but also to design powerful heuristic procedures for large classes of discrete combinatorial and continuous nonconvex programming problems. The various contributions addressed in this project involve the development of both general theoretical and algorithmic concepts, as well as specialized procedures for several important applications.The impact of this study will be the development of a comprehensive technology that unifies many important concepts and offers insights into problem structures and modeling strategies, as well as provides a construct for generating tight relaxations.