How many variables pulp can handle in reasonable time?

[Alexey Voevodkin]

Hello Everybody!

.

I understand my question is ambiguous - а lot of depends on the task and the program and what to call reasonable time.

I just want to hear something like that:

I solved my task with 100 000 variables with pulp for 1hour or for 24 hours using laptop with 8G RAM and 2.1GHz.

Please share the real experience.

In my case, the construction of the objective function takes around 23 minutes for 32000 variables.

So, for 30 times more variables  I expect it will take more than 12 hours.

[Stuart Mitchell]

Can you give the code that you are using to construct your objective that seems too long

Stu

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

[Alexey Voevodkin]

Hi Stuart,

Indeed, 23 minutes for 32000 vars  is too long.

Now the problem is solved. It takes seconds to build objective function for ~76000 vars.

Let me not showing my shitty initial code. For newbies like me here is the code that works for me:

totcost = plp.LpAffineExpression()
i = 0
for h in hub:
    for t in tran:
        for d in dc:
            for m in model:
                totcost += cost.loc[(h, d), t] * x[(h, t, d, m)]  # x - decisoin vars
               
                if i%1000 == 0: print(i, end=", ")
                i += 1

prob += totcost

prob.solve()

Conclusion:

The real live problem for ~76000 vars may be solved with pulp for less than 30 seconds (default solver).

[Richard Tabassi]

I have some scheduling problems I am currently doing that are exceeding 300K variables and tens of thousands of constraints.  On my laptop it was taking ~45 minutes to write the problem prior to solving.

The solve had been quick, but I tightened some constraints and now getting a good deal of trouble solving anything, let alone in a reasonable time.  ~ sub hour.  I may need to reduce it down and accept more inefficiency.  Too long to write, too long to attempt to solve.

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 https://groups.google.com/group/pulp-or-discuss.
For more options, visit https://groups.google.com/d/optout.

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

[Mixit Sheth]

Hi,

I got a similar problem about running an optimization problem for scheduling in healthcare setting. Default CBC solver of PuLP is taking 180 min in total. I have approximately 5k variable and 2k constraints. What changes in the code should I follow to reduce the total time using CBC?

Here, is the python code

import pandas as pd
from pulp import *

# Indices
chair = list(range(1, 24))
pat_type = list(range(1, 7))
slot = list(range(1, 21))
type_and_demand = {1: 28, 2: 11, 3: 14, 4: 8, 5: 15, 6: 1}
type_and_slots = {1: 1, 2: 2, 3: 4, 4: 6, 5: 10, 6: 12}

# Variables
Y = LpVariable.dicts("BeginTreatment", (chair, pat_type, slot), 0, 1, LpBinary)
X = LpVariable.dicts("ContinueTreatment", (chair, pat_type, slot), 0, 1, LpBinary)

# Objective Function
model = LpProblem("ChairUtilization", LpMaximize)
model += lpSum([Y[i][j][t] for i in chair for j in pat_type for t in slot])

# Only  5 patients can begin treatment at 1st slot
#model += lpSum([Y[i][j][t] for i in chair for j in pat_type for t in range(1, 2)]) <= 5

# Patient Type 1 Continuity constraint
model += lpSum([X[i][j][t] for i in chair for t in slot for j in range(1, 2)]) == 0

# No new arrivals during lunch time period
model += lpSum([Y[i][j][t] for i in chair for j in pat_type for t in range(10, 12)]) == 0

# Patient Mix
for j in pat_type:
    model += lpSum([Y[i][j][t] for i in chair for t in slot]) >= type_and_demand[j]

# No more than one patient per chair
for i in chair:
    for t in slot:
        model += lpSum([X[i][j][t] for j in pat_type]) + lpSum([Y[i][j][t] for j in pat_type]) <= 1

# No Nurse overtime
for j in range(2, len(pat_type) + 1):
    model += lpSum([Y[i][j][t] for i in chair for t in range(len(slot) - type_and_slots[j] + 2, len(slot) + 1)]) == 0

# Chair continuity constraint
for i in chair:
    for j in range(2, len(pat_type) + 1):
        for t in range(1, (len(slot) - type_and_slots[j] + 1) + 1):
            model += lpSum([X[i][j][u] for u in range(t + 1, t + type_and_slots[j])]) >= (type_and_slots[j] - 1) * \
                     Y[i][j][t]

#print(model)
# Solving the model
model.solve()

# Output the results of the model
output = []
for variable in model.variables():
    if variable.varValue == 1.0:
        print(variable.name, "=", variable.varValue)
        output.append(variable.name)

Any help would really be appreciated.

[Stuart Mitchell]

I would replace your chair continuity constraint with a set partitioning formulation

See the wedding planning example

Stu

Stuart Mitchell

PhD Engineering Science

Extraordinary Freelance Programmer and Optimisation Guru

www.stuartmitchell.com

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.

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

[Mixit Sheth]

Hi Stu,

I went through the example, but it looks really tough to me. Could you help me make chair continuity constraint as set partitioning formulation as I'm new to PuLP and optimization

[Stuart Mitchell]

I didn't really look at your formulation.

In general you a priori generate all possible/ reasonable sequences for each chair. i.e at the worst case 7 pattern types and 21 slots 7 ** 21 variables (this is the hard bit)

Then make a constraint stating that you only what 24 schedules to be selected (1 per chair)

Stu

Stuart Mitchell

PhD Engineering Science

Extraordinary Freelance Programmer and Optimisation Guru

www.stuartmitchell.com

On Mon, Aug 6, 2018 at 11:56 AM, Mixit Sheth <sheth0...@gmail.com> wrote:

Hi Stu,

I went through the example, but it looks really tough to me. Could you help me make chair continuity constraint as set partitioning formulation as I'm new to PuLP and optimization

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.

--
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 https://groups.google.com/group/pulp-or-discuss.
For more options, visit https://groups.google.com/d/optout.

--
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 https://groups.google.com/group/pulp-or-discuss.
For more options, visit https://groups.google.com/d/optout.

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

[Prabhat Kumar]

Rather than solving at once. divide the problem and solve in chunks.