切除平面法2024介紹!(持續更新)

切割可以被加入到被松弛的线性规划中,使得当前的非整数解对松弛不再可行。 切割平面法由 Ralph Gomory 在 20世纪 50 年代提出,用于解决整数规划和混合整数规划问题。 然而,当时的大多数专家,包括 Gomory 自己都认为由于数值上的不稳定性,这种方法没有实际运用价值;同时由于求解过程中需要进行过多轮的切割,该方法可能是无效的。

现在,所有的商用 MILP 求解器都或多或少地使用了 Gomory 切割。 Gomory 切割可通过单一单纯形表格生成,相比于其他计算成本高昂、甚至分离为 NP-困难的其他切割法来说十分高效。 在其他 MILP 的普遍切割法中,提升和投影割平面法明显优于 Gomory 切割。 在求解相应的线性规划时,首先要将原问题的数学模型进行标准化。 这里的“标准化”有两个含义:第一是将所有的不等式约束全部转化成等式约束,这是因为要采用单纯形表进行计算的缘故。 第二是将整数规划中所有非整数系数全部转换成整数,这是出于构造“切割不等式”的需要。

切除平面法: 切除平面法

这个新增加的约束条件的作用就是去切割相应松弛问题的可行域,即割去松弛问题的部分非整数解(包括原已得到的非整数最优解). 而把所有的整数解都保留下来,故称新增加的约束条件为割平面. 当经过多次切割后,就会使被切割后保留下来的可行域上有一个坐标均为整数的顶点,它恰好就是所求问题的整数最优解. 即切割后所对应的松弛问题,与原整数规划问题具有相同的最优解。

切除平面法

混合整数线性规划(MILP)的割平面法通过将整数问题线性松弛为非整数线性问题,并对其进行求解,来求解 MILP 问题。 线性规划理论说明,在温和的假定下(如果线性规划存在最优解,并且可行域不包含一条线),总存在一个极值点或顶点是最优的。 如否,则必然存在一线性不等式将最优点和真可行集的凸包分离。 找到这样的不等式是分离问题,而这样的不等式就是切割。

切除平面法: 절제 평면법 切除平面法 :

对于这类问题,通常的可微优化的梯度法无法使用,而使用这些方法可以高效地得到凸目标函数及其次梯度。 这种情况最常出现在双拉格朗日函数的凹优化中。 另一种常见情形是 Dantzig-Wolfe分解应用于结构优化问题中,这类问题通常有含有指数级变量的表达式。

  • 第二是将整数规划中所有非整数系数全部转换成整数,这是出于构造“切割不等式”的需要。
  • 否则,就增加一个新的约束条件,称为割平面。
  • 即切割后所对应的松弛问题,与原整数规划问题具有相同的最优解。
  • 这个新增加的约束条件的作用就是去切割相应松弛问题的可行域,即割去松弛问题的部分非整数解(包括原已得到的非整数最优解).
  • 这里的“标准化”有两个含义:第一是将所有的不等式约束全部转化成等式约束,这是因为要采用单纯形表进行计算的缘故。

基本思路是:先不考虑整数性约束,求解相应的线性规划问题。 若线性规划问题的最优解恰好是整数解,则此解即为整数规划问题的最优解。 切除平面法 切除平面法 否则,就增加一个新的约束条件,称为割平面。 用割平面法求解整数规划的基本思路是:先不考虑整数约束条件,求松弛问题的最优解,如果获得整数最优解,即为所求,运算停止. 切除平面法 如果所得到最优解不满足整数约束条件,则在此非整数解的基础上增加新的约束条件重新求解.

切除平面法: 割平面法Gomory 切割

先不考虑变量的取整约束,用单纯形法求解相应的线性规划问题,如果该问题没有可行解或最优解已是整数则停止,否则转下步。 求一个“切割不等式”及添加到整数规划的约束条件中去,即对上述线性规划问题的可行域进行“切割”,然后返回步骤1。 其基本原理是通过封闭半空间的有限集估算非线性(凸)问题的可行域,并对一系列的线性问题估算进行求解。 用于普遍的凸连续优化和变体的割平面法有不同的名称: Kelley 法, Kelley-Cheney-Goldstein 法和捆绑法。

  • 当经过多次切割后,就会使被切割后保留下来的可行域上有一个坐标均为整数的顶点,它恰好就是所求问题的整数最优解.
  • 如果所得到最优解不满足整数约束条件,则在此非整数解的基础上增加新的约束条件重新求解.
  • 先不考虑变量的取整约束,用单纯形法求解相应的线性规划问题,如果该问题没有可行解或最优解已是整数则停止,否则转下步。
  • 基本思路是:先不考虑整数性约束,求解相应的线性规划问题。
  • 在求解相应的线性规划时,首先要将原问题的数学模型进行标准化。
  • 线性规划理论说明,在温和的假定下(如果线性规划存在最优解,并且可行域不包含一条线),总存在一个极值点或顶点是最优的。
  • 求一个“切割不等式”及添加到整数规划的约束条件中去,即对上述线性规划问题的可行域进行“切割”,然后返回步骤1。

通过延迟列生成法按需生成这些变量等同于在对应的对偶问题上切割平面。

切除平面法: 割平面法Gomory 切割

为整数的约束进行松弛,并求解相应的线性规划问题,得出基本可行解。 在几何层面上,该解为含有所有可行解的凸多胞形的一个顶点。 如果该顶点不是整数点,则该方法将凸多胞形分为两部分,一部分含有该顶点的超平面,另一部分含有所有整数解。 切除平面法 该超平面随即作为额外的线性约束加入到问题中,构成修正的线性问题,以排除前一步发现的顶点。 随后求解新的线性问题,重复这一过程,直到发现整数解。

切除平面法