XJTU System Optimization and Scheduling Final Report

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 7.7k 阅读时长 ≈ 7 分钟

分支定界法在背包问题中的应用

西安交通大学《系统优化与调度》课程期末报告

1 背景简介

背包问题（Knapsack problem）是一种组合优化的NP完全（NP-Complete，NPC）问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。

2 数学描述

背包问题根据物品数量限制的不同分为以下三类：0-1背包问题，完全背包问题和多重背包问题。0-1背包问题是指每样物品只有一件，即每件物品只有未放入背包和放入背包（0和1）两种状态；而在完全背包问题中，每样物品的数量没有限制，即可以向背包中放入任意多个任意物品；多重背包问题则是指每样物品有一定的数量限制，即在背包中放入的某样物品数量不能超过其数量限制。下文将分别介绍这三类背包问题的数学描述。

2.1 0-1 背包问题

最基本的背包问题，其数学描述为：有 \(n\) 件物品，物品 \(i\) 的体积（有时也被称为代价，重量等。后文均使用体积作为代表）为 \(w_i\)，价值为 \(v_i\)。背包的容积（预算，最大承受重量等。后文均使用体积作为代表）为 \(W\)。限定每个物品最多只能往背包中放入1个，求将那些物品装入背包可以使装入物品的总体积不超过背包的容积并且总价值最大。即： \[ \max \sum_{i=1}^nv_ix_i\\ s.t.\left\{ \begin{array}{**lr**} \sum_{i=1}^nw_ix_i\leq W\\ x_i\in\{0,1\} \end{array} \right. \]

2.2 完全背包问题

完全背包问题的数学描述为：有 \(n\) 件物品，物品 \(i\) 的体积为 \(w_i\)，价值为 \(v_i\)。背包的容积为 \(W\)。每件物品有无穷多个，求如何将物品装入背包可以使装入物品的总体积不超过背包的容积并且总价值最大。即： \[ \max \sum_{i=1}^nv_ix_i\\ s.t.\left\{ \begin{array}{**lr**} \sum_{i=1}^nw_ix_i\leq W\\ x_i\in N_+ \end{array} \right. \]

2.3 多重背包问题

多重背包问题的数学描述为：有 \(n\) 件物品，物品 \(i\) 的体积为 \(w_i\)，价值为 \(v_i\)，数量为\(b_i\)。背包的容积为 \(W\)。求如何将物品装入背包可以使装入物品的总体积不超过背包的容积并且总价值最大。即： \[ \max \sum_{i=1}^nv_ix_i\\ s.t.\left\{ \begin{array}{**lr**} \sum_{i=1}^nw_ix_i\leq W\\ x_i\leq m_i\\ x_i\in N_+\\ \end{array} \right. \]

3 求解算法

3.1 分支定界算法

分支定界法（branch and bound）是一种求解整数规划问题的最常用算法。这种方法不但可以求解纯整数规划，还可以求解混合整数规划问题。分支定界法是一种搜索与迭代的方法，选择不同的分支变量和子问题进行分支。通常，把全部可行解空间反复地分割为越来越小的子集，称为分支；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。分支定界算法的步骤如下：

  1. 对于最小化问题，设定初始最优解的值为 \(best=+\infty\);
  2. 根据分枝法则（Branching rule），从尚未被洞悉（Fathomed）的节点（局部解）中选择一个节点，并在此节点的下一阶层中分为几个新的节点；
  3. 根据下界函数计算出每个节点的下界值（Lower Bound，LB）；
  4. 若节点的下限值大于当前最优值 \(best\)，则其之后的节点中不包含可行解，因此该节点在后续计算中将不再被考虑；若已找到在此节点中，具最小下限值的可行解，则停止向下搜索；否则将该节点作为未洞悉节点继续向下搜索；
  5. 判断是否仍有尚未被洞悉的节点，如果有，则进行步骤二，如果已无尚未被洞悉的节点，则演算停止，并得到最优解。

分支定界算法的关键在于分支规则和下界函数的选取。对于不同的问题，有着不同的选取方式。在背包问题中，将每件物品放入的数量作为分支依据，每件物品的不同选取方式产生搜索树的不同层。下界函数可以通过松弛放入物品个数为整数这个约束来进行计算。具体算法见后文。

3.2 求解0-1背包问题

在此问题中，节点的Lower Bound 的计算方法如下：

  1. 计算每件物品的单位体积价值，即 \(p_i=v_i/w_i\)；
  2. 计算已经确定状态（装入/不装入）物品的总体积 \(w_{sum}\) 和总价值 \(v_{sum}\)；
  3. 若 \(w_{sum}>W\)，则节点无效；否则从未确定状态的物品中挑选单位体积价值最高的物品依次装入背包，直到将背包装满（此时可以装入浮点数个物品，如6/7个物品2，松弛条件在这里生效）。再次计算背包中物品的总价值 \(v_{sum}\)，即为该节点的 Lower Bound。

分支定界算法过程如下：

  1. 创建空队列，将根节点放入队列中；
  2. 从队列中选取一个节点，生成该节点的子节点。若无子节点说明该节点为可行解，与当前最优解进行比较，若小于最优解则替换当前最优解；若子节点存在，则计算每个子节点的Lower Bound，若子节点不合法或者Lower Bound大于当前最优解则将该节点舍去，否则将该节点加入队列中。
  3. 重复步骤2直到队列为空，此时保留下来的最优解即为该问题最优解。

节点生成算法如下：

  1. 找出所有未确定状态的物品；
  2. 选出这些物品中单位体积价值最大的物品；
  3. 生成两个节点分别为放入该物品和不放入该物品之后的状态节点。

在分支定界过程中，从队列中选取节点方法主要有以下两种：

  • FIFO 选取，即先入先出，依照队列的顺序进行节点的选取。优点为存储空间需求较小；缺点为搜索方式类似BFS，需要大量的运算后才能搜索到可行解从而更新最优解和剪枝，运算量较大。
  • 优先队列选取，每次从队列中选取Lower Bound最小的节点进行探索。优点为运算量小，快速向下探索更新可行最优解便于更有效的剪枝；缺点为需要更多的存储空间。

以一个简单的0-1背包问题为例：

背包容量为10，物品个数为5，其体积和价值如下表所示：

1 2 3 4 5
cost 2 2 6 5 4
value 6 3 5 4 6

通过以上两种不同节点选取方式计算出的结果均为：

选取物品1, 2, 5，最大价值为15。其中，采用FIFO选取算法循环运算46次，采用优先队列选取算法循环运算13次。

3.3 求解多维背包问题

多维背包问题与0-1背包问题的区别在于，每件物品可以放入背包一定数量以内个而非只有一个，即物品 \(i\) 最多可以在背包中放入 \(b_i\) 个。通过对0-1背包问题的分支定界求解算法作出一部分调整即可进行求解。改动如下：

在此问题中，节点的Lower Bound 的计算方法如下：

  1. 计算每件物品的单位体积价值，即 \(p_i=v_i/w_i\)；
  2. 计算已经确定装入数量物品的总体积 \(w_{sum}\) 和总价值 \(v_{sum}\)；
  3. 若 \(w_{sum}>W\)，则节点无效；否则从未确定状态的物品中挑选单位体积价值最高的物品依次装入背包，直到将背包装满（此时可以装入浮点数个物品，如1.5个物品2，松弛条件在这里生效）。再次计算背包中物品的总价值 \(v_{sum}\)，即为该节点的 Lower Bound。

子节点生成的计算方法如下：

  1. 找出所有未确定状态的物品；
  2. 选出这些物品中单位体积价值最大的物品；
  3. 根据该物品的数量限制 \(b_i\) 生成 \(b_{i}+1\) 个子节点，每个子节点分别放入该物品 \(0,1,...,b_{i}\)个

其余部分的计算方法与0-1背包问题相同。通过多次迭代即可得到最优解。

3.4 求解完全背包问题

分支定界算法的核心部分为剪枝搜索，而完全背包问题每一件物品没有数量限制。这就导致每一个搜索树中的非叶节点有无穷个子节点。采用该算法无法构建与之对应的搜索树。因此，对于完全背包问题，分支定界算法并不适用。

4 数值运算

4.1 0-1 背包问题数值运算

选取多个背包问题对上述算法进行测试（具体测试数据见附录），测试结果如下：

物品个数 背包大小 最大价值 循环次数
5 100 133 10
8 200 334 14
10 300 383 20
100 1000 2614 276
100 1000 2541 287
100 1000 2617 244

上述计算结果均使用优先队列选取方式，其运算速度相较于队列选取计算速度要快上很多。此外，动态规划也常用来求解背包问题。但动态规划求解的复杂度对数据敏感，在同样大小，不同内容的数据上的复杂度不同。而分支定界法在一般情况下计算时间复杂度较为稳定，基本不会受到数据内容的影响。

4.2 多重背包问题数值运算

其余数据与上述0-1背包相同，增加每件物品的数量限制，将每件物品的数量上限均设置为2个，得到计算结果如下

物品个数 背包大小 最大价值 循环次数
5 100 196 16
8 200 481 38
10 300 559 44
100 1000 3645 12580
100 1000 3766 14216
100 1000 3440 9490

上述计算结果均使用优先队列选取方式，可以看出，相较于0-1背包问题，计算多重背包问题需要更长的时间。这是因为增加物品数量会指数级提升搜索树的节点个数。从而大大提升计算所需要的循环次数。因此，分支定界算对于大规模的多重背包问题并不适用。

5 小结

分支定界算法是一种剪枝搜索算法，其核心思想在于通过松弛部分约束条件来快速求得每种状态下的Lower Bound，通过Lower Bound和Best比较来进行剪枝。从而快速去除大量不存在可行解的区域，最终快速求得最优解。

但是，分支定界算法也有其固有的局限性。首先，分支定界算法在计算时需要在搜索树中进行搜索。这在面对多维大规模的问题时，虽然通过剪枝可以减少很多不必要的搜索过程，但剩余的搜索规模依然很大，特别是在搜索树很深时，增加一点宽度就可能会增加大量的计算量；其次，分支定界算法在数学上是不稳定的，其剪枝过程依赖的 Lower Bound 是下届而非下确界，因此完全可以构造一组数据使得分支定界算法无法完成剪枝操作从而使其需要搜索树中的每个节点，大大增加算法的复杂度。

6 附录

数值计算代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
import math
import queue
import numpy as np

# simple example
N=5
W=20
w=np.array([2,2,6,5,4])
v=-np.array([6,3,5,4,6])
b=np.array([2,3,5,7,4])

# read data from file
with open('temp.txt','r+') as f:
    w=[]
    v=[]
    text=f.readline()[:-1]
    data=text.split(' ')
    N=int(data[0])
    W=int(data[1])
    while True:
        text=f.readline()
        if not text:
            break
        text=text[:-1]
        data=text.split(' ')
        w.append(int(data[0]))
        v.append(int(data[1]))
    w=np.array(w)
    v=-np.array(v)

b=np.array([2]*100)
root_state=[-1]*N

v_per_w=v/w
sort_index=np.argsort(v_per_w)


def get_min_good(state):
    for i in sort_index:
        if state[i]<0:
            return i
    return None

def lower_bound(state):
    w_sum=0
    v_sum=0
    state=list(state)

    for i,s in enumerate(state):
        if s>=0:
            w_sum+=w[i]*s
            v_sum+=v[i]*s
    if w_sum>W:
        return math.inf
    while w_sum<W:
        w_free=W-w_sum
        selected_good=get_min_good(state)
        if selected_good is None:
            break
        if w[selected_good]<w_free*b[selected_good]:
            w_sum+=w[selected_good]*b[selected_good]
            v_sum+=v[selected_good]*b[selected_good]
            state[selected_good]=b[selected_good]
        else:
            w_sum=W
            v_sum+=v[selected_good]*w_free/w[selected_good]
    return v_sum

def get_children(state):
    selected_good=get_min_good(state)
    if selected_good is None:
        return None
    state_list=[]
    for i in range(b[selected_good]+1):
        child=list(state)
        child[selected_good]=i
        state_list.append(child)
    return state_list

# calculate the accurate value of state
def func(state):
    w_sum=0
    v_sum=0

    for i,s in enumerate(state):
        if s>=0:
            w_sum+=w[i]*s
            v_sum+=v[i]*s
    if w_sum>W:
        return math.inf
    return v_sum

def queue_search(state):
    best=math.inf
    best_state=None
    temporal_cost=0

    search_queue=queue.SimpleQueue()
    search_queue.put(state)

    while not search_queue.empty():
        temporal_cost+=1
        state_now=search_queue.get()
        state_list=get_children(state_now)
        if state_list is None:
            if best>func(state_now):
                best=func(state_now)
                best_state=state_now
            continue
        for state in state_list:
            bound=lower_bound(state)
            if bound == math.inf or bound>best:
                continue
            search_queue.put(state)
    print('FIFO Search\n    Temporal Cost:',temporal_cost,'Optimal Result:',best_state,'Optimal Value:',best)
    return best,best_state

class Node:
    def __init__(self,state) -> None:
        self.state=state
        self.bound=lower_bound(state)

# find the node with the lowest lower bound
def get_lowest_node(search_queue):
    lowest_bound=math.inf
    lowest_node=None
    for node in search_queue:
        if node.bound<lowest_bound:
            lowest_bound=node.bound
            lowest_node=node
    return lowest_node

def priority_search(state):
    best=math.inf
    best_state=None
    temporal_cost=0

    search_queue=[]
    search_queue.append(Node(state))

    while search_queue!=[]:
        temporal_cost+=1
        node_selected=get_lowest_node(search_queue)
        search_queue.remove(node_selected)
        if node_selected is None:
            continue
        state_now=node_selected.state
        state_list=get_children(state_now)
        if state_list is None:
            if best>func(state_now):
                best=func(state_now)
                best_state=state_now
            continue
        for state in state_list:
            bound=lower_bound(state)
            if bound == math.inf or bound>best:
                continue
            search_queue.append(Node(state))
    print('Priority Search\n    Temporal Cost:',temporal_cost,'Optimal Result:',best_state,'Optimal Value:',best)
    return best,best_state

priority_search(root_state)
# queue_search(root_state)