Bc7e36c96501581928f50952eb2f8a4f
AutoLayout 中的线性规划 - Simplex 算法

本文验证代码可以从 这个链接 中获取

前一段时间由于跳槽,博客停更了大概有 150 天左右的样子。在所有事情都安置好后,决定推掉之前写过的半截文章,开始更这么一个 Topic。自己没有阅读 paper 的习惯,这也是一次对自己的挑战。

本文与 iOS 关系不大,多半偏向 paper 的学习和算法介绍,请读者根据兴趣自行阅读。

温习线性规划

当我们在 Storyboard 上建立完一堆约束后,发现其实所有的约束都可以用多个约束间的不等式关系来描述。于是乎将 UI 的布局问题,就转化成了一个线性规划问题

如何求解这个线性规划问题呢?我们引入一个求解线性规划的经典方法 - Simplex 算法。虽然该算法具有指数时间的复杂度,但是在绝大多数情况下仍旧会保持着多项式时间复杂度,关于复杂度分析我们在后文具体分析。

Simplex 算法

Simplex 算法主要有三个步骤:

  1. 找到一个初始的基本可行解;
  2. 持续进行旋转(Pivot)操作;
  3. 重复操作 2,直到找到最优解;

Simplex 算法我以下面一个线性规划方程为例:

$$
\begin{cases}
\ -x_1-14x_2-6x_3 \quad min\\
\ x_1+x_2+x_3+x_4=4&\\
\ x_1\leq2\\
\ x_3\leq3\\
\ 3x_2+x_3\leq6\\
\ x_1,x_2,x_3\geq0
\end{cases}
$$

改写成松弛形式

$$
\begin{cases}
\ -x_1-14x_2-6x_3 \quad min\\
\ x_1+x_2+x_3+x_4=4 \\
\ x_1+x_5=2 \\
\ x_3+x_6=3 \\
\ 3x_2+x_3+x_7=6 \\
\ x_1, x_2, x_3, x_4, x_5, x_6, x_7 \geq 0
\end{cases}
$$

将增加的松弛量放到等号左边,得到基本变量非基本变量关系式:

$$
\begin{cases}
\ \beta=-x_1-14x_2-6x_3 \\
\ x_4=4-x_1-x_2-x_3 \\
\ x_5=2-x_1 \\
\ x_6=3-x_3 \\
\ x_7=6-3x_2-x_3
\end{cases}
$$

将右边所有非常量都设为 0,然后左边基本变量的值求得:

$$
(x_1,x_2,...,x_7)=(0,0,0,4,2,3,6)
$$

此时目标值 $\beta=0$。求出基本可行解后,我们开始对其做旋转操作。每次旋转,我们选择目标函数中带有负常数项进行放大操作,此时选定 $x_1$。将 $x_1=2-x_5$ 带入非基本变量:

$$
\begin{cases}
\ \beta=-2-14x_2-6x_3+x_5 \\
\ x_4=2-x_2-x_3+x_5 \\
\ x_5 = 2-x_1 \\
\ x_6 = 3-x_3 \\
\ x_7 = 6-3x_2-x_3
\end{cases}
$$

每次旋转过程,一次旋转选取一个非基本变量,这里称作替入变量 $x_e$ 和一个替出变量 $x_i$,然后带入变量。此时继续将所有非常量为设为 0,得到:

$$
(x_1,x_2,...,x_7)=(2,0,0,2,0,3,6) \\
\beta = -2
$$

此时我们发现目标值减少了 -2。继续旋转,这次我们选择 $x_2$,通过式 ② 得到 $x_2=2-x_3-x_4+x_5$ 带入得到:

$$
\begin{cases}
\ \beta = -30-\frac{2}{3}x_3+x_4+\frac{13}{3}x_7 \\
\ x_2=2-\frac{1}{3}x_3-\frac{1}{3}x_7 \\
\ x_1=2-\frac{2}{3}x_3-x_4+\frac{1}{3}x_7 \\
\ x_6=3-x_3 \\
\ x_5=\frac{2}{3}x_3+x_4-\frac{1}{3}x_7
\end{cases}
$$

求出解和目标值为:

$$
(x_1,x_2,...,x_7)=(2,2,0,0,0,3,0) \\
\beta=-2
$$

发现其目标值并没有提升,之后我们做最后一次旋转,选择 $x_3$,通过式 ② 得到 $x_3=3-\frac{3}{2}x_1-\frac{3}{2}x_4-\frac{1}{2}x_7$,然后分别带入:

$$
\begin{cases}
\ \beta = -32+x_1+2x_4+4x_7 \\
\ x_2=1+\frac{1}{2}x_1+\frac{1}{2}x_4-\frac{1}{2}x_7 \\
\ x_3=3-\frac{3}{2}x_1-\frac{3}{2}x_4+\frac{1}{2}x_7 \\
\ x_6=\frac{3}{2}x_1+\frac{3}{2}x_4-\frac{1}{2}x_7 \\
\ x_5=2-x_1
\end{cases}
$$

现在目标函数中没有可以增大的项了,停止选装。所以 $\beta=-32$ 是我们最终的目标解。此时基本解为 $(x_1,x_2,...,x_7)=(0,1,3,0,2,0,0)$。

可是往往事情并不想这次的计算那么顺利,有的时候我们发现旋转操作一直无法将目标值继续扩大或缩小,也就是之前计算中的倒数第二次选装操作。这种现象叫做退化(Degeneracy)。有的时候退化现象还会产生旋转循环(cycling),从而一直无法到最终的旋转状态。产生循环的原因在《算法导论》中有解释:

Degeneracy can prevent the simplex algorithm from terminating, because it can lead to a phenomenon known as cycling: the slack forms at two different iterations of SIMPLEX are identical. Because of degeneracy, SIMPLEX could choose a sequence of pivot operations that leave the objective value unchanged but repeat a slack form within the sequence. Since SIMPLEX is a deterministic algorithm, if it cycles, then it will cycle through the same series of slack forms forever, never terminating.

简单的来表述,其实是因为 Simplex 算法自身的原因,可能会产生不同的旋转迭代过程中,松弛形式相同,从而无法缩减目标值,并构成循环条件。

避免退化的方法就是使用 Bland 规则:在选择带入变量和替出变脸的时候,选择满足下列条件的最小值:

  1. 带入变量 $x_e$:目标条件中,系数为负数的第一个作为带入变量;
  2. 替出变量 $x_i$:对所有约束条件中,选择对 $x_e$ 约束强度最大的一式;

Simplex 算法 Coding 及改善

拿出最开始的线性规划方程组(松弛形式):

$$
\begin{cases}
\ -x_1-14x_2-6x_3 \quad min\\
\ x_1+x_2+x_3+x_4=4 \\
\ x_1+x_5=2 \\
\ x_3+x_6=3 \\
\ 3x_2+x_3+x_7=6 \\
\ x_1, x_2, x_3, x_4, x_5, x_6, x_7 \geq 0
\end{cases}
$$

用三个矩阵来表达这个松弛形式:

$$
C =
\left\{
\begin{matrix}
-1 & -14 & -6 & 0 & 0 & 0 & 0 \\
\end{matrix}
\right\}
$$

$$
B =
\left\{
\begin{matrix}
4 \\
2 \\
3 \\
6
\end{matrix}
\right\}
$$

$$
A =
\left\{
\begin{matrix}
1 & 1 & 1 & 1 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 1 & 0 \\
0 & 3 & 1 & 0 & 0 & 0 & 1
\end{matrix}
\right\}
$$

  • 矩阵 A:约束条件的系数矩阵;
  • 矩阵 B:约束条件值矩阵;
  • 矩阵 C:目标函数系数矩阵;

把这三个矩阵拼接起来:

$$
S_1 =
\left\{
\begin{matrix}
0 & -1 & -14 & -6 & 0 & 0 & 0 & 0 \\
4 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\
2 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\
3 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\
6 & 0 & 3 & 1 & 0 & 0 & 0 & 1
\end{matrix}
\right\}
$$

然后我们拿出第一次旋转后的约束方程:

$$
\begin{cases}
\ \beta=-2-14x_2-6x_3+x_5 \\
\ x_4=2-x_2-x_3+x_5 \\
\ x_5 = 2-x_1 \\
\ x_6 = 3-x_3 \\
\ x_7 = 6-3x_2-x_3
\end{cases}
$$

整理后获得矩阵:

$$
S_2 =
\left\{
\begin{matrix}
2 & 0 & -14 & -6 & 0 & 1 & 0 & 0 \\
2 & 0 & 1 & 1 & 1 & -1 & 0 & 0 \\
2 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\
3 & 0 & 0 & 1 & 0 & 0& 1 & 0 \\
6 & 0 & 3 & 1 & 0 & 0 & 0 & 1 \\
\end{matrix}
\right\}
$$

在这一步中,我们选择了将 $x_1$ 用 $x_5$ 表示。矩阵变换由于 $x_1$ 是被替换量。

第三行中,我们需要的是将选用量的系数归一。所以该行只要进行 matrix[2] /= matrix[2][1] 即可。

我们推导一下非第三行的变换规律。$x_1=2-x_5$,得到第 i 行的系数 matrix[i - 1] = matrix[i - 1] - matrix[2] * matrix[i - 1][1]。我们发现还原操作最后变成了两行相减。

对于目标函数,与非第三行进行同样的操作即可。通过这个思路写出代码:

```python
import numpy as np

class Simplex(object):

def __init__(self, obj, max_mode=False):
    # 默认是解决 min LP 问题,如果是最大值用 True,要 mut -1
    self.max_mode = max_mode
    self.mat = np.array([[0] + obj]) * (-1 if max_mode else 1)

def add_constraint(self, a, b):
    # 增加约束,即在矩阵最后一行增加
    self.mat = np.vstack([self.mat, [b] + a])

@property
def solve(self):
    # 获得矩阵的纬度
    m, n = self.mat.shape
    # 零矩阵和对角矩阵上下排列
    temp, B = np.vstack([np.zeros((1, m - 1)), np.eye(m - 1)]), list(range(n - 1, n + m - 1))
    # 组合系数矩阵
    mat = self.mat = np.hstack([self.mat, temp])
    # 循环所有目标函数的系数,直到全部没有负数为止
    while mat[0, 1:].min() < 0:
        # 1. 选择合适的替入和替出变量
        # Bland 规则对矩阵做退化操
        col = np.where(mat[0, 1:] < 0)[0][0] + 1
        row = np.array([mat[i][0] / mat[i][col] if mat[i][col] > 0 else 0x7fffffff for i in
                        range(1, mat.shape[0])]).argmin() + 1  # find the theta index
        # 如果没有替出变量,则说明原问题无界
        if mat[row][col] <= 0: return None

        # 2. 旋转过程
        # 系数归一,整行相除
        mat[row] /= mat[row][col]
        # 对所有 i!= row 进行 mat[i]= mat[i] - mat[row] * mat[i][col] 操作
        ids = np.arange(mat.shape[0]) != row
        mat[ids] -= mat[row] * mat[ids, col:col + 1]
        B[row] = col
top Created with Sketch.