search

coin-or / pulp

A python Linear Programming API
http://coin-or.github.io/pulp/
Other
2.01k stars 376 forks source link

Using a warm start to speed up the solution of various sub-problems? #702

Closed SaVoAMP closed 6 months ago

SaVoAMP commented 8 months ago

Hey!

I work with time series data and try to fit polynomials there. To do this, I rewrote my problem in a linear program that minimizes the absolute error between the polynomial and the measured data. Now I'm trying to find out if I can use the warm start to solve a bigger problem if I've already solved a subproblem of that bigger problem, and I especially want to find out if I can solve the bigger problem faster than if I have to recalculate everything from scratch.

To make the whole thing a little easier to understand and more concrete: Suppose I have a vector of length 10 that contains my measurement data. Then I solve the linear program for this and get my fitted polynomial. If another data point is added, my vector has length 11 and I have to solve a new linear program. Since I assume that the calculated polynomial will hardly change with only one additional data point - and consequently only one additional equation in the linear program - it seems plausible that I can reuse the result calculated for the 10 points in order to accelerate the result for the 11 points by means of a warm start and not have to solve the problem for the 11 points completely from scratch again.

To find out whether this assumption proves to be true, I use the solver PULP_CBC_CMD, as it offers the warm start option. Now, however, it is somewhat difficult to get a reliable answer as to whether the warm start brings an acceleration or not. On the one hand, I can of course measure the runtime that the solver needs with and without a warm start. However, another indication could be that the solver requires a different number of iterations to obtain the optimal solution.

Now I ask myself the following questions: 1) Has anyone already dealt with this problem and knows whether the WarmStart actually brings a runtime gain here? 2) Is there an easy way in PuLP to get the iterations needed to solve the linear program? I have seen that this information is displayed in the console when the flag msg=True is set in the solver. Is there any easier way to get this information than using RegEx to examine the console output?

Thank you very much in advance and I would be very happy to receive a helpful answer!

pchtsp commented 6 months ago

Hello!

  1. It will heavily depend on the solver and the problem. And luck. CBC's warm start functionality is very sensitive to having a complete solution. Gurobi or CPLEX are more friendly and robust.
  2. You can write the log to a file by filling the logPath argument to the solver. If you want to interpret the log, I recommend https://github.com/pchtsp/orloge which does regex on the logs of some solvers and returns a friendlier format.

Feel free to reach out again through the Discussions page for more information.