【0基础运筹学】【SCIP论文】【3.1.2 Feasibility Pump（可行性泵）】Primal Heuristics for Mixed Integer Programs

Feasibility Pump（可行性泵）是一种启发式算法寻找MIP问题可行解的算法。

相关教程

• 【0基础运筹学】【SCIP论文】【3.1.1 Some Simple Divers】Primal Heuristics for Mixed Integer Programs
• 【0基础运筹学】【SCIP论文】【3.2.1 RENS】Primal Heuristics for Mixed Integer Programs
• 【0基础运筹学】【SCIP论文】【3.2.2 Some Other Rounding Methods】Primal Heuristics for Mixed Integer Programs

相关文献

• [1] Achterberg T . Constraint Integer Programming. Springer Berlin Heidelberg, 2007.
• [2] Berthold T . Primal Heuristics for Mixed Integer Programs[J]. master’s thesis technische universität, 2006.
• [3] Fischetti M , Glover F , Lodi A . The feasibility pump[J]. Mathematical Programming, 2005, 104(1):91-104.

前言

之前一直想跟大家分享一下【1】Achterberg T . Constraint Integer Programming. Springer Berlin Heidelberg, 2007.、【2】Berthold T . Primal Heuristics for Mixed Integer Programs[J]. master’s thesis technische universität, 2006.，这两篇SCIP官方文献，也全网搜了许多文档、视频、论文等。大部分教程抽象程度较高，需要具备大量的基础知识才能看明白，于是写一篇尽可能0基础上手的分享，希望能帮到也在从事相关行业的你。

2023新年FLAG：SCIP两篇文章分享更新计划完成！！！——@小猪快跑

从一个例子出发：

我们先看一个简单的MIP问题：

$\max 7x+y$
$s.t.$
$x\le 2$
$y\le 2$
$3x-y\le 4$
$4x+y\le 9$
$x+5y\le 11$
$x,y\in \mathbb{N}$

一般情况来说，求解MIP问题的松弛解（LP）会比原问题快很多，但松弛解通常是不可行的，这时候我们希望通过松弛解得到原问题的可行解。

原问题的LP问题：

$\max 7x+y$
$s.t.$
$x\le 2$
$y\le 2$
$6x-y\le 8$
$5x+2y\le 11$
$2x+9y\le 20$
$x,y\in \mathbb{R}，x,y\ge 0$

求解得到：

$x=1.86$
$y=1.57$

我们有一个大胆的猜测，就是原问题（MIP）的解和LP的解距离非常接近。其实这也是非常合理的猜测，如下图所示，我们只要向下平移$7x+y=12.65$，然后和可行域有整数解的交点就是MIP的可行解了，而越接近$7x+y=12.65$，目标 $\max 7x+y$ 值越大。

我们最直接的思想肯定是把点$X_0(x=1.86,y=1.57)$ 圆整（四舍五入）：$X_1(x=2,y=2)$ ，这时候点$X_1$离最优解很近，并且他是一个整数解（可能不可行）。我们从下图中发现点$X_1(x=2,y=2)$并不在可行域。

但我们能够发现如果在点$X_1$的$L_1$-范数距离<=1有$X_{1,left},X_{1,right},X_{1,up},X_{1,down}$四个整数点，其中$X_{1,left}$在可行域里。

于是我们大胆的猜测，在点$X_1$的$L_1$-范数距离很小的时候找到的可行解离最优解距离也很近。也就是说其实我们想找一个点，这个点离$X_1(x=2,y=2)$越接近越好，这个点还要在可行域内。于是我们有：

$\min \left|2-x\right|+\left|2-y\right|$
$s.t.$
$x\le 2$
$y\le 2$
$6x-y\le 8$
$5x+2y\le 11$
$2x+9y\le 20$
$x,y\in \mathbb{R}，x,y\ge 0$

因为$x\le 2$，$y\le 2$，所以目标 $\min \left|2-x\right|+\left|2-y\right|$可以把绝对值去掉。于是我们有：

$\min (2-x)+(2-y)$
$s.t.$
$x\le 2$
$y\le 2$
$6x-y\le 8$
$5x+2y\le 11$
$2x+9y\le 20$
$x,y\in \mathbb{R}，x,y\ge 0$

求解得到：

$x=1.44$
$y=1.90$

于是我们在图中标注$X_2(x=1.44,y=1.90)$，重复之前的步骤，直接圆整LP的解得到$X_3(x=1,y=2)$，我们很容易验证$X_3$在可行域内，他就是原问题（MIP）的一个可行解（在这个问题中刚好也是最优解）。

预备知识

定义： R ^ : = R ∪ { ± ∞ } \hat{\mathbb{R}}:=\mathbb{R}\cup\{\pm\infty\} R^:=R∪{±∞}
定义1.1 m , n ∈ R , A ∈ R m × n , b ∈ R m , c ∈ R n , l , u ∈ R ^ , I ⊆ N = { 1 , ⋅ ⋅ ⋅ , n } m,\,n\,\in\,\mathbb{R},\ A\in\ \mathbb{R}^{m\times n},\ b\in\ \mathbb{R}^{m},\ c\in\mathbb{R}^{n},\ l,\,u\in\hat{\mathbb{R}}\ ,{I}\subseteq{\cal N}=\{1,\cdot\cdot\cdot,n\} m,n∈R, A∈ Rm×n, b∈ Rm, c∈Rn, l,u∈R^ ,I⊆N={1,⋅⋅⋅,n}
$$\begin{array}{rll}\min & c^{T}x& \\ suchthat& Ax\le b& \\ & l\le x\le u& \\ & x_j\in \mathbb{Z}& forallj\in I\end{array}$$ 我们称这是一个混合整数规划（mixed integer program (MIP)）。

定义1.2 给定MIP如定义1.1所示，我们称：
$$\begin{array}{rll}a\mathrm{linear}\mathrm{program}(\mathrm{LP})& if& I=\varnothing \\ an\mathrm{integer}\mathrm{program}(\mathrm{IP})& if& I=N\\ a\mathrm{binary}\mathrm{program}(\mathrm{BP})& if& B=I=N,and\\ a\mathrm{mixed}\mathrm{binary}\mathrm{program}(\mathrm{MBP})& if& B=I.\end{array}$$ 其中 B : = { j ∈ I ∣ l j = 0 , u j = 1 } B:=\{j\in I\mid l_{j}=0,u_{j}=1\} B:={j∈I∣lj​=0,uj​=1}

定义1.3 给定MIP如定义1.1所示，我们称：
$$\begin{array}{rll}\mathrm{LP}-\mathrm{feasible}for(1.1)& if& A\hat{x}\le bandl\le \hat{x}\le u,\\ \mathrm{integer}\mathrm{feasible}for(1.1)& if& {\hat{x}}_j\in \mathbb{Z}forallj\in I,\\ a\mathrm{feasible}\mathrm{solution}for(1.1)& if& \hat{x}isLP-feasibleandintegerfeasible,and\\ an\mathrm{optimal}\mathrm{solution}for(1.1)& if& \hat{x}isafeasiblesolutionand{c}^T\hat{x}\le c^{T}x\\ & & forallotherfeasiblesolutionsx.\end{array}$$ 如果给定一个MIP，通过省略整数约束（$x_j\in \mathbb{Z}\mathrm{for}\mathrm{all}j\in I$）而产生的LP被称为MIP的LP松弛（LP-relaxation）。 P ( A , b , l , u ) : = { x ∈ R n ∣ A x ≤ b , l ≤ x ≤ u } P(A,b,l,u):=\{x\in\mathbb{R}^{n}\mid A x\leq b,l\leq x\leq u\} P(A,b,l,u):={x∈Rn∣Ax≤b,l≤x≤u}被称为MIP的LP多面体（LP-polyhedron）。

Feasibility Pump（可行性泵）

Feasibility Pump

定义3.2 $S\subseteq N$， $x\in {\mathbb{R}}^n$
$$[x{]}_j^S:=\{\begin{array}{ll}\lfloor x_j+0.5\rfloor & ifj\in S\\ x_j& ifj\notin S.\end{array}$$ 【友情提示】：$[x{]}_j^S$ 相当于指标$j$在$S$里的话，$x_j$进行四舍五入。

$${\Delta }^S(x,y):=\sum _{j\in S}|x_j-y_j|$$ 【友情提示】：${\Delta }^S(x,y)$ 相当于指标$j$在$S$里的话，$x$和$y$的$L_1-distance$。

$$f^S(x):=\sum _{j\in S}f(x_j)withf(x_j):=|x_j-\lfloor x_j+0.5\rfloor |$$ 【友情提示】：$f^S(x)$相当于对于指标$j$在$S$里的话，向量$x\in {\mathbb{R}}^n$的分数部分（离最近整数的距离）绝对值求和。

流程图

流程细节

1. 求原问题的LP松弛解，记为$\bar{x}$。
2. $\bar{x}$中本应是整数变量但可能存在小数的情况，于是我们四舍五入：$\tilde{x}\leftarrow [\bar{x}{]}^S$
3. 这时候$\tilde{x}$可能不可行，根据上面举得例子我们猜测：原问题（MIP）的解和LP的解距离非常接近。于是乎我们跟上面例子一样，希望找一个点$\bar{x}$满足：$\tilde{x}$ 的 $L_1-$ 范数距离很小时候的LP可行解。
   x ˉ : = arg min ⁡ { Δ S ( x , x ~ ) ∣ x ∈ P ( A , b , l , u ) } \bar{x}:=\argmin\{\Delta^{S}(x,\tilde{x})\mid x\in P(A,b,l,u)\} xˉ:=argmin{ΔS(x,x~)∣x∈P(A,b,l,u)} 也就是说，我们只需要求解如下LP问题：
   $$\begin{gathered} \min \sum _{j\in S:{\tilde{x}}_j=l_j}(x_j-l_j)+\sum _{j\in S:{\tilde{x}}_j=u_j}(u_j-x_j)+\sum _{j\in S,l_j<{\tilde{x}}_j<u_j}{d}_j \\ \begin{array}{lr}\mathrm{such}\mathrm{that}& Ax\le b\\ & x-\tilde{x}\le d\\ & \tilde{x}-x\le d\\ & l\le x\le u\end{array} \end{gathered}$$ 这里我们希望 $x$ 和 $\tilde{x}$ 的 $L_1-$ 范数距离小：$|x-\tilde{x}|\le d\iff \{\begin{array}{r}x-\tilde{x}\le d\\ \tilde{x}-x\le d\end{array}$ ，所以我们有了上面的约束。（注：如果$S=B$，则不需要创建变量$d_j$）
4. 重复步骤2和3，迭代直到 $\bar{x}=\tilde{x}$ ，也就是得到一个MILP可行解。

Feasibility Pump算法思想主要利用了定义1.3：a feasible solution if $\hat{x}$ is LP-feasible and integer feasible 。LP-feasible通过求解松弛问题（LP）即可，integer feasible取整即可。从几何学的角度来看，FP（Feasibility Pump）产生了两个点 $\bar{x}$ 和 $\tilde{x}$ 的轨迹（希望是收敛的），它们以互补的方式满足部分的可行性，一个满足线性约束，另一个满足整数要求。该方法引导 $\bar{x}$ 走向可行性的一个重要特征：我们在每个pumping cycle（指的是步骤2和3）计算 $\bar{x}$ 与多面体P的 $L_1-$ 范数距离 $(x,\tilde{x})$，而不是像MIP启发式方法中惯用的那样，对单个线性约束的违反程度进行加权组合（instead of taking a weighted combination of the degree of violation of the single linear constraints）（这句博主目前也不是特别理解）。这个距离可以解释为 $\bar{x}$ 和 $(x,\tilde{x})$ 的 “压力差”，我们试图通过将 $\bar{x}$ 的整体性 "泵入 " $(x,\tilde{x})$ 来减少这种压力——这就是方法名称的由来。FP可以被解释为一种产生四舍五入序列的算法，从而生成可行的MIP点。FP也可以被看作是修正的local branching策略。事实上，在每个pumping cycle，我们都有一个满足整数要求的（可能不可行）的解决方案 $\bar{x}$，我们面临的问题是在一个小距离的邻域内找到一个可行的解决方案（如果存在的话），即只改变其变量的一个小子集。在 local branching 的背景下，这个子问题的模型是MIP： min ⁡ { c T x : A x ≥ b , Δ S ( x , x ~ ) ≤ k } \min\{c^{T}x:A x\geq b,\ \Delta^{S}(x,\tilde{x})\leq k\} min{cTx:Ax≥b, ΔS(x,x~)≤k}，其中 $k$ 是一个合适的值。在FP背景下，相同的子问题通过一种宽松的方式建模就是步骤3中的模型，其中 "小距离 "的要求被转化为目标函数的条件。

The Objective Feasibility Pump

计算结果表明，Feasibility Pump在寻找MIP的可行解是非常成功的。不幸的是，解的质量有时是相当差的。这可以从这样的观察中得到解释：MIP的原始目标函数 $c$ 只用到过一次，即当第一个LP可行点 $\bar{x}$ 被确定为LP-relaxation的最优解时。Achterberg和Berthold提供了一个修改版的Feasibility Pump，称为 Objective Feasibility Pump，它比原Feasibility Pump更多地考虑了目标函数。Objective Feasibility Pump在第一次迭代后并不完全忽略目标函数c，而是在每个迭代步骤中减少其影响。因此，它的运行时间越长，就越趋向于可行性，越趋向于最优性。如果不存在适当的原始目标函数，即 $c=0$，我们将只使用Feasibility Pump的原始版本。为了避免一些技术上的困难，我们假设 $c\ne 0$。这里我们考虑用 ${\Delta }^S(\cdot ,\bar{x})$ 和 $c$ 的凸组合（convex combination）替换 ${\Delta }^S(\cdot ,\bar{x})$。

定义3.3 L e t x ~ ∈ R n , S ⊆ N , c ∈ R n \ { 0 } , a n d α ∈ [ 0 , 1 ] . L e t\ \tilde{x}\in\mathbb{R}^{n},\ S\subseteq N,\ c\in\mathbb{R}^{n}\backslash\{0\},\ a n d\,\alpha\in[0,1]. Let x~∈Rn, S⊆N, c∈Rn\{0}, andα∈[0,1].
$${\Delta }_{\alpha }^S(x,\tilde{x}):=(1-\alpha ){\Delta }^S(x,\tilde{x})+\alpha \frac{\sqrt{|S|}}{\Vert c\Vert }{c}^{T}x$$ 【友情提示】：$||\cdot ||$是Euclidean范数，即$||x|{|}_2=\sqrt{{\sum }_i{x}_i^2}$。
【友情提示】：$\sqrt{|S|}$ 是 Feasibility Pump 原始版本的Euclidean范数，这里我们把 ${\Delta }^S(\cdot ,\bar{x})$ 看成一种距离的定义，那么其Euclidean范数即
$$\sqrt{|S|}=\sqrt{\sum _{j\in S:{\tilde{x}}_j=l_j}(x_j-l_j{)}^2+\sum _{j\in S:{\tilde{x}}_j=u_j}(u_j-x_j{)}^2+\sum _{j\in S,l_j<{\tilde{x}}_j<u_j}{d}_j^2}$$。
【友情提示】：${\alpha }_{t+1}=\phi {\alpha }_t,\phi \in [0,1),{\alpha }_0\in [0,1].$

Dealing with Cycles

在Feasibility Pump的两个变体中都出现了一个主要问题：如果取整后的点 $\tilde{x}$，而这个点在之前的迭代中已经被访问过，那么该怎么办？处理这种方式的紧迫性在两个版本中都不一样。对于最初的Feasibility Pump来说，返回到一个已经被访问过的点意味着陷入一个循环。Feasibility Pump会找到完全相同的最接近的点 $\bar{x}$，会像之前的迭代一样把它四舍五入到相同的整数可行点，因此，会一次又一次地得到整个点的序列。因此，Fischetti, Glover和Lodi建议进行重启操作。
重启会进行随机扰动，将最后一个LP可行解 $\bar{x}$ 的一些变量值随机地向上或向下移动，而不是像通常那样四舍五入。如果有一个长度为1的循环，这意味着你立即转回前一次迭代的舍入点 $\tilde{x}$，你将跳过随机选择，而只是把一定数量的比如说最小 $T$ 个变量舍入到另一边。
Objective Feasibility Pump在不同的迭代步骤 $t$ 和 $t^{\prime }$ 中使用不同的参数 ${\alpha }_t$ 和 ${\alpha }_{t^{\prime }}$。由于不同的目标函数 ${\alpha }_t$ 和 ${\alpha }_{t^{\prime }}$，有可能到达一个新的LP可行点 $\bar{x}$ ，即使已经访问过 $\tilde{x}$，也不会遇到循环。这一事件的概率显然取决于两个函数 ${\alpha }_t$ 和 ${\alpha }_{t^{\prime }}$的差异程度，而这本身又取决于 ${\alpha }_t$ 和 ${\alpha }_{t^{\prime }}$的差异程度。只有在迭代 $t^{\prime }<t$ 时已经访问过点 $\tilde{x}$，且 ${\alpha }_{t^{\prime }}-{\alpha }_t\le {\delta }_{\alpha }$，其中 ${\delta }_{\alpha }\in (0,1]$ 是一个固定的参数值，Objective Feasibility Pump才会在迭代 $t$ 时执行重新启动。

伪代码