3
$\begingroup$

I have a set of many similar linear programs (LP). All these LPs have the same objective function, and almost all constraints are the same. The only difference is for one linear constraint $f(x)=a_{i}$, where $a_{i}$ is a constant that changes from one LP to the next. Instead of solving each LP from scratch, I am trying to use the information from the first LP problem to solve the other LPs more quickly.

Thanks to this conversation, I was told that this kind of change preserves dual feasibility, so I should apply the dual simplex method with a warm start from the previous optimal basis.

Based on this suggestion, I was trying to iteratively warm start LP number $i$ with the optimal solution from LP number $(i-1)$. Concretely, I was using the following steps using PuLP with Gurobi:

  • Update the only constraint that changes in the LP: prob.constraints['cst_a'] += a[i-1] - a[i]
  • Set the initial value to all LP variables: for t in ts: varProb[t].setInitialValue(optimalVarPreviousProb[t])
  • Solve the new LP using warm start and dual simplex: prob.solve(pulp.GUROBI_CMD(logPath="LogFile.log", warmStart=True, options=[("method",1)]))

However, I was surprised to see that the total computation time did not decrease. If anything, it actually increased slightly (certainly due to the extra time to set initial values).

I compared the log files with and without warm starting the problem, and the number of dual simplex iterations for each LP is exactly the same. In other words, it looks like the warm starting did not do anything.

Actually, the log file does not seem to acknowledge any warm starting. But when I use warm start with MILP problems, the log file does acknowledge the use of a "User MIP start". Does that mean LP warm start does not work with PuLP and/or Gurobi?

Any other idea what I could be doing wrong?

Improve this question
$\endgroup$
4
  • $\begingroup$ Update: I tried the same process using gurobipy instead of PuLP and the warm start does work! I only have to do cst_a.rhs = a[i] and model.update(). This is simpler because I do not even have to set the initial values, the gurobi model "remembers" the last solution. However, I would still be interested to know how to do it in PuLP $\endgroup$
    – Quentin PLOUSSARD
    Commented Dec 13, 2023 at 17:57
  • $\begingroup$ Are you warm starting using a primal infeasible solution or a basis corresponding to the solution? $\endgroup$
    – Sune
    Commented Dec 15, 2023 at 20:58
  • $\begingroup$ The solution I am using for warm start was feasible (and optimal) in the previous LP but infeasible in the new LP. This is because it satisfied the previous equality constraint f(x) = a_(i-1) but it does not satisfy f(x)=a_i. But it has the same objective function so it is dual feasible in both LP. $\endgroup$
    – Quentin PLOUSSARD
    Commented Dec 16, 2023 at 21:10
  • $\begingroup$ You also don't need your second bullet in pulp if you are calling the same model object. The values will be set to whatever the solved solution was in the prior iteration. This shows warmstart for CPLEX, but is an example of subtour elimination constraints using pulp, github.com/apwheele/PatrolRedistrict/blob/master/DataCreated/…. $\endgroup$
    – Andy W
    Commented Dec 17, 2023 at 16:48

1 Answer 1

Reset to default
2
$\begingroup$

You typically don't warmstart LPs by providing a start solution. This is mostly done for MIPs to get a quick incumbent solution. For LPs, you need to provide the basis information and ideally have some more internal data structures available (like the basis factorization). When you don't throw away everything after one optimization and just alter some model data, all this is readily available and the solver should use this for warmstarting based on the previous optimization.

With a third-party tool like PuLP, you need to be careful to preserve that information. It may happen that everything is discarded and every new optimization is treated as a completely new task without any information from previous runs. So, using gurobipy directly is a much better approach and provides much more control over what actually happens or should be happening.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for your reply. That makes sense. In other words, it is better to use the python library made for a specific solver like gurobipy. Now, is there another solver/python library that can do the same thing (starting from a specific basis)? $\endgroup$
    – Quentin PLOUSSARD
    Commented Dec 18, 2023 at 14:11
  • $\begingroup$ www.mosek.com is one alternative. See docs.mosek.com/latest/pythonapi/tutorial-reoptimization.html $\endgroup$
    – ErlingMOSEK
    Commented Dec 18, 2023 at 15:28
  • $\begingroup$ In fact, I suppose almost every decent Simplex-based LP solver out there has the capability to start from a given basis. $\endgroup$
    – mattmilten
    Commented Dec 18, 2023 at 17:12
  • $\begingroup$ In theory yes. In practice it is hard to find one with free license $\endgroup$
    – Quentin PLOUSSARD
    Commented Dec 19, 2023 at 19:46
  • $\begingroup$ You can check the public benchmarks (mattmilten.github.io/mittelmann-plots) for other options. $\endgroup$
    – mattmilten
    Commented Dec 20, 2023 at 8:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.