[Knapsack Problem (Wikipedia)](https://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83 % E3% 82% AF% E5% 95% 8F% E9% A1% 8C) Branch and Bound (Wikipedia) % 9E% 9D% E9% 99% 90% E5% AE% 9A% E6% B3% 95). The other day I solved the knapsack problem with a greedy algorithm. Solving the Python knapsack problem with the greedy algorithm
The greedy algorithm was not a method for finding an exact solution, but a method for finding a good solution. This time we will implement a branch-and-bound method to find an exact solution.
(About the branch-and-bound method from Wikipedia)
Branch-and-bound method (Bunshigen Teiho, English: branch and bound,BB)
It is a general-purpose algorithm that finds optimal solutions for various optimization problems (especially discrete optimization and combinatorial optimization).
Branch operation (English:branching operation) and limited operation (English):Bounding operation).
It systematically lists all solution candidates, using an optimized amount of upper and lower bound estimates.
Non-optimal candidates are thrown away "in bulk".
Checking all the candidates would be too many, so it is possible to use the mitigation problem (the solution of x is 0 or 1, but find the solution with 0 <= x <= 1). If there isn't one, I feel like I'm going to cut it from the candidates. If the solution of the mitigation problem is smaller than the solution of the provisional solution, it is removed from the candidates.
We would appreciate it if you could let us know if there are any deficiencies or suggestions for improvement regarding the code.
2*x1 + 3*x2 + 5*x3 + 6*x4 <= 9
xi = 0 or 1 (i = 1, 2, 3, 4)
Under the above conditions
4*x1 + 5*x2 + 12*x3 + 14*x4
To maximize( x1, x2, x3, x4 )Use the branch-and-bound method.
import numpy as np
from pandas import DataFrame
import copy
class BranchAndBound:
def __init__(self, weights, values, max_weight, answer_val):
self.weights = np.array(weights)
self.values = np.array(values)
self.max_weight = max_weight
self.answer_val = answer_val
self.evaluates = self.values/self.weights
self.index_list = []
for index in range(1, len(weights) + 1):
self.index_list.append('x' + str(index))
self.target_df = DataFrame(np.c_[self.evaluates, self.weights, self.values, np.array(self.answer_val)], index=self.index_list, columns=["evaluate", "weight", "value", "ans"])
self.target_df = self.target_df.sort_values('evaluate', ascending=False)
self.answer_val = list(self.target_df['ans']) # answer_Changed val to one sorted in descending order of evaluation value
del self.target_df['ans'] #Removed "ans" column as it is no longer needed for DataFrame
self.target_ans = np.dot(np.array(answer_val), values)
self.index_list = self.target_df.index #Change index order
def __judgeValue(self, fixed_list): # fixed_Solve the mitigation problem at the fixed value of x passed in list and judge the branch continuation. Also, if a better solution is found, the provisional solution will be exchanged.
sum_weight = 0 #The total weight of the adopted x
evaluate_list = [] #Stores acceptance decision
evaluate_list.extend(fixed_list)
for index, val in enumerate(fixed_list):
sum_weight += self.target_df.ix[self.index_list[index]]['weight']*val # fixed_The total weight of the x values passed in list
for index in range(len(fixed_list), len(self.index_list)):
if sum_weight > self.max_weight: #max_If the weight is exceeded, the branch ends
return False #Branch end
elif sum_weight == self.max_weight: #max_Since the weight has been reached, the other x is 0
evaluate_list.append(0)
continue
else:
if sum_weight + self.target_df.ix[self.index_list[index]]['weight'] < self.max_weight: # x=Even if it is 1, max_When weight is not reached
sum_weight += self.target_df.ix[self.index_list[index]]['weight']
evaluate_list.append(1)
else: # 0 < x <=When it becomes 1
evaluate_list.append((self.max_weight - sum_weight)/self.target_df.ix[self.index_list[index]]['weight'])
sum_weight = self.max_weight
if (self.max_weight - sum_weight) == self.target_df.ix[self.index_list[index]]['weight']: # x=When 1, replace the provisional solution
evaluate_list_count = len(evaluate_list)
for i in range(evaluate_list_count, len(self.index_list)): #Enter 0 for all x that have not been decided
evaluate_list.append(0)
self.target_ans = np.dot(np.array(evaluate_list), np.array(self.target_df.value)) #Provisional solution target_Replacing ans
self.answer_val = evaluate_list #Provisional answer answer_Replacing val
return False #Branch end
if len(fixed_list) == len(self.index_list): #Comparison with the provisional solution when all x values are fixed
if (sum_weight <= self.max_weight) and (np.dot(np.array(fixed_list), np.array(self.target_df.value)) > self.target_ans): #Comparison with the provisional solution
self.target_ans = np.dot(np.array(fixed_list), np.array(self.target_df.value)) #Provisional solution target_Replacing ans
self.answer_val = fixed_list #Provisional answer answer_Replacing val
return False
if np.dot(np.array(evaluate_list), np.array(self.target_df.value)) > self.target_ans: #When the solution of the mitigation problem exceeds the provisional solution
return True #Branch continuation
else: #When the provisional solution is not exceeded
return False #Branch end
def breadthFirstSearch(self): #Breadth-first search
search_lists = [[0], [1]] #element[0]、[1]Put in first
while len(search_lists) != 0: # search_Continue until lists are empty
first_list = search_lists[0] #Think in Queue, get one from the top
search_lists.pop(0) #Delete the acquired element
if self.__judgeValue(first_list): #Whether the search continues
new_list_cp = copy.deepcopy(first_list) #Deep copy to add "1" to the next element
new_list_cp.append(0) #Add 0 to the end
search_lists.append(new_list_cp) #Search for new elements_Store at the end of lists
new_list_cp = copy.deepcopy(first_list) #Deep copy to add "0" to next element
new_list_cp.append(1) #Add 1 to the end
search_lists.append(new_list_cp) #Search for new elements_Store at the end of lists
print("-----Breadth-first search-----")
for index, val in enumerate(self.index_list):
print(val + ": " + str(self.answer_val[index]))
print("ans: " + str(self.target_ans))
def depthFirstSearch(self): #Depth-first search
search_lists = [[0], [1]] #element[0]、[1]Put in first
while len(search_lists) != 0: # search_Continue until lists are empty
first_list = search_lists[0] #Think with Stach, get one from the top
search_lists.pop(0) #Delete the acquired element
if self.__judgeValue(first_list): #Whether the search continues
new_list_cp = copy.deepcopy(first_list) #Deep copy to add "1" to the next element
new_list_cp.append(1) #Add 1 to the end
search_lists.insert(0, new_list_cp) #Search for new elements_Store at the beginning of lists
new_list_cp = copy.deepcopy(first_list) #Deep copy to add "0" to next element
new_list_cp.append(0) #Add 0 to the end
search_lists.insert(0, new_list_cp) #Search for new elements_Store at the beginning of lists
print("-----Depth-first search-----")
for index, val in enumerate(self.index_list):
print(val + ": " + str(self.answer_val[index]))
print("ans: " + str(self.target_ans))
# BranchAndBound(weight_list(a1, a2, a3, a4), value_list(c1, c2, c3, c4), max_weight(a_max), first_values(x1, x2, x3, x4))
# first_values can be anything, but here greedy-The solution obtained by the algorithm is given as the initial value.
bb = BranchAndBound([2, 3, 5, 6], [4, 5, 12, 14], 9, [1, 0, 0, 1] )
bb.breadthFirstSearch()
bb = BranchAndBound([2, 3, 5, 6], [4, 5, 12, 14], 9, [1, 0, 0, 1] )
bb.depthFirstSearch()
In the branch-and-bound method, there seems to be a depth-first search and a breadth-first search, so I tried either method.
It seems that the amount of code can be reduced a little more. ..
-----Breadth-first search-----
x3: 0
x4: 1
x1: 0
x2: 1
ans: 19.0
-----Depth-first search-----
x3: 0
x4: 1
x1: 0
x2: 1
ans: 19.0
Therefore, ( x1, x2, x3, x4 ) = ( 0, 1, 0, 1 )
Recommended Posts