python-3.x - docplex.cp.model 比穷举搜索慢
问题描述
我正在解决一个combinatorial optimisation
问题,并意识到这CPLEX
需要很长时间才能运行。这是一个玩具示例:
我正在使用python
APIdocplex
import numpy as np
from docplex.cp.model import CpoModel
N = 5000
S = 10
k = 2
u_i = np.random.rand(N)[:,np.newaxis]
u_ij = np.random.rand(N*S).reshape(N, S)
beta = np.random.rand(N)[:,np.newaxis]
m = CpoModel(name = 'model')
R = range(0, S)
idx = [(j) for j in R]
I = m.binary_var_dict(idx)
m.add_constraint(m.sum(I[j] for j in R)<= k)
total_rev = m.sum(beta[i,0] / ( 1 + u_i[i,0]/sum(I[j] * u_ij[i,j] for j in R) ) for i in range(N) )
m.maximize(total_rev)
sol=m.solve(agent='local')
sol.print_solution()
for i in R:
if sol[I[i]]==1:
print('i : '+str(i))
部分输出如下:
Model constraints: 1, variables: integer: 10, interval: 0, sequence: 0
Solve status: Optimal
Search status: SearchCompleted, stop cause: SearchHasNotBeenStopped
Solve time: 76.14 sec
-------------------------------------------------------------------------------
Objective values: (1665.58,), bounds: (1665.74,), gaps: (9.27007e-05,)
Variables:
+ 10 anonymous variables
我尝试了详尽的搜索:
import numpy as np
import pandas as pd
from itertools import combinations,permutations,product
import time
start = time.time()
results = []
for K_i in range(1,k+1): #K
comb = list(combinations(range(S), K_i))
A = len(comb)
for a in range(A):# A
comb_i = comb[a]
I = np.repeat(0,S).reshape(-1,1)
I[comb_i,0] = 1
u_j = np.matmul(u_ij,I)
total_rev = np.sum(beta/ (1 + u_i/u_j))
results.append({'comb_i':comb_i, 'total_rev':total_rev })
end = time.time()
time_elapsed = end - start
print('time_elapsed : ', str(time_elapsed))
results = pd.DataFrame(results)
opt_results = results[results['total_rev'] == max(results['total_rev'].values)]
print(opt_results)
输出:
time_elapsed : 0.012971639633178711
comb_i total_rev
23 (1, 6) 1665.581329
如您所见,CPLEX
它比穷举搜索慢 1000 倍。有没有办法改进CPLEX
算法?
解决方案
对于这个特殊问题:
sol=m.solve(agent='local', SearchType='DepthFirst', Workers=1)
应该有很大帮助。
推荐阅读
- sql - oracle sql:“获取或插入”存储过程
- python - list_filter 以选择作为值
- javascript - 我试图通过改变宽度来隐藏数组中的所有元素。在函数内部使用了 setInterval 但它只对最后一个元素正确运行
- prolog - Prolog:查找并放入列表中的重复项
- c++ - 将彩色文本绘制到 c++ win32
- java - 如何在 JAVA 中从 Azure Functions 中引用文件?
- excel - 将不同的工作表合并为具有相同结构的工作表
- c# - 在“离开”文本框后将十六进制字符串格式化为字节数组
- reactjs - HTML to JSX REACT: addEventListener to onClick
- azure - 授予 StorageV2 目录中的用户访问权限(通用 v2)