12

I'm working on an mid-sized linear program (70k x 10k sparse constraint matrix) and need to run a large number of scenarios, requiring ~2,000 CPU-hours at my current solve time. Because the changes are relatively minor (changing at most ~10% of the objective function, aka c matrix), using a warm start could significantly speed up solution times, but I have not been able to find a fast warm-start LP solver in Python.

I have been working to date with linprog in Matlab and the CVXOPT lp solver in Python, with the best performance using the GLPK simplex solver within CVXOPT. However, the CXVOPT wrapper for GLPK does not implement a warm start, even though a warm start is possible using GLPK. While CVXOPT supports warm start in its native conelp solver, this is significantly slower than a cold start in GLPK. I have not been able to find warm start options in PuLP or other references to warm starts in Python modules.

Does anyone have experience adapting/patching CVXOPT to do warm starts with GLPK, or can show how to do a warm start in other Python optimization packages?

Similar questions have been asked here and here, but without enough detail to produce useful answers.

Community
  • 1
  • 1
emunsing
  • 9,536
  • 3
  • 23
  • 29
  • 2
    If you are willing to consider another language, I'd suggest Julia and its JuliaOpt packages. In particular, JuMP (the modeling language) supports GLPK and other solvers (like CLP, which performs better than GLPK and is open source), and supports warm starts for them. – IainDunning Aug 07 '15 at 01:22
  • Great, that's helpful- I have colleagues who use Julia, but haven't made the jump. I'll look into it. – emunsing Aug 07 '15 at 05:52
  • 1
    @IainDunning JuliaOpt is simply too nice for such tasks! But oh the pain, once you have to port your Julia prototype to Python (or in my case R) and then have to deal with problems as the OP. If only I could convince my lab to switch to Julia :). – air Aug 19 '15 at 16:28
  • I've been using Pyomo in python with glpk, and I believe you can do a warm start. I know you can at least initialize variables with particular values. This may provide the functionality you need. – Dylan Cross Sep 02 '15 at 14:54
  • 1
    As this is still getting up-votes despite being closed, I'll give an update- I ended up using [CyLP](https://github.com/coin-or/CyLP) which allows warm-start programming and provided very significant speed improvements. – emunsing Jun 23 '17 at 19:13
  • 2
    @emunsing Could you elaborate on your approach using CyLP. I used it before and don't doubt it might do it. But before checking out CBCs code to get there (*setBestSolution*?) i'm wondering if you can't add some info here / maybe a Gist-link or something similar? – sascha Jan 13 '18 at 11:55
  • How did you get GLPK and CLP to use initial starting points? According to this question that is not possible: https://discourse.julialang.org/t/warm-starts-in-jump-0-21-glpk-0-12-1/36223 – Sirplentifus Jul 13 '21 at 23:15

0 Answers0