Slow adding constraints about cylp HOT 10 CLOSED

I think the main reason it's slow is because your creating the variables one by one. If you create them at once it'll be much MUCH faster. So instead of saying:

for n in range(0, 20):
a = s.addVariable('a_{}'.format(n), 1, isInt=False)
s += 0.0 <= a <= ((n+1) * 10)
b = s.addVariable('b_{}'.format(n), 1, isInt=True)
s += (-(n+1) * 10) * b + a <= 0

You could say:

a = s.addVariable('a', 20, isInt=False)
b = s.addVariable('b', 20, isInt=True)
s += 0 <= b <= 1 # To make them binary
for n in range(0, 20):
s += 0.0 <= a[i] <= (n + 1) * 10
s += (-(n+1) * 10) * b[i] + a[i] <= 0

Also, as a general rule, modelling using numpy arrays are preferred to using Python loops to add constraints, of course, if that option is available. For example in your case you could say:

import numpy as np
a = s.addVariable('a', 20, isInt=False)
b = s.addVariable('b', 20, isInt=True)
s += 0 <= b <= 1 # To make them binary
myarray = np.arange(10, 201, 10) # Or any other way to create your vector
s += 0.0 <= a <= myarray # This is 20 LP constraints
s += -myarray * b + a <= 0.0 # another 20 constraints

notice that the loop completely disappeared.

On top of all this, to make your modelling process even faster, you may use CyLPModel to create your model and then create a CyClpSimplex using it. You may find an example at:
http://mpy.github.io/CyLPdoc/modules/modeling.html (look at the second modelling example)

I hope this makes your modelling fast enough. Please let me know how much speedup you get after these modifications...

from cylp.

Oh, and please don't forget (as I did) to convert "myarray" to CyLPArray. Otherwise it won't work:

from cylp.py.modeling.CyLPModel import CyLPArray
.
.
myarray = CyLPArray(np.arange(10, 201, 10))
.
.

from cylp.

Thanks for your help @mpy. It's taken a little effort to refactor my code, but it is working now.

I'm using CyLP to solve many relatively small/quick problems, using the multiprocessing module to run 16 instances concurrently (on an 8 core machine). It really rips through the problems.

Is there a way to disable the terminal output from CBC? It's not readable anyway (as it's all mixed up between the different processes), and it's probably adding a bit of overhead just displaying it.

from cylp.

I'm glad I could help and happy to hear it's working much faster. Btw, I'm curious to know what type of problem your trying to solve using CyLP/CBC, of course if it's not confidential. You could also email me if that works better.

I can imagine how CBC log looks like in your parallel setup! You could disable it by setting logLevel to 0:

cbcModel.logLevel = 0

from cylp.

The model seeks to maximise the benefit of transfering water (the volume variable), where benefit is defined as the value in transfering the water minus the cost of doing so. There are both variable and fixed costs, hence the need for the binary variables. The problem has a spatial element, and the relationships between variables are extracted from a GIS (Geographic Information Systems) layer.

Now that I've turned the logging off can see a some warnings raised by CyLP/numpy.

    var_volume = s.addVariable('volume', num_options, isInt=False)
  File "CyClpSimplex.pyx", line 1357, in cylp.cy.CyClpSimplex.CyClpSimplex.addVariable (cylp/cy/CyClpSimplex.cpp:19281)
  File "CyClpSimplex.pyx", line 1891, in cylp.cy.CyClpSimplex.CyClpSimplex.loadFromCyLPModel (cylp/cy/CyClpSimplex.cpp:27324)
  File "CyCoinPackedMatrix.pyx", line 30, in cylp.cy.CyCoinPackedMatrix.CyCoinPackedMatrix.__cinit__ (cylp/cy/CyCoinPackedMatrix.cpp:1421)
FutureWarning: comparison to `None` will result in an elementwise object comparison in the future.

This seems to relate to this line: https://github.com/coin-or/CyLP/blob/master/cylp/cy/CyCoinPackedMatrix.pyx#L30

Should that be if rowIndices is None?

from cylp.

Very interesting. Thanks a lot for sharing. Good luck!

You're right about the source of the warning. That's my bad. I'll push a fix tomorrow.

from cylp.

I'm still not getting performance quite the same as the CBC standalone binary, only with the solution now rather than the problem generation. Is there an easy way to get CyLP to solve using the same defaults that the CBC binary uses? I've tried adding the various cuts (see code below). The binary solves in a couple of seconds ($ cbc problem9.lp), whereas the code below takes at least a couple of minutes (then I kill it...).

The problem I've been testing with is here:
http://snorf.net/problem9.lp

#!/usr/bin/env python

import numpy as np
from cylp.cy import CyClpSimplex
from cylp.py.modeling.CyLPModel import CyLPModel, CyLPArray
from cylp.cy.CyCgl import *

filename = 'problem9.lp'

s = CyClpSimplex()
s.readLp(filename)

status = s.primal()
print status

cbcModel = s.getCbcModel()

# add cut generators
probe = CyCglProbing()
cbcModel.addCutGenerator(probe, name="Probing")
gom = CyCglGomory()
cbcModel.addCutGenerator(gom, name="Gomory")
knap = CyCglKnapsackCover()
cbcModel.addCutGenerator(knap, name="Knapsack")
clq = CyCglClique()
cbcModel.addCutGenerator(clq, name="Clique")
mir2 = CyCglMixedIntegerRounding2()
cbcModel.addCutGenerator(mir2, name="MixedIntegerRounding2")
flowcover = CyCglFlowCover()
cbcModel.addCutGenerator(flowcover, name="FlowCover")
twomir = CyCglTwomir()
cbcModel.addCutGenerator(twomir, name="TwoMir")

status = cbcModel.branchAndBound()
print status

Should I be passing more options to the cut generators? Or am I missing something else?

from cylp.

There's a method called solve() that does the CBC magic for your problem. You may call it instead of branchAndBound(). This way you should be able to reproduce the same performance as when you call CBC's executable. And you no longer need to add additional cuts.

from cylp.

The solve method doesn't appear to respect cbcModel.logLevel = 0.

from cylp.

I just fixed this issue in master (see 0c95945). This has not made it to a release yet, but I guess it will soon.

from cylp.