割平面法是数学优化中的一类算法,通过不断添加称为割的线性不等式,逐步改进对原问题的近似。每个割都会排除当前近似中的一部分,同时不排除任何必须保留的解。在整数规划中,割通常用于剔除连续松弛中的分数解,同时保留所有可行整数解。在凸优化中,割可以将不可行点与可行域分离,也可以给出目标函数的仿射下界。
这一术语指的是一种算法框架,而非某个单一算法。其效果取决于如何生成割、如何选择下一个候选解,以及如何管理累积的不等式。
几何原理
线性不等式
定义了一个半空间,其边界是超平面 。设原问题的可行集为 ,而一个较简单的集合 包含它:
如果候选点 不符合要求,割平面算法就寻找一个满足下列条件的不等式:
下一个近似为
因此,这个割保留了 ,却排除了当前候选点。
如果保留已生成的割,各次近似便构成嵌套序列:
如果这些近似由有限个线性不等式定义,那么它们就是多面体。
一个基本区别在于:有效不等式在整个目标集合上都成立,而分离割除此之外还会排除当前考察的点。当前点已经满足的有效不等式可能在之后发挥作用,但此时并不能将该点分离出去。
一般算法
典型的基于优化的割平面过程具有以下结构:
- 构造松弛问题。 用一个更简单的问题替代原问题,使其可行域包含原问题的可行集。
- 求解当前松弛问题。 得到一个候选解,以及原问题最优值的一个界。
- 检验候选解。 判断它是否满足被省略的要求,或者当前近似是否已经足够精确。
- 生成割。 添加一个或多个被候选解违反的不等式。
- 重复。 在确认最优性、不可行性或达到规定精度后停止。
当前的松弛问题通常称为主问题。它往往是一个线性规划问题,但也可能是二次规划、锥规划或其他形式的主问题。
对于最小化问题,有效的松弛会给出最优值的下界,而任意可行解都会给出上界。两者之差可用作停止准则。对于最大化问题,上下界的角色则相反。
并非所有割平面算法都通过优化主问题来选择下一个点。定位类方法会从已知包含某个解的区域中选取一个代表点,再利用新信息缩小该区域。
整数规划中的割平面
考虑整数线性规划
其线性规划松弛将 替换为 。松弛问题通常更容易求解,但其最优解可能含有非整数分量。
令
对 有效的每个线性不等式,对其凸包 也有效。因此,整数规划中的割可以理解为对整数凸包近似的逐步改进。
如果松弛精确描述了整数凸包,而且能够取得有限最优值,那么它就存在整数最优解。然而,显式描述这个凸包可能需要数量极其庞大的不等式。割平面法会按需生成选定的不等式,而不是预先构造完整的描述。
一个简单例子
考虑
连续松弛的最优值为 。将其约束除以二,得到
由于左端在每个整数可行点处都是整数,这个不等式可以加强为
加强后的不等式排除了所有目标值为 的松弛最优解,同时保留了每个可行整数点。因此,整数问题的最优值为 。
这一加强后的不等式对原来的连续区域并不有效:它成立的依据是整数性。
Chvátal–Gomory 割
Chvátal–Gomory 割推广了上述舍入思路。对于纯整数系统 ,选取非负乘子 ,使 的系数均为整数。于是,每个可行整数点都满足
非负线性组合保持了有效性,而由于左端的取值为整数,可以将右端向下取整。
反复施加多轮此类割,可以逐步加强松弛。对于有理多面体,原则上经过有限轮即可得到整数凸包。不过,这里的一轮在概念上是施加该类型的所有割;这一结果并不保证任意逐个添加割的策略都能迅速终止。
Gomory 分数割
经典的 Gomory 分数割由纯整数问题的单纯形表中的一行推导而来。设该行为
其中列出的所有变量都被约束为非负整数。记
如果 不是整数,对应的割为
在当前基本解处,非基变量 均为零,因此该不等式被违反。其有效性可由单纯形表中的等式和变量的整数性推出。
当部分变量为连续变量时,不能原样套用这个公式。混合整数问题所使用的割,必须考虑哪些变量需要取整数。
凸优化中的割平面
割平面法也利用了凸函数的支撑几何性质。
对于凸函数 ,其在 处的一个次梯度 在整个定义域上满足
。如果 可微,其梯度就是一个次梯度。
这个不等式给出了一个全局仿射下界。将这些下界累积起来,可得到分段线性模型
且有 。
Kelley 割平面法
对于
其中 是凸集,Kelley 方法通过求解下列问题来选择新的候选点:
当 是多面体时,这是一个线性规划问题。为了使主问题适定,需要选用合适的初始定义域或其他界定结构。
主问题的最优值给出真实最小值的下界。已计算的可行目标值中的最佳值则给出上界。两者之间的间隙可以用来确认近似最优性。
虽然这些割给出的是函数的下界,但它们构成的是函数上图的外近似;上图是满足 的点对 所组成的集合。
凸约束的割
设有约束
其中 为凸函数。如果 ,且 是 处的一个次梯度,那么每个可行点都满足
这个不等式排除了当前不可行点,同时保留了该约束的可行域。
凸性是上述论证成立的关键。非凸函数的切线近似不一定是全局下界,可能会错误地排除可行解或最优解。
分离与计算复杂度
分离预言机接收一个候选点,要么确认该点属于目标凸集,要么返回一个分离不等式。这使得割平面算法能够处理约束数量过多、无法显式列出的集合。
例如,旅行商问题的某些模型包含指数数量的子回路消除不等式。求解器可以只从其中一部分不等式开始,在不断生成解的过程中寻找被违反的不等式。
椭球法确立了分离与优化之间的重要联系。在适当的编码、有界性和精度假设下,可以利用高效的分离过程,实现凸集上的高效优化。相关的多项式时间结果,并不意味着每种实际的割平面实现都具有多项式时间复杂度,也不意味着对每一类有用的割都容易求解分离问题。
寻找一个被违反的强不等式,本身就可能是一个困难的优化问题。因此,实际算法往往将精确分离过程与启发式搜索相结合。
相关方法与实用变体
分支切割法
现代混合整数求解器通常将割平面与分支定界法结合,形成分支切割法。
割用于加强松弛、改善界;分支则将搜索划分为若干子问题。这两种机制相辅相成:割可能避免大量分支,而当割的生成停滞时,分支可以继续推动求解。
全局割在原问题的整个可行集上都有效。局部割可能依赖于搜索树某个节点所施加的限制,因此仅在对应的子树内有效。混淆这些有效范围,可能使优化结果失效。
本德斯分解
本德斯分解将问题分为主问题和子问题。在满足相应线性或凸性假设的条件下,利用子问题的信息,可以在主变量空间中生成可行性割或最优性割。
如果固定一组变量后,剩余优化问题会显著简化,这种方法就很有用;许多规划模型和基于情景的模型都具有这种特点。
稳定化方法与束方法
未经稳定化的凸割平面法可能在相距很远的点之间来回跳动,因为累积形成的下界模型在这些位置过于乐观。束方法保留次梯度信息,同时加入稳定化机制,通常通过近端项或信赖域来实现。
这类方法保留了利用支撑不等式构建模型的核心思想,同时控制新计算点的选择。
历史
割平面的思想沿着几条相互关联的路线发展而来。20 世纪 50 年代,乔治·丹齐格、雷·富尔克森和塞尔默·约翰逊对旅行商问题的研究,展示了如何利用针对特定问题的不等式来加强线性规划模型。
拉尔夫·戈莫里于 1958 年提出了适用于整数规划的一般割平面过程。小 J. E. 凯利于 1960 年提出的方法将逐次构造支撑超平面的思想应用于凸优化。雅克·本德斯于 1962 年提出的分解方法,则为从子问题生成割提供了另一个影响深远的框架。
后续的发展将通用割、针对特定问题的分离方法、分解和搜索结合起来。这种组合成为大规模混合整数优化的核心。
局限性与实现问题
仅仅保证割有效,并不能确保它在计算中有用。需要考虑的重要因素包括:
- 强度。 一个割可能排除了当前点,却只使目标值的界得到轻微改善。
- 生成成本。 搜索强割的开销,可能超过后续改进所节省的成本。
- 主问题规模增长。 累积大量不等式会增加内存占用和求解时间。
- 冗余。 相似的割可能增加大量计算工作,却几乎不能进一步收紧松弛。
- 数值条件。 系数过大或尺度不佳,可能给浮点运算带来问题。
- 收敛假设。 有限终止或收敛是否成立,取决于问题类别、选择规则、算术模型和其他算法细节。
因此,实际实现会对割进行筛选、缩放、老化管理,有时还会删除割。如果删除了割,逐次得到的松弛就不一定仍然嵌套;除非单独保留先前有效的界,否则其界也不一定单调改善。
还应区分特定精确算术过程的理论有限收敛结果,与采用数值容差时的实际表现。一个点可能在求解器容差范围内被视为可行,却仍以很小的幅度违反某个数学不等式。可靠的实现必须妥善处理这些容差,不能将无效不等式当作合法的割。