More efficient resolve when change in objective function only

[rsjeffers]

Describe the new feature

For decomposition problems where we need to solve the same optimisation problem iteratively with a slight change in the objective function each time, having writeLP in actualSolve makes this very computationally inefficient. For cplex we have the cplex_py version, but this still has a rather costly "buildSolverModel" each time we call "actualSolve", rewriting the model each time even if we are only changing the objective function.

I was wondering whether it would be possible to have an option that separates "buildSolverModel" from "actualSolve" so that we can change the objective function and resolve without rewriting the whole problem? I'd be quite happy starting off with cplex, and maybe going on to other solvers that currently only have the writeLP option?

Thanks in advance :)

Example problem: I would like to use pulp as the modelling language for a decomposition problem, for example: The optimisation problem is:

x_i is a one dimensional vector of any size and X_i is the domain of x_i.

I dualise the equality constraint so that I can decompose the problem, so for each i I have the following smaller problem:

Where \lambda is the dual variable associated with the equality constraint in the frontal problem.

I update \lambda iteratively using gradient descent.

Additional info

Please answer these questions before submitting your feature request.

Is your feature request related to an issue? Please include the issue number.

Not as far as I can tell

Does this feature exist in another product or project? Please provide a link.

It exists in a modelling language used at my company that is in C++ and currently not open source.

[pchtsp]

Hello, thanks for the suggestion, which is definitely relevant.

There are many parts to the answer.

First of all, are you sure the time is spent in the writing of the file / preparation of the model? I'm guessing you've profiled the code? In my experience, some cases of decompositions built with pulp do have the model building as the bottleneck, but many other times it's somewhere else (the pulp formulation, the solver, etc.).

If indeed it's the writing of the LP problem, there are still several possibilities, as you mentioned.

For solvers that use the official python API (CPLEX_PY, GUROBI, MOSEK) (i.e., that do not write a file to disk), one option is to edit the internal model, manually. To do this, you have to access the solverModel inside the problem. There, you can play with the solver official api and edit the objective function. Do note that this does not avoid the internal time of the solver api.

So here, you'd do something like:

import pulp as pl

prob = pl.LpProblem(name, const.LpMinimize)
        x = pl.LpVariable("x", 0, 4)
        y = pl.LpVariable("y", -1, 1)
        z = pl.LpVariable("z", 0, None, const.LpInteger)
        prob += 1.1 * x + 4.1 * y + 9.1 * z, "obj"
        prob += x + y <= 5, "c1"
        prob += x + z >= 10, "c2"
        prob += -y + z == 7.5, "c3"

solver = pl.CPLEX_PY()

prob.solve(solver)

# now you have the model into CPLEX format, you can edit it
# for example, you change the sense of the objective:
prob.solverModel.objective.set_sense(
    prob.solverModel.objective.sense.minimize
)

# then you can solve it again without rebuilding:
solver.callSolver(prob)

# you manually retrieve the values of the variables:
solver.findSolutionValues(prob)

For solvers that use LP / MPS files, you have the option of using a ram disk (I've read of people using that in the google group) to speed up the I/O. I have never personally need that.

If you want something better / easier / faster: any proposal is more than welcome. Including adding to the PuLP docs these existing possibilities.

[rsjeffers]

Hi thanks for the reply :)

Yes I profiled the code and in my example the time was being spent in the writing of the file/prep of model... though this was a while ago so I'll run the profiler again using a more recent version of pulp.

Your workaround for the solvers that use the official API is great! I'll update the docs with your solution and maybe add a simpler function for modifying the objective function as another PR.