CODEWITHSUNDEEP
pythonor-toolscp-sat
Sami Al-Subhi
Sami Al-Subhi

Reputation: 4672

Specific constraint in Or-tools is too slow, are there other methods?

I have a problem and using ortools is too slow.

The problem is that there is an item that stores have but at different prices. I need to select where to pick those items from to achieve the lowest total price as well as not exceeding 4 stores.

This is the code I have but it is slow if the supplied cost matrix has more than 4 stores. The problem lies in the store max limit constraint. Is there any other way that this can be coded differently to improve speed?

import numpy as np
from ortools.sat.python import cp_model
from ortools.linear_solver import pywraplp

#cost matrix, where j are stores, i are items

C = np.array([[38, 13, 73, 10, 76,  6, 80, 65, 17,  2],
        [77, 72,  7, 26, 51, 21, 19, 85, 12, 29],
        [30, 15, 51, 69, 88, 88, 95, 97, 87, 14],
        [10,  8, 64, 62, 23, 58,  2,  1, 61, 82],
        [ 9, 89, 14, 48, 73, 31, 72,  4, 71, 22],
        [50, 58,  4, 69, 25, 44, 77, 27, 53, 81],
        [42, 83, 16, 65, 69, 26, 99, 88,  8, 27],
        [26, 23, 10, 68, 24, 28, 38, 58, 84, 39],
        [ 9, 33, 35, 11, 24, 16, 88, 26, 72, 93],
        [75, 63, 47, 33, 89, 24, 56, 66, 78,  4],
        [ 1, 78,  7, 53, 86, 71,  3, 77, 92, 22],
        [76,  8, 78, 73, 76, 77, 44, 21, 31, 37],
        [ 8, 46, 69, 58, 83, 97, 14, 11, 24, 82],
        [ 8, 25, 75, 93, 21, 33, 13, 66, 95, 61],
        [25, 83, 98,  3, 93, 99, 11, 55, 97, 83],
        [87, 71, 67, 72, 49, 55, 16,  6, 18, 43],
        [21, 49, 23, 14, 98, 54, 85, 11, 97, 56],
        [62, 57, 90, 22, 97, 84, 26, 15, 14, 85],
        [44,  7, 78, 57, 60, 16, 25, 10, 67, 72],
        [54, 70, 37, 22, 41, 78, 92, 50, 48, 78]])
    
    # The solver:
def Solve_Cost_Matrix_2(cost):
    model = cp_model.CpModel()
    max_stops = 4

    #generate ranges
    num_items = len(cost)
    num_shops = len(cost[0])
    
    all_items = range(num_items)
    all_shops = range(num_shops)
    

    # Create bool Variable matrix
    x = []
    for i in all_items:
        t=[]
        for j in all_shops:
            t.append(model.NewBoolVar(f'i{i}_j{j}'))
        x.append(t)
    
        # Constraints
        # Each item only assigned once to any store.
    [model.Add(sum(x[i][j] for j in all_shops) == 1) for i in all_items]
           
        
    # Adding the intermediate variable to constrain the number of the stores. 
    s=[]
    for j in all_shops:
        s.append( model.NewBoolVar(f's_{j}') )
          
    for j in all_shops:
        model.Add(sum(x[i][j] for i in all_items) >= 1).OnlyEnforceIf(s[j])
        model.Add(sum(x[i][j] for i in all_items) == 0).OnlyEnforceIf(s[j].Not())
    
    model.Add(sum(s[j] for j in all_shops) <= max_stops)
  
        
    # Create the Objective function Variable
    total_cost = model.NewIntVar(0, 1000000, 'total_cost')


    # Create the Objective function, Minimize (Sum of cost) 
    model.Add(total_cost == (sum(x[i][j] * cost[i][j] for j in all_shops for i in all_items )))

    model.Minimize(total_cost)
    
        
    #Initialize the Solver
    solver = cp_model.CpSolver()
    status = solver.Solve(model)
    
    print(solver.ResponseStats())
    Total_Cost,senario_cost = 0, 0
      
  
    #printing the solution
    if status == cp_model.OPTIMAL:
        senario_cost={'Items':[],'Assigned_to':[],'Item_cost':[],'Num_stops':0,'cost':[]}
        Total_Cost = solver.ObjectiveValue()
            
        for i in range(num_items):
            for j in range(num_shops):
                if solver.Value(x[i][j]) == 1:
                    senario_cost['Items'].append(i)
                    senario_cost['Assigned_to'].append(j)
                    senario_cost['Item_cost'].append(cost[i][j])
        senario_cost['Num_stops'] = len(set(senario_cost['Assigned_to']))
        senario_cost['cost'] = cost
        
        return Total_Cost,senario_cost
    else: return None, None

Output:

CpSolverResponse:
status: OPTIMAL
objective: 213
best_bound: 213
booleans: 210
conflicts: 106343
branches: 158796
propagations: 4242079
integer_propagations: 7844526
restarts: 878
lp_iterations: 0
walltime: 6.90529
usertime: 6.90529
deterministic_time: 4.67974
primal_integral: 0

CPU times: user 6.86 s, sys: 41 ms, total: 6.9 s
Wall time: 6.95 s

Upvotes: 1

Views: 979

Answers (1)

Laurent Perron
Laurent Perron

Reputation: 11064

When I run the supplied code on the master branch, without parallelism, I get:

CpSolverResponse:
status: OPTIMAL
objective: 213
best_bound: 213
booleans: 210
conflicts: 31
branches: 617
propagations: 5226
integer_propagations: 8220
restarts: 428
lp_iterations: 130
walltime: 0.021303
usertime: 0.021303
deterministic_time: 0.0011162
primal_integral: 0.00536794

Do you get a different result?

Upvotes: 1

Related Questions