数学建模应用中整数线性规划问题的常用解法初探

徐晓辉

[摘           要]  在数学建模应用中，整数线性规划问题是一种常见的运筹学问题，其常用的解法有分支定界法、割平面法、蒙特卡罗法等。试图从数学建模实践的角度，淡化理论证明，仅对这几种典型方法的原理、优缺点、应用范围等作一个简要的分析比较，以供读者在实际的数学建模过程中灵活应用。

[关    键   词]  整数线性规划;分支定界法;割平面法;蒙特卡罗法

[中图分类号]  O151.2                 [文献标志码]  A               [文章编号]  2096-0603（2021）07-0178-02

一、整数线性规划问题

规划问题是运筹学的一个重要分支，从表达形式上看，可以分为线性规划（linear programming，LP）和非线性规划（non-linear programming，NLP）;从变量的可行域要求來看，也可以分为整数规划（integer programming，IP）和非整数规划（non-integer

programming，NIP），若既有表达式上的线性特征，又有变量的取整要求，这样的规划问题我们一般称之为整数线性规划（integer linear programming，ILP）问题[1]。

整数线性规划问题的传统解法是先求解与之对应的松弛问题（即先不考虑变量的整数约束而形成的新的线性规划问题），若刚好得到整数解，则求解过程结束;否则，再通过适当方法（切割平面或分支定界）生成一个或多个新的松弛问题（最初松弛问题加上新的切割或分支条件），重复以上步骤直至求得最优解。

一般而言，整数线性规划问题的求解难度要比普通线性规划问题大，其根本原因在于自变量取值增加了离散特性，但在工程上，离散特性恰好可以被计算机利用。蒙特卡罗算法是一类随机方法的统称。这类方法的基本思路是，可以通过随机采样进行计算而得到近似结果，随着采样的增多，得到正确结果的概率将逐渐加大，经过一定的步骤之后，就会尽可能趋近最佳结果。

二、割平面法

1958年，美国应用数学家R.E.戈莫里（Ralph Edward Gomory）首先提出了用割平面法求解整数线性规划问题的经典思路：先求解相对应的松弛问题，若该松弛问题的最优解就是整数解，则求解过程结束，否则通过适当的变形增加一个新的线性约束条件，再重复上述过程，直到最终求出原问题的最优解[2]。新增的约束条件实际上缩小了变量的可行域，因此称为“割平面”，割平面法的基本操作步骤如下：

事实上，由（3）式决定的割平面方程可能有一个或多个，这一方面提高了问题的难度，但是另一方面，增加割平面约束之后得到的新问题LP2在求解的时候也可以借助对偶单纯形法原理得到一定程度的简化。

从上述过程可以看出，基于严谨的理论推导的割平面法，比较适用于求解规模较小的整数线性规划问题，但该方法收敛的速度比较慢，而且割平面的选取不唯一，这些都增加了其使用的复杂性。

三、分支定界法

20世纪60年代，美国计算机科学家、图灵奖获得者理查德·卡普（Richard M.Karp）提出了求解整数线性规划问题的另一个经典思路[3]：同样是先求解相对应的松弛问题，若该松弛问题的最优解就是整数解，则求解过程结束，否则用与这个非整数解最接近的两个整数来约束这个变量，并作为新的约束条件加入原问题中，形成两个子问题，这称为分支;重新求得两个子问题的目标函数值确定了原问题目标函数值的上限（上界）或下限（下界），这称为定界;若某个分支的最优目标值超出了上一步的最优目标值，则直接舍弃这个分支，是为“剪枝”，该过程缩小了原问题的搜索范围，保证了算法的收敛性。重复上述分支、定界与剪枝过程，经若干步之后一般能找到原问题的最优解。上述方法称为分支定界法（branch and bound），其操作步骤如下：

Step 1：求解相应的线性规划模型，确定目标值的初始上、下界：记原整数规划问题为IP，先求解其对应的松弛问题为LP，若LP有整数解，即为IP的解，若LP的解中有非整数分量，则其目标值为IP的初始上界z1，进入下一步。

Step 2：分支。找出Step 1中解出的某个非整数分量，记为xj=bj，构造两个新的约束条件xj≤[bj]和xj≥[bj]+1（其中[bj]表示不大于bj的最大整数）并分别加到原LP中，构成两个子问题并求解它们。

Step 3：定界。以每个后继问题为一个分支，并将所求得的最优值与其他分支进行比较，找出其中最大者更新IP的上界z1;若有新的分支求得了整数解，则找出这些分支中目标函数最大者跟新IP的下界z2（最初的下界可以看作是z2=0）。

Step 4：剪枝。对任意一个分支，若本身无可行解，或是已经得到了不大于z2的非整数最优解，则可以直接“剪除”这个分支，不再往下考虑了。

Step 5：若z1>z2，则找出z1多对应的分支，继续返回Step 2，并重复上述过程，直至z1=z2z*，则z*就是此IP问题的解。

在实践中，用分支定界算法求解整数线性规划问题时，其平均收敛速度往往比用割平面法快，但新增的分支显然也增加了计算的复杂度。

四、蒙特卡罗及其他方法

蒙特卡罗法一般认为是起源于法国数学家布丰（Buffon）的投针实验，并由J.冯·诺伊曼等人在二战中研究“曼哈顿计划”时正式提出。蒙特卡罗法是一种以概率统计理论为指导的数值计算方法，其基本思路是通过随机采样的方法来计算近似结果，且随着采样的增多，得到正确结果的概率也会逐渐增大，在一定的规则下，部分采样（不完全枚举）就能得到在概率上相当满意的结果。蒙特卡罗法一般的操作步骤是：

Step1：模型匹配。分析实际问题所求变量的特征，寻找恰当的概率统计模型，使得该模型某个指标的概率分布或者数字特征恰好可以用来表达该实际问题所求的解。

Step2：模拟测试。对上述模型中的随机变量建立抽样方法，在计算机上进行模擬测试，抽取足够多的随机数，对有关事件进行统计。

Step3：结果分析。对模拟试验结果加以分析，给出所求解及其精度（方差）的估计。

Step4：模型改进。若上述Step3得到的结果不够理想，或实验方案费用过高，还可以考虑进一步改进模型以提高模拟计算的效率。

从应用的角度来说，用蒙特卡罗法求解整数线性规划问题当然是可行的，而且适合于高维或者可行域较大的情形。因为在计算机模拟的条件下，低维或可行域较小的情形下蒙特卡罗法就退化成了枚举法，或者使用前述的分支定界或割平面等方法，也能够解决问题。事实上，蒙特卡罗方法在求解非线性整数规划等复杂问题时会显示出特别的优势。

另外，还有一类特殊的整数规划问题，例如指派问题，我们称之为0-1规划;若目标函数及约束条件是线性的，我们也可称之为0-1整数线性规划问题。解决这类规划问题需要用到完全枚举法、隐枚举法或者“匈牙利法”等特殊解法，在此不做详述。

整数线性规划问题首先具有线性特征，这使得它在求解过程中可以借鉴一般线性规划问题的单纯形解法，割平面法和分支定界法本质上都是一种基于线性规划基础上迭代的方法，利用迭代逐渐缩小可行域，最终收敛到最优解。蒙特卡罗法主要依赖变量取整数这一特性，它本质上是一种有限枚举法，在某种概率意义上最终收敛到最优解。就处理能力而言，割平面法由于收敛慢，主要适用于规模较小的整数线性规划问题，分支定界法收敛速度快一些，可以解决规模稍大一点的问题，而蒙特卡罗法作为一种随机解法，可解决更大规模的问题，或者是某些非线性整数规划问题。当然，对于超大规模，或者形式特别复杂的一般整数规划问题，或许还有待开发出新的算法。

参考文献：

[1]黄力伟，冯杰，王勤，等.军事运筹学[M].北京：国防工业出版社，2016.

[2]杨明歌，常水珍.求解整数规划的割平面法的研究[J].洛阳师范学院学报，2014（5）：1-4.

[3]熊伟.运筹学（第3版）[M].北京：机械工业出版社，2014：81.

[4]Kroese，D.P.;Brereton，T.;Taimre，T.;Botev，Z.I.Why the Monte Carlo method is so important today[J].WIREs Comput Stat，2014（6）：386-392.

编辑 李 争