使用 Python 呼叫 Gurobi 解背包問題 (Knapsack problem)

背包問題 (Knapsack problem) 是一種組合最佳化的 NP 完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最高。

import time
import os
import pandas as pd
import numpy as np
from gurobipy import *

sample = 500000 # 50 萬個東西
c = np.random.randint(20, high = 100, size = sample) # 亂數
A = np.random.randint(2, high = 5, size = sample)
b = 1200000
# print(c.shape[0], A.shape[0])

if not os.path.isdir('output'): # create the directory output if not exist
    os.mkdir('output')

m = Model("Knapsack")
x = m.addVars(c.shape[0], lb = 0, vtype = GRB.BINARY, name = "x") # variables
m.update()

obj = sum(c[i] * x[i] for i in range(c.shape[0]))
m.setObjective(obj, GRB.MAXIMIZE) # or MINIMIZE the objective

m.addConstr( quicksum(A[i] * x[i] for i in range(A.shape[0])) <= b) # constraint

t = time.process_time() # the current time used as the starting time
m.optimize()
t_opt = time.process_time()
# finished time minus starting time
print("Optimization time:", t_opt - t, " seconds")
# store the optimization problem as text file. Could inspect the problem
m.write('output/Knapsack.lp')

out = [] # list for the output of variable names and values
for v in m.getVars():
    out.append([v.varName, v.x]) # Append variable name and value to the output list
df = pd.DataFrame(out) # store as a Pandas dataframe 
df.to_excel('output/Knapsack.xlsx') # Output as an Excel (or csv) file
t_rec = time.process_time()
print("Recording output time:", t_rec - t_opt, " seconds")

輸出

雖然這是一個困難的組合學問題，只要 0.953 秒鐘就可以得到50 萬個東西的最佳解 (gap = 0%)，代表硬體和軟體演算法的進步，最佳化可以解決實際的問題。

使用動態規劃求解的複雜度為 O(n^2 * c_max)，其中 c_max = 100，所以此資料有多項式時間解。

學校的學生和老師可以申請免費的 Gurobi 學術版 (Gurobi and Anaconda for Windows)。