Originally posted by: Olivia.w

Hi.

I am very new to Python and trying to build up my first model by Cplex Python API.

At first, everything goes well when I test small-scale instance.

But it takes too long to build up an MIP model when I test my large-scale instances.

Then I searched previous topics here and have tried to build a map between my constraints' names and indices.

It seems that the procedure of creating the model have been seeped up a little bit.

But, I think it is still very slow since I used to test the same instance using C++.

Below is part of constraints and one of my variables.

Is there anything I can do to further speed up the procedure of creating a model using Python?

Thanks a lot.

 

__IP_model = cplex.Cplex()

__IP_model.objective.set_sense(__IP_model.objective.sense.maximize)

#

# constriants

__myrhs_cons1 = [1] * Parameters.n_order

__myconsname1 = ["cons1{}".format(i + 1) for i in range(Parameters.n_order)]

__myrhs_cons2 = flatten(TruckClass.slots_overt)

__myconsname2 = ["cons2{}{}".format(j + 1, t + 1) for j in range(Parameters.n_truck) for t in

                 range(Parameters.n_type)]

__myrhs = __myrhs_cons1 + __myrhs_cons2

__myconsname = __myconsname1 + __myconsname2

__mysense = 'L' * len(__myrhs)

__IP_model.linear_constraints.add(rhs=__myrhs, senses=__mysense, names=__myconsname)

__name2ind = {n : k for k, n in enumerate(__IP_model.linear_constraints.get_names())}

#

# columns

# x[i][j]

for i in range(Parameters.n_order):

    for j in range(Parameters.n_truck):

        __IP_model.variables.add(obj=[Parameters.alpha * OrderClass.value[i]], lb=[0], ub=[1],

                                 types=[__IP_model.variables.type.integer],

                                 names=["x{}{}".format(i + 1, j + 1)],

                                 columns=[cplex.SparsePair(ind=[__name2ind["cons1{}".format(i + 1)]] + [__name2ind[

                                     "cons2{}{}".format(j + 1, t + 1)] for t in

                                     range(OrderClass.type[i])],

                                                           val=[1] + [1 for t in range(OrderClass.type[i])])])

 

#CPLEXOptimizers
#DecisionOptimization

The following things come to mind:

1. Don't create variables one by one. Instead create them in chunks. For example, create all n_truck variables for a fixed i with a single call to variables.add(). Or even create all variables with a single call to variables.add().
2. In SparsePair(ind = [__name2ind["cons1{}".format(i+1)] ...  it seems inefficient to create a string just for indexing. If you do offset = __IP_model.linear_constraints.get_num() right before calling linear_constraints.add() then the index of the constraint you are seeking here is just offset+i (no string, no lookup required). Similarly for cons2.
3. You have [1 for t in range(OrderClass.type[i])]. It might me faster and slightly less obscure to just do [1] * range(OrderClass.type[i])

I am not sure these things will speed up things a lot but they are the first things I'd try to make that code faster.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Olivia.w

Thank you very much for your reply. I will try the things as you suggested. Hopefully they will work. 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Lmuno

Hello Daniel/olivia,

I'm having performance issues with my large scale model during the building phase using python + Cplex API.

 

I'm providing an example of the constraint that slows down my model since requires 4 nested loops of approximately o(n^4) where n=200.  If I use n=100 it takes about 7 minutes for this constraint to be generated while the model is taking under 2 to minutes to solve.

I believe linear_constraint.add is the bottleneck since I'm able to speed up the code from 7 min to .2 min if I replace the  c.linear_constraints.add function with a simple array c_linear_constraints.append[]. For example:

c.linear_constraints.add(lin_expr= [cplex.SparsePair(ind = ["x"+str(j_row)+'_'+str....

is replaced with  

c_linear_constraints=[]

c_linear_constraints.append(["x"+str(j_row)+'_'+str(m_row)+'_'+str...

 

Copy of the code of this constraint:

Copy of the code- appends to an array in python (fast) 

        c_linear_constraints=[]
        for t in range(1,makespan+1):

            for m_row in m:
                #SUM OF: THIS COLUMN MUST BE WHERE WE add linear constraints
                cnt=0
                for j_row in j:
                    cnt+= len(range(max(max(1,int(set_job[j_row-1][2])),int(t - set_job[j_row-1][7] +1)), min(t+1,int(int(set_job[j_row-1][3]) - set_job[j_row-1][7] +1))))

                c_linear_constraints.append(["x"+str(j_row)+'_'+str(m_row)+'_'+str(t_) for j_row in j for t_ in range(max(max(1,int(set_job[j_row-1][2])),int(t - set_job[j_row-1][7] +1)), min(t+1,int(int(set_job[j_row-1][3]) - set_job[j_row-1][7] +1)))])
 

         

Copy of the same code using cplex API (very slow) 

        for t in range(1,makespan+1):

            for m_row in m:
                #SUM OF: THIS COLUMN MUST BE WHERE WE add linear constraints
                cnt=0
                for j_row in j:
                    cnt+= len(range(max(max(1,int(set_job[j_row-1][2])),int(t - set_job[j_row-1][7] +1)), min(t+1,int(int(set_job[j_row-1][3]) - set_job[j_row-1][7] +1))))
                
                    c.linear_constraints.add(lin_expr= [cplex.SparsePair(ind = ["x"+str(j_row)+'_'+str(m_row)+'_'+str(t_) for j_row in j for t_ in range(max(max(1,int(set_job[j_row-1][2])),int(t - set_job[j_row-1][7] +1)), min(t+1,int(int(set_job[j_row-1][3]) - set_job[j_row-1][7] +1)))], 
                                                                                val = [1]*cnt)] , 
                                                                                senses=["L"],
                                                                                rhs=[1],
                                                                                names=["c3_t_"+str(t)+"_m_"+str(m_row)])
 

I would appreciate your guidance on how to speed building the model. Is it possible to create the model as text file and then rename it to *.lp?

#CPLEXOptimizers
#DecisionOptimization

Hello Luis,

For starters, give the following tips a try:

1. Use indices instead of names. For example, keep a dictionary that maps names to indices and use the indices in the SparsePair ind list rather than names.
2. Add constraints in a batch rather than one at a time. That is, build up the argument lists in the loop (e.g., a list of SparsePair objects, etc.) and then just call c.linear_constraints.add once.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Lmuno

Hello Ryan,

Thanks for the quick reply. I need to try suggestion 1. I believe I'm batching as much as I can (I batch 2 out of 4 indices). I need to think harder to figure out if I can batch all the 4 indices.

btw, is there a way to create the model in memory (RAM) then write it to a text file *.lp. then call the model to solve the *.lp file?

#CPLEXOptimizers
#DecisionOptimization

In order to add you constraints in batches you don't have to batch indices. You can just have an array, add the constraints to the array instead of calling add_linear_constraints() and whenever the size of the array exceeds a threshold (say for example 10000) then you call add_linear_constraints() with all constraints in the array (and clear the array afterwards).

But I think that using indices instead of names should already give you a performance boost.

In order to write the model to a file use Cplex.write().

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Lmuno

Thank you Daniel, this is a good tip. I will attempt to write all my constraints in arrays first, then call the add_linear_constraints() when the array exceeds a threshold.

Thanks again to both of you Ryan and Daniel.

#CPLEXOptimizers
#DecisionOptimization