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

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