1
$\begingroup$

I'm approaching some continuous optimization problems by considering discrete approximations of them at different resolutions. Those discrete approximations can be solved with linear programming solvers, like GLPK.

After having solved a discrete approximation at resolution $h_0$, I can produce a reasonably good feasible solution $x_h$ for any discrete approximation of the problem at a higher resolution $h$. BUT, that reasonably good feasible solution $x_h$ is in general not a corner(i.e. basic) solution.

Given that solvers like GLPK can do a warm start only at a basic solution, how can I come up with a basic feasible solution near $x_h$ to warm start the solver with? Are there any open source, or at least free, solvers that can be warm started with feasible non-basic solutions?

$\endgroup$
2
$\begingroup$

LP solvers use simplex typically, so starting from nonbasic solution doesn't have too much sense. You can try finding a basic solution to $x_h$ by minimizing $||x-x_h||_p$ over your feasible region. I believe it's still an LP for $p=1$ and $p=\infty$. However, there is no guarantee warm start combined with this is faster.

$\endgroup$
  • $\begingroup$ Is solving that norm minimization LP supposed to be fast? $\endgroup$ – ORerwannabe Jun 13 '17 at 19:34
  • 1
    $\begingroup$ In the worst case it's the same as solving original LP $\endgroup$ – Eugene Jun 13 '17 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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