Reformulation-linearization-based global optimization methods

简介：
该文献对一类全局优化问题中的关键方法进行了阐述——重新配方-线性化方法。该方法的主要特点是通过构建一系列紧致的线性规划松弛问题来求解原问题，其中每一步骤都依赖于这些松弛的强度或紧致度与算法的成功率直接相关。作为实现这一目标的技术手段，重组-线性化技术（Reformulation-Linearization Technique,简称RLT）不仅能够构建精确解策略，而且还被用来开发解决大量离散组合优化和非凸规划问题的高效启发式算法。 重新配方-线性化方法的起源可追溯至几位早期研究者的开创性工作，这些研究主要聚焦于处理0-1变量、混合0-1线性和多项式规划问题。随后，该方法被扩展到更为复杂的连续非凸多项式规划领域。对于涉及混合0-1线性或多项式的规划问题，RLT方法通过构建n层结构，系统地生成了可行解集合凸包的显式代数特征。整个过程可分为两个关键阶段：首先是重新配方步骤，在此过程中，研究者通过对原始模型进行巧妙修改以降低复杂度；其次是线性化处理阶段，经过前述修改后的问题被转化为一个纯粹的线性规划形式。该方法凭借所生成的更紧密松弛而取得显著成效。这些松弛效果主要通过将原问题转化为等价的线性规划模型来实现。其优势体现在成熟的求解算法体系上，尤其是包括经典的单纯形法与内点法等高效求解器在大规模场景下的应用表现。这些松弛结果不仅适用于精确求解方法，同时也为构造高效的启发式搜索策略提供了良好的基础。RLT技术在混合整数0-1规划问题、多项式规划问题、非凸规划问题、可分解规划问题以及连续非凸多项式规划问题等几类关键领域上展现出显著的效果。同时也能处理连续问题的建模与求解，通过附加一些关键有效的约束条件（key valid constraints），RLT技术能够更精确地逼近原问题中复杂且难以界定的可能性空间。这些新增的关键约束条件有助于更准确地界定原问题中非线性和非凸区域的可能性空间。对于连续型非凸规划问题，RLT方法主要依据一系列线性（或凸）规划松弛来近似求解原问题，而这些松弛的质量直接决定了算法的效率。类同方式下，离散问题同样能够生成优质松弛方案，使得复杂难以精确求解的组合优化问题得以通过松弛转化为线性规划或凸规划形式，并可利用现有高效算法进行有效解决。 该技术在解决混合整数线性和非线性规划问题以及连续非凸规划问题中的外逼近方法方面发挥了重要作用。这些领域是分支定界算法的重要应用方向之一。 一种系统地探索搜索空间的方法，分支定界算法旨在找到优化问题的最优解。其通过分阶段细化搜索空间来寻找最优解，并利用有效的界来进行剪枝操作以减少计算负担。 该技术为这种方法提供了更加紧凑的下界，从而提高了分支定界算法的效率。 简单而言，重新配方-线性化方法基于线性和凸规划理论和技术体系地解决了离散与连续型非凸规划问题中的关键挑战，形成了一个强有力的解决方案框架。这种技术在多个领域展现出广泛的适用性，包括生产计划与控制、位置分配、资源优化、经济学分析及博弈论研究、量子化学问题以及工程设计等多个方面。这些方法不仅对学术理论研究具有重要意义，在实际应用中解决优化难题也显示出显著的实用价值和前景。