整数编程 | 解决 0-1 背包问题的分支与边界算法（附 MATLAB 代码）

今天为各位讲解分支定界（branch-and-bound, B&B）算法求解0-1背包问题（0-1KP），本次推文目录如下。

目录

1.0-1背包问题描述

2.数学模型

3.线性规划松弛最优解

4.实例讲解

5.MATLAB代码

我们之前在​​运筹学（最优化理论）学习笔记 | 分支定界法​​这篇推文中讲解了分支定界算法的基本操作步骤，忘记B&B算法的小伙伴可以点击上述链接复习一下。

1.0-1背包问题描述

我们之前在​​遗传算法求解0-1背包问题（附matlab源代码）​​这篇推文中对0-1背包问题进行过描述。

实际上，0-1背包问题就是将若干个重量已知、价值已知的物品装入载重量已知的背包中，使得装进背包中物品的总价值最大。具体数学描述如下：

假设有个物品，其物品的重量用 表示，物品的价值用表示，背包的最大载重量为，如果物品i被装入背包，则，否则。

2.数学模型

根据上述描述，0-1KP问题的整数规划模型如下：

其中。现在对上述整数规划模型进行松弛，即变量的取值不仅仅为0或1，而变为0~1之间的任何数，则0-1KP问题的线性规划松弛模型如下：

3.线性规划松弛最优解

一般来说求解线性规划松弛问题常采用的办法为单纯形法，但是由于背包问题约束的特殊性，实际上可以采用贪婪法求解上述线性规划松弛模型，而不必用单纯形法。

贪婪法的基本思想是尽可能将性价比高的物品装入背包，那么性价比的含义是什么？

物品的性价比物品的价值物品的重量

先将物品按照性价比进行降序排列，假设排序结果如下：

设是使下式成立的最大指标：

该式的含义为：根据排序结果最多将性价比最高的前个物品装进背包，刚好不会超出背包载重量。一旦将性价比排在第位的物品也装入背包，则会超出背包载重量。

综上所述，0-1KP问题线性规划松弛模型的最优解为

最优解的实际含义如下：

表示将性价比最高的前个物品装进背包。

表示性价比排在第位以后的物品都不会装包。

表示性价比排在第位的物品只会将其一部分装进背包，使背包内物品的总质量刚好达到背包载重量。

4.实例讲解

现有5个物品，每个物品的重量分别为，价值分别为，背包载重量为26，则就上述数据构建的整数规划数学模型如下：

step1

根据第3节线性规划松弛最优解，对上述物品按照性价比进行排序，排序结果如下：

即

此时可以将物品3和物品1装入背包中，且没有超出背包载重量，即

因此，最优解如下：

综上所述，该问题的线性规划松弛的最优解为，对应的上界为52.625。此节点编号为0，节点深度为1。

在分支定界过程中，在剪支后如何从搜索树中剩下的节点（子问题）中选择一个节点继续进行分支也将影响整个分支定界的收敛速度，本文我们将使用深度优先策略。

深度优先含义如下：把分支定界树的层数定义为节点的深度，深度优先策略是选择具有最大深度的节点进行分支，从而快速找到可行解。

step2

选择分数变量进行分支，固定和，则得到2个子问题：

子问题（P1）的线性规划松弛的最优解为，对应的上界为52.57，此节点编号为1，节点深度为2。子问题（P2）的线性规划松弛的最优解为，对应的上界为52，此节点编号为2，节点深度为2。分支过程如下图所示：

step3

选择子问题（P1），选择分数变量进行分支，固定和，则得到2个子问题：

子问题（P1）的线性规划松弛的最优解为，对应的上界为52.33，此节点编号为3，节点深度为3。子问题（P2）的线性规划松弛的最优解为，对应的上界为52，此节点编号为4，节点深度为3。分支过程如下图所示：

step4

选择子问题（P1），选择分数变量进行分支，固定和，则得到2个子问题：

子问题（P1）的线性规划松弛的最优解为，**==对应的上界为47==，此节点编号为5，节点深度为4，因为此节点最优解为整数解，所以先保留此整数解作为当前最优可行解，不需要继续对该节点进行分支。子问题（P2）的线性规划松弛的最优解为，对应的上界为51，此节点编号为6，节点深度为4**。分支过程如下图所示：

step5

选择子问题（P2），选择分数变量进行分支，固定和，则得到2个子问题：

子问题（P1）的线性规划松弛的最优解为，对应的上界为39，此节点编号为7，节点深度为5，虽然此节点最优解为整数解，但是此节点解的目标函数值小于47，所以不需要继续对该节点进行分支。子问题（P2）的线性规划松弛的最优解为，对应的上界为50.45，此节点编号为8，节点深度为5。分支过程如下图所示：

step6

选择子问题（P2），选择分数变量进行分支，固定和，则得到2个子问题：

当时，对应的上界为40，此节点编号为9，节点深度为6，虽然此节点最优解为整数解，但是此节点解的目标函数值小于47，因此无法作为当前最优可行解。当时，不存在可行解，此节点编号为10，节点深度为6。分支过程如下图所示：

step7

找出当前未分支过，且节点深度最深的节点，从分支定界树中可以找出节点4为满足上述要求的节点。因此，对节点4进行分支，选择分数变量进行分支，固定和，则得到2个子问题：

子问题（P1）的线性规划松弛的最优解为，对应的上界为50.22，此节点编号为11，节点深度为4。子问题（P2）的线性规划松弛的最优解为，对应的上界为51.64，此节点编号为12，节点深度为4。分支过程如下图所示：

step8

选择子问题（P2），选择分数变量进行分支，固定和，则得到2个子问题：

子问题（P1）的线性规划松弛的最优解为，对应的上界为49.44，此节点编号为13，节点深度为5。子问题（P2）不存在可行解，此节点编号为14，节点深度为5。分支过程如下图所示：

step9

选择子问题（P1），选择分数变量进行分支，固定和，则得到2个子问题：

当时，对应的上界为37，此节点编号为15，节点深度为6，虽然此节点最优解为整数解，但是此节点解的目标函数值小于47，因此无法作为当前最优可行解。当时，不存在可行解，此节点编号为16，节点深度为6。分支过程如下图所示：

step10

找出当前未分支过，且节点深度最深的节点，从分支定界树中可以找出节点11为满足上述要求的节点。因此，对节点11进行分支，选择分数变量进行分支，固定和，则得到2个子问题：

子问题（P1）的线性规划松弛的最优解为，对应的上界为36，此节点编号为17，节点深度为5，虽然此节点最优解为整数解，但是此节点解的目标函数值小于47，因此无法作为当前最优可行解。子问题（P2）的线性规划松弛的最优解为，对应的上界为49.9，此节点编号为18，节点深度为5。分支过程如下图所示：

step11

选择子问题（P2），选择分数变量进行分支，固定和，则得到2个子问题：

当时，对应的上界为29，此节点编号为19，节点深度为6，虽然此节点最优解为整数解，但是此节点解的目标函数值小于47，因此无法作为当前最优可行解。当时，不存在可行解，此节点编号为20，节点深度为6。分支过程如下图所示：

step12

找出当前未分支过，且节点深度最深的节点，从分支定界树中可以找出节点2为满足上述要求的节点。因此，对节点11进行分支，选择分数变量进行分支，固定和，则得到2个子问题：

子问题（P1）的线性规划松弛的最优解为，对应的**==上界为51==，此节点编号为21，节点深度为3，因为此节点最优解为整数解，并且此节点解的目标函数值大于47，所以==更新当前最优可行解==，且无需继续对该节点进行分支。子问题（P2）的线性规划松弛的最优解为，对应的上界为51.55，此节点编号为22，节点深度为3**。分支过程如下图所示：

step13

选择子问题（P2），选择分数变量进行分支，固定和，则得到2个子问题：

子问题（P1）的线性规划松弛的最优解为，对应的上界为50.14，此节点编号为23，节点深度为4，虽然此节点最优解为不是整数解，但是此节点解的目标函数值小于51，因此无需继续对该节点进行分支。子问题（P2）不存在可行解，此节点编号为24，节点深度为4。分支过程如下图所示：

至此，最优解为[0,1,1,10]，总价值为51，总重量为26，满足背包载重量约束。

5.MATLAB代码

本次推文暂时只公布MATLAB加密代码，后续如果各位有需要，我们会单独出一期推文讲解本次推文代码。

代码获取方式：公众号后台回复【BAB求解01KP】，即可获取代码。

代码使用方式如下：

%% @copyright
%微信公众号：优化算法交流地
clear
clc
tic
%% 输入数据 方式1
w=importdata('p08_w.txt')';     %物品重量
p=importdata('p08_p.txt')';     %物品价值
cap=importdata('p08_c.txt');    %背包载重量
s=importdata('p08_s.txt');      %已知最优解


%% 输入数据 方式2
% p=[8,11,6,4];
% w=[5,7,4,3];
% cap=14;


%% bnb_01kp函数
%输入w：物品重量
%输入p：物品价值
%输入cap：背包载重量
%输出bestSol：最优解，即哪些物品装包，哪些物品不装包
%输出bestValue：最优解总价值
%输出bestWeight：最优解总重量
[bestSol,bestValue,bestWeight]=bnb_01kp(w,p,cap);
toc
%微信公众号：优化算法交流地

直接在主函数main中输入数据即可，第一种输入方式：将数据存放在txt文件中，第二种输入方式：直接在代码中手动输入即可。

样例数据为：背包载重量为6404180，物品数目为24，各个物品重量和价值数据如下：

求解结果如下：

参考文献

[1] 孙小玲，李端，整数规划，科学出版社，2010

OK，今天就到这里啦，各位可点击下方图片留言。

​​

微信公众号：优化算法交流地