LinExpr.add_var / LinExpr.add_expr / LinExpr.add_term are way too slow

[jachymb]

Consider the following function. It generates and solves a model structurally somewhat similar to a practical problem I am solving. (I tried to simplify it as much as possible)

def experiment_mip(n):
    start = time.time()

    model = mip.Model(sense=mip.MAXIMIZE, solver_name=mip.CBC)
    obj = []
    for i in range(n):
        var = model.add_var(f"var_{i}", lb=0.5, ub=1.0)
        a = random.random()  - 0.5  # Just a dummy value for illustration
        obj.append(var * a)
        constraint = mip.xsum(obj) <= 1.0
        model.add_constr(constraint, f"constraint_{i}")
    model.objective = mip.xsum(obj)

    construction_time = time.time() - start
    start = time.time()

    model.optimize()

    solution_time = time.time() - start
    return {"Model construction time": construction_time, "Solution time": solution_time}

Now, try running this for example for n=4000. The solution is much faster than the construction of the model. My measurements suggest that the solution time is asymptotically O(n^2) complexity but the construction is more than O(n^3). The profiler shows that that most time is spent in the LinExpr.add_var, LinExpr.add_expr and LinExpr.add_term functions. I think this is not acceptable and it should never take more time to construct than to solve a nontrivial problem.

I am not sure what the solution could be.

[jachymb]

Possibly related to #146

[h-g-s]

Hi,

I agree that this needs to be optimized, but remember that the model is created in an interpreted, dynamic language and it is solved using highly optimized native machine code.

If I remember correctly, the culprit here is

Xsum

    LinExpr.add_term

More specifically lines

        if isinstance(term, Var):

            self.add_var(term, coeff)

        elif isinstance(term, LinExpr):

            self.add_expr(term, coeff)

        elif isinstance(term, numbers.Real):

            self.add_const(term)

        else:

in entities.py 280

This is slow since before adding each term to the LinExpr it needs to check its type, it can be a constant, a variable, another LinExpr… This makes easy to build models but also makes it slow.

A faster approach would be to have a more “low level” way of creating constraints, i.e. using constraint indexes and coefficients both as numpy arrays (or cffi arrays). The code would be uglier and more verbose (like C code) but definitely much faster.

Cheers

From: Jáchym Barvínek notifications@github.com Reply-To: coin-or/python-mip reply@reply.github.com Date: Sunday, November 22, 2020 at 3:42 PM To: coin-or/python-mip python-mip@noreply.github.com Cc: Subscribed subscribed@noreply.github.com Subject: [coin-or/python-mip] LinExpr.add_var / LinExpr.add_expr / LinExpr.add_term are way too slow (#163)

Consider the following function. It generates and solves a model structurally somewhat similar to a practical problem I am solving. (I tried to simplify it as much as possible)

def experiment_mip(n):     start = time.time()

    model = mip.Model(sense=mip.MAXIMIZE, solver_name=mip.CBC)     obj = []     for i in range(n):         var = model.addvar(f"var{i}", lb=0.5, ub=1.0)         a = random.random()  - 0.5  # Just a dummy value for illustration         obj.append(var * a)         constraint = mip.xsum(obj) <= 1.0         model.addconstr(constraint, f"constraint{i}")     model.objective = mip.xsum(obj)

    construction_time = time.time() - start     start = time.time()

    model.optimize()

    solution_time = time.time() - start     return {"Model construction time": construction_time, "Solution time": solution_time} Now, try running this for example for n=4000. The solution is much faster than the construction of the model. My measurements suggest that the solution time is asymptotically O(n^2) complexity but the construction is more than O(n^3). The profiler shows that that most time is spent in the LinExpr.add_var, LinExpr.add_expr and LinExpr.add_term functions. I think this is not acceptable and it should never take more time to construct than to solve a nontrivial problem.

I am not sure what the solution could be.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or unsubscribe.

[rschwarz]

I guess that in many situations, the modeler would input constraints in sum notation, knowing that no variable appears twice, and every term is of the form coefficient * variable. In this case, it would make sense to offer an alternative constructor to LinExpr that takes in a dict or a list of tuples.

This would not provide nice-looking algebraic syntax, but it avoids many dictionary operations as well as the isinstance calls.

[christian2022]

With these minor changes (see ###), on my laptop construction time is 1/3 of solution time for n = 4000

def experiment_mip(n):
    start = time.time()

    model = mip.Model(sense=mip.MAXIMIZE, solver_name=mip.CBC)
    obj = LinExpr() ### do not build array of LinExpr but directly append to LinExpr
    for i in range(n):
        var = model.add_var(f"var_{i}", lb=0.5, ub=1.0)
        a = random.random()  - 0.5  # Just a dummy value for illustration
        obj.add_var(var, a) ### do not create intermediate LinExpr
        constraint = obj <= 1.0 ### no need to mip.xsum as obj is already the sum
        model.add_constr(constraint, f"constraint_{i}")
    model.objective = obj

    construction_time = time.time() - start
    start = time.time()

    model.optimize()

    solution_time = time.time() - start
    return {"Model construction time": construction_time, "Solution time": solution_time}

[hadware]

Super interesting ! That's a pretty nice solution, I'll try to find some time to hack this into the package.

[tuliotoffolo]

Nice, @christian2022! I like this code and that's why we reintroduced inplace operations for LinExpr, so that you could also write obj += a * var (of course this would create an intermediate LinExpr).

Anyhow, I agree that it would be useful to have something like an alternative LinExpr constructor that takes a dict or a list of tuples.

[tuliotoffolo]

I've just included a test considering 5 variations of the code @jachymb and @christian2022 posted here. The test example is available in this link and here are the 'construction' runtimes I got with n=10000:

using_addvar: 9.426069974899292
using_inplace_op: 9.878501176834106
using_dict: 11.112802028656006
using_lists: 14.583881855010986
recreating_linexpr: 74.6143479347229

@rschwarz: you can now create a LinExpr from a dictionary or two lists (variables and coeffs).