松弛+分支定界

1. 松弛+分支定界

1.1. 松弛

方式：

1. 削弱目标函数
2. 削弱约束（多为削弱约束）
   1. 线性松弛，将整数变量约束，削弱为连续变量约束

要求：

1. 原问题所有可行解必须保留
2. 新的问题比原问题更好解

1.1.1. 作用

1. 松弛模型证明元模型的可行性

2. 给出原模型目标值的界

   1. 对于min 问题， 松弛模型确定下届，取整数确定上届

      

      模型上下界

3. 采用更强的线性规划松弛

4. 使用大M 常量，是0-1变量与 普通变量联系起来 $$ x_i < 100*y_i, \space y_i 是0-1变量， x_i 是对应y=1时候的数值 $$

数学中，松弛模型使用表示， x̃，估计值使用， x̂

1.2. 分支定界

对于线性问题，逐步增加约束，树枝上每一步确定约束生效时候，值应该取多少

分支

对min问题，定界的三种情况

1. 解出整数解， 停止，尝试更新上界（这是已经探明的最好的可行解）
2. 某个松弛条件 > 上界，没有松弛必要，停止搜索
3. 某个问题不可行，停止搜索