elapsed time

[Tom van der Hoeven]

Hello,

I am using PULP for a network problem with flows and pressures.
The problem has 3000 variables, 2500 equations and 9000 non zeros.
The problem is solved in less than 0.5 second.
However setting it up with PULP takes more than 10 seconds.
I profiled it and here is the result.
Is there anything I can do to bring this time down

Tom

---------------------------------------

18597977 function calls (18595610 primitive calls) in 44.009
seconds

Ordered by: cumulative time

ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 44.009 44.009 <string>:1(<module>)
1 0.006 0.006 44.009 44.009 netber.py:17(netber)
25927 0.384 0.000 41.332 0.002 pulp.py:532(__init__)
2586 0.189 0.000 41.137 0.016 plpaa.py:3(__init__)
11502 0.029 0.000 40.295 0.004 pulp.py:595(copy)
3150 0.012 0.000 39.827 0.013 pulp.py:746(__add__)
25928 0.266 0.000 29.350 0.001 collections.py:58(__init__)
25928 4.168 0.000 28.972 0.001 _abcoll.py:483(update)
2868234 17.434 0.000 24.538 0.000
collections.py:76(__setitem__)
660 0.012 0.000 13.665 0.021 elementaa.py:249(lp)
354 0.008 0.000 12.705 0.036 elementaa.py:144(lp)
22069 6.462 0.000 11.416 0.001 _abcoll.py:368(items)
11470661 9.539 0.000 9.539 0.000 pulp.py:176(__hash__)
753 0.011 0.000 6.047 0.008 puntaa.py:23(lp)
228 0.002 0.000 4.905 0.022 elementaa.py:162(lp)
2973007 2.633 0.000 2.633 0.000 collections.py:97(__iter__)
62 0.002 0.000 2.397 0.039 elementaa.py:219(lp)
80 0.002 0.000 1.674 0.021 elementaa.py:61(lp)
18 0.002 0.000 1.498 0.083 elementaa.py:173(lp)

[Stuart Mitchell]

Looks like you are calling LpAffineExpression.__init__ ALOT 25927 times to be exact I would expect your code to call it once for each equation if you using the LpAffineExpression() function to generate them.

Let me have a look at the code either here or privately, and i could probably make some suggestions.

Stu

--
You received this message because you are subscribed to the Google Groups "pulp-or-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pulp-or-discuss+unsubscribe@googlegroups.com.
To post to this group, send email to pulp-or-discuss@googlegroups.com.
Visit this group at http://groups.google.com/group/pulp-or-discuss.
For more options, visit https://groups.google.com/d/optout.

--

Stuart Mitchell

PhD Engineering Science

Extraordinary Freelance Programmer and Optimisation Guru

www.stuartmitchell.com

[Tom van der Hoeven]

Stuart,

Problem solved!
Your first sentence brought me back to my own code.

I have a separable convex piecewise linear programming problem with equality constraints.
This means the cost function = sum_i f_i(x_i) and constraints are Ax=b

I have a converter who transforms this to a lp problem.
For each variable I start with cost = 0.0 and for each slope: cost += f_s * (lpvar_s - a_s)
having done so I do totcost += cost  (**)

I have changed this to cost = [] and for each slope cost += [ (lpvar_s, f_s) ]
having done so I do totcost += cost
At the end I use one LpAffineExpression(totcost) to bring it in one step to PULP

I think at (**) PULP each time evaluates totcost, which results in quadratic number of calls.
It is up to you to decide weather I misuse PULP or it is a flaw.

Anyhow, the problem is solved and I can continue using PULP.

Tom

Stuart Mitchell schreef op 15-3-2015 om 8:23:

To unsubscribe from this group and stop receiving emails from it, send an email to pulp-or-discu...@googlegroups.com.
To post to this group, send email to pulp-or...@googlegroups.com.

Visit this group at http://groups.google.com/group/pulp-or-discuss.
For more options, visit https://groups.google.com/d/optout.

--

Stuart Mitchell

PhD Engineering Science

Extraordinary Freelance Programmer and Optimisation Guru

www.stuartmitchell.com

--
You received this message because you are subscribed to the Google Groups "pulp-or-discuss" group.

To unsubscribe from this group and stop receiving emails from it, send an email to pulp-or-discu...@googlegroups.com.
To post to this group, send email to pulp-or...@googlegroups.com.

[Stuart Mitchell]

yeah using the += operator with pulp is really slow, as is using sum() instead of lpSum()

I think I need to emphasize this in the docs

Glad that it works

Stu

[Sasha A.]

Question, 

What's the alternative to using the += operator? 

Like should we be building up a list/dictionary of all possible constraints and then adding the list of constraints to the problem with a single += ? 

Can you give us an example of how this would work with 3 or 4 constraints? Like how would I go about building a list of LpExpressions that can be added to the problem? 

Thanks 

Sasha

[Stuart Mitchell]

Hi please continue to use += to add constraints to the problem.

Don't use += to build a constraint from variables.

To unsubscribe from this group and stop receiving emails from it, send an email to pulp-or-discuss+unsubscribe@googlegroups.com.
To post to this group, send email to pulp-or-discuss@googlegroups.com.

Visit this group at https://groups.google.com/group/pulp-or-discuss.

[Pedro Esmeriz]

I don't understand what you mean with "building the constraints" with += nor how to use the LpAffineExpression.

I understood the difference of using lpSum instead of sum(). but the += i did not. specially the part where you mentioned LpAffineExpression.

In my code, I make the following processes:
1.- create all variables
2.- create the objective function. In this processes I have several functions that will increment a variable, which , at the end, will be added to pulp:

my_lp_problem = pulp.LpProblem('Name', pulp.LpMinimize)
Function = 0 and i increment parcels of the objective function
my_lp_problem += Function, 'Z'

3.- I had the constraints. For the majority of these, I simply use:
my_lp_problem += c1*LpVariable1 + c2*LpVariable2 <=  100 (for example)

I think I am using the += as you suggested but I do not understand where should I use the LpAffineExpression()

thank you for your attention

[Stuart Mitchell]

Without seeing your code I really can help you but a summary of this thread would be

Avoid building _constraints_ like this

cons = LpAffineExpression()

#This use of += to build a constraint is very slow

for x in vars:

    cons += x

To unsubscribe from this group and stop receiving emails from it, send an email to pulp-or-discuss+unsubscribe@googlegroups.com.
To post to this group, send email to pulp-or-discuss@googlegroups.com.

Visit this group at https://groups.google.com/group/pulp-or-discuss.
For more options, visit https://groups.google.com/d/optout.

[Noam Zilo]

Hi

I am also having speed issues with setting the constraints.
I get what to AVOID.
but how SHOULD I add constraints?

this is my code - please tell me what's wrong with it. takes over 30 minutes to add 4000 constraints (~8500 variables)

# each constraint is: |pixel-expected-value - pixel-actual-value| < allowed_diff_between_targe_pixel_and_result
# which translates to 2 constraints:
# 1) sum(lines coefficients through pixel) < pixel-expected-value + allowed_diff_between_targe_pixel_and_result
# 2) sum(lines coefficients through pixel) < pixel-expected-value - allowed_diff_between_targe_pixel_and_result
for pixel_low_res_ind in range(num_of_low_res_pixels):
    print("setting constraint for low res pixel # ", pixel_low_res_ind, " out of ", num_of_low_res_pixels)
    pixel_low_res_x, pixel_low_res_y = ind2sub(image_low_res.shape, pixel_low_res_ind)

    constraint_1_name = "Constraint 1 for pixel " + str(pixel_low_res_ind)
    constraint_2_name = "Constraint 2 for pixel " + str(pixel_low_res_ind)

    #TODO this should be done for only the lines that pass through the pixel. how shall I know which ones?
    constraint_predicate_1 = lpSum([line_variables[str(j)] * lines_to_low_res_matrix[j][pixel_low_res_ind] for j in range(num_of_lines)]) \
                             <= image_low_res[pixel_low_res_x][pixel_low_res_y] + allowed_diff_between_targe_pixel_and_result
    # constraint_predicate_2 = lpSum([line_variables["line " + str(j)] * lines_to_low_res_matrix[j][pixel_low_res_ind] for j in range(num_of_lines)
    #                                 >= image_low_res[pixel_low_res_x][pixel_low_res_y] - allowed_diff_between_targe_pixel_and_result

    problem += constraint_predicate_1, constraint_1_name

[Pedro Esmeriz]

Hi there,

First, and this is only a python good practice, avoid string formation with '+'. Since python is interpreted, this consumes a lot more time, if you use format then the processing is faster (maybe +10%)

"Constraint 1 for pixel " + str(pixel_low_res_ind)

"Constraint 1 for pixel {0}".format(pixel_low_res_ind)

Nonethekess, why do you want a name on the constraint? I did not use this feature and I do not know if this is a major time component. 

If this is used to debug and detect issues on the formulation on a posterior stage, try adding an additional variable instead with a negative effect on the objetive function. (if max use - M.a1; if min use + M.a1, but watch out the size of M!)

With this, your model won't "break" if it turns out to be infeasible and you know precisely the constraint where this happened (and might also have a speed increase)

Time your code to detect this and other issues.

Second, I don't create the constraint and then add to the problem. i do "problem += var X * coef. + var Y * coef. <= constant" and this works out pretty fast for me.

Third and most importantly, you use crude loops in your code, which is normal since you are using lists. 

I would recommend using numpy arrays or even pandas dataframes. You might even accelerate your performance if you use vectorized functions.

Check numba library also. Since you are using PuLP to create this i do not know if Numba can increase performance but it worth the shot.

--
You received this message because you are subscribed to a topic in the Google Groups "pulp-or-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/pulp-or-discuss/p1N2fkVtYyM/unsubscribe.
To unsubscribe from this group and all its topics, send an email to pulp-or-discuss+unsubscribe@googlegroups.com.
To post to this group, send email to pulp-or-discuss@googlegroups.com.

Visit this group at https://groups.google.com/group/pulp-or-discuss.
For more options, visit https://groups.google.com/d/optout.

--

Pedro Esmeriz

[Daniela]

Hi Stuart,

sorry to come up with that question again, but from the discussion it's not clear to me, how to improve my code. It takes 12 seconds to add the following constraints to the problem.This is a code snippet (flow preservation constraints in a network flow problem):

 

for v in V:
    prob += lpSum([x[(v1, v2)] for (v1, v2) in A if v2 == v]) - lpSum([x[(v2, v1)] for (v2, v1) in A if v2 == v]) == 0

 I'd be glad if you could help me, thanks a lot. 

To unsubscribe from this group and stop receiving emails from it, send an email to pulp-or...@googlegroups.com.

To post to this group, send email to pulp-or...@googlegroups.com.
Visit this group at https://groups.google.com/group/pulp-or-discuss.
For more options, visit https://groups.google.com/d/optout.

--

[Franco Peschiera]

Hello Daniela,

This is more of a python performance issue.

In every iteration, you’re running two list comprehensions.
What you should do is first prepare your data that lets you do less iterations inside the loop (i.e., none).

For example:

# A_index_v1 => all arcs that start in node v
# A_index_v2 => all arcs that finish in node v
A = [(2, 3), (2, 6), (1, 2), (1, 3), (2, 5), (2, 7)]

A_index_v1 = {}
A_index_v2 = {}
for (v1, v2) in A:
    if v1 not in A_index_v1:
        A_index_v1[v1] = []
    if v2 not in A_index_v2:
        A_index_v2[v2] = []
    A_index_v1[v1].append((v1, v2))
    A_index_v2[v2].append((v1, v2))

for v in V:
    prob += lpSum([x[_tup] _tup in A_index_v2[v]]) - lpSum([x[_tup] _tup in A_index_v1[v]) == 0

Alternative using the pytups library:

import pytups as pt

A_index_v1 = pt.TupList(A).to_dict(result_col=[0, 1], indices=[0])
A_index_v2 = pt.TupList(A).to_dict(result_col=[0, 1], indices=[1])

for v in V:
    prob += lpSum([x[_tup] _tup in A_index_v2[v]]) - lpSum([x[_tup] _tup in A_index_v1[v]) == 0

Franco

[Daniela]

Thanks a lot, that's great advice!