使用 docplex 和 Python 呼叫 CPLEX 解指派問題 (assignment problem)

考慮指派問題，2000 個工作要分給 2000 個人做， 所以一共有四百萬 (2000 * 2000) 個決策變數， 4000 個限制式。

利用 docplex 和 Python (3.5 版) 呼叫 (IBM) CPLEX (12.8.0 版)，作業系統 Windows 7、記憶體 4GB、處理器 Intel i3-2350M CPU @ 2.30 GHz，使用 Anaconda3 提供的 Spyder IDE，(一次) 執行時間 306 秒，可以得到最佳解。學校的老師可以申請免費的 CPLEX 學術版。

可以參考一下程式碼


from docplex.mp.model import Model
import time, numpy

numberTeam =  2000
people = numberTeam
jobs = numberTeam
m = Model(name='assignment_problem')
R = range(numberTeam)
# decision variables
x = m.binary_var_dict((i, j) for i in R for j in R)

# Constraints
for j in range(jobs):
    m.add_constraint(m.sum(x[i, j] for i in range(people)) == 1)    
for i in range(people):
    m.add_constraint(m.sum(x[i, j] for j in range(jobs)) == 1)

# Objective function
objective = numpy.random.randint(low = 5, high = 100, size=(numberTeam, numberTeam))
total_cost = m.sum(objective[i][j] * x[i,j] for i in range(people) for j in range(jobs))
m.minimize(total_cost)

t = time.time() 
m.solve()
print("完成時間為 ", time.time()-t,  "秒")
m.print_information()
m.objective_value

m.solve_details