docplex.cp.model is slower than the exhaustive search

Question

I am working on a combinatorial optimisation problem and realised the CPLEX is taking a significant time to run. Here is a toy example:

I am using the python API for docplex

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))

Part of the output is as follows:

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

The same I tried with an exhaustive search:

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)

Output:

time_elapsed :  0.012971639633178711
    comb_i    total_rev
23  (1, 6)  1665.581329

As you can see the CPLEX is 1000 times slower than the exhaustive search. Is there a way to improve the CPLEX algorithm?

Package `docplex.cp` uses CPO, a Constraint Programming engine, which is different from CPLEX, a linear programming engine (package `docplex.mp.xxx`) — Philippe Couronne, Sep 26 '21 at 15:38

score 1 · Answer 1 · edited Nov 13 '21 at 02:14

1

For this particular problem:

sol=m.solve(agent='local', SearchType='DepthFirst', Workers=1)

should help out a lot.

edited Nov 13 '21 at 02:14

Nick is tired

6,860
20
39
51

answered Sep 27 '21 at 08:27

Paul Shaw

36
1

score 1 · Answer 2 · answered Sep 27 '21 at 08:32

1

if you change

sol=m.solve(agent='local')

to

sol=m.solve(agent='local',SearchType="DepthFirst")

you ll get the optimal solution faster.

Nb:

Proving optimality may take time sometimes with CPOptimizer

answered Sep 27 '21 at 08:32

Alex Fleischer

9,276
2
12
15

Thanks for your reply, yes it does improve the run time but still slower than the exhaustive algorithm ive written. I think the issue is because of the loop in the CP optimisation `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) )`. Do you think I can improve this line? – S.Perera Sep 27 '21 at 08:59

docplex.cp.model is slower than the exhaustive search

2 Answers2