分支定界法如何求解整数规划问题

参考资料

分支定界法

分枝定界是一种深度优先的树搜索算法。通过对树进行剪枝，可以缩小了搜索范围，大大减小计算量。但同时又不会遗漏最优解。请现在就记住，分枝定界思想，就是不断缩小搜索范围的过程。

主要思路

对有约束条件的优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。
通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。
分枝定界法可用于解纯整数或混合的整数规划问题。在本世纪六十年代初由 Land Doig 和 Dakin 等人提出的。由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。

举例分析

设有最大化的整数规划问题AAA，与它相应的线性规划为问题BBB，从解问题BBB开始，若其最优解不符合AAA的整数条件，那么BBB的最优目标函数必是AAA的最优目标函数z∗z^*z∗的上界,记作z‾\overline{z}z；而AAA的任意可行解的目标函数值将是z∗z^*z∗的一个下界z‾\underline{z}z。分支定界法就是将BBB的可行域分成子区域的方法。逐步减小z‾\overline{z}z和增大z‾\underline{z}z，最终求到z∗z^*z∗。

例

Maxz=40x1+90x2Max \quad z = 40 x_1 +90x_2 Maxz=40x1+90x2

\begin{align} s.t. \quad \begin{cases} 9x_1 +7x_2 \le 56\\ 7x_1 + 20x_2 \le 70\\ x_1,x_2 \ge 0,integer \end{cases} \end{align}

解：
- 先不考虑整数限制，即解相应的线性规划BBB，得最优解为：
  
  x1=4.8092,x2=1.8168,z=355.8779x_1 = 4.8092,x_2 = 1.8168,z =355.8779 x1=4.8092,x2=1.8168,z=355.8779
  
  可见她不符合整数条件。这时zzz是问题AAA 的最优目标函数值z∗z^*z∗的上界，记作z‾\overline{z}z。而x1=0，x2=0x_1= 0，x_2= 0x1=0，x2=0显然是问题A的一个整数可行解，这时z=0z=0z=0,是z∗z^*z∗的一个下界，记作z‾\underline{z}z,即$ 0\le z^* \le 355$。
- 因为x1,x2x_1,x_2x1,x2当前均为非整数，故不满足整数要求，任选一个进行分枝。设选x1x_1x1进行分枝，把可行集分成2个子集(以下为增加的约束)：
  
  x1≤[4.8092]=4,x1≥[4.8092]+1=5x_1 \le [4.8092]=4, \quad x_1 \ge [4.8092] +1 =5 x1≤[4.8092]=4,x1≥[4.8092]+1=5
  
  因为4与5之间无整数，故这两个子集的整数解必与原可行集合整数解一致。这一步称为分枝。这两个子集的规划及求解如下：
  - 问题B1:B_1:B1:
    
    Maxz=40x1+90x2Max \quad z = 40x_1 + 90x_2 Maxz=40x1+90x2
    
    \begin{align} \begin{cases} 9x_1 + 7x_2 \le 56\\7x_1+20x_2 \le70 \\0\le x_1 \le4,x_2\ge0 \end{cases} \end{align}
    
    最优解为: $$ x_1 = 4.0,x_2 =2.1,z_1 =349$$
  - 问题B2:B_2:B2:
    
    Maxz=40x1+90x2Max \quad z = 40x_1 + 90x_2 Maxz=40x1+90x2
    
    \begin{align} \begin{cases} 9x_1 + 7x_2 \le 56\\7x_1+20x_2 \le70 \\x_1\ge5,x_2\ge0 \end{cases} \end{align}
    
    最优解为: $$ x_1 = 5.0,x_2 =1.57,z_1 =341.4$$
  - 再定界：0≤z∗≤3490 \le z^* \le 3490≤z∗≤349
- 对问题B1:B_1:B1:再对不是整数的x2x_2x2进行分枝得问题B11B_{11}B11和B12B_{12}B12，它们的最优解为：
  - B11:x1=4,x2=2,z11=340B_{11}:x_1 = 4,x_2 = 2,z_{11} = 340B11:x1=4,x2=2,z11=340
  - B12:x1=1.43,x2=3.00,z12=327.14B_{12}:x_1=1.43,x_2=3.00,z_{12}=327.14B12:x1=1.43,x2=3.00,z12=327.14
  - 由开头所说，线性规划BBB的最优目标函数值必是AAA的最优目标函数z∗z^*z∗的上界,记作z‾\overline{z}z，整数规划AAA的任意可行解的目标函数值将是z∗z^*z∗的一个下界z‾\underline{z}z。
  - 再定界有：340≤z∗≤349340 \le z^*\le349340≤z∗≤349，并将不在这个范围内的B12B_{12}B12剪枝。
- 对问题B2B_2B2再进行分枝得问题B21B_{21}B21和B22B_{22}B22，它们的最优解为：
  - B21:x1=5.44,x2=1.00,z22=308B_{21}:x_1 = 5.44,x_2 = 1.00,z_{22} = 308B21:x1=5.44,x2=1.00,z22=308
  - B22B_{22}B22无可行解
  - 再定界有：340≤z∗≤341340 \le z^*\le341340≤z∗≤341将B21,B22B_{21},B_{22}B21,B22 剪枝。
- 于是可以断定原问题的最优解为：
  
  x1=4,x2=2,z∗=340x_1 = 4,x_2 = 2,z^{*} = 340 x1=4,x2=2,z∗=340
- 但是我认为现在还不能断定这个解就是原问题的最优解，刚开始是选择的是x1,我认为可能还需要对x2进行这样的分枝定界才能最终确定最优解是什么，可能理解的不准确仅作参考。
图解如下