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

这项研究项目涉及一种统一的求解方法，即重构线性化/凸化技术(RLT)，它是为产生大类离散组合和连续非凸规划问题的紧松弛而发展起来的。该项目涉及的各种贡献包括发展一般理论和算法概念，以及几个重要应用的专门程序，以及调查相关的实施问题，并伴随着广泛的计算测试。对于线性混合整数0-1问题，我们探索了有效的RLT松弛的设计，通过条件逻辑蕴涵增强，并嵌入动态拉格朗日松弛约束生成方案。在连续非凸问题的背景下，我们提出了产生紧的可管理松弛的各种策略的研究，以设计计算上有效的全局优化RLT方法来求解一大类可分解的非线性规划。为了有效地处理由RLT产生的松弛的大小和结构，提出了各种拉格朗日对偶/松弛、聚集、罚函数、信赖域和共轭/偏转次梯度方法。这些想法建议在各种具体应用的背景下进一步探索，包括雷达脉冲和位映射问题，机器调度问题，涉及整数资源决策的两阶段随机混合整数问题，船舶设计问题，以及机场和航线空域面临的各种运营和战略规划空中交通管理问题。离散和连续的非凸规划问题出现在许多实际的运营、战略规划和系统或工程设计应用中。最近在解决这类问题的算法的开发方面取得了一些进展。这些方法的核心是驱动求解过程的一系列线性(或凸)规划松弛，而此类算法的成功很大程度上依赖于这些松弛的强度或紧密性。这项研究项目涉及一种统一的求解方法，即重构-线性化/凸化技术(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.