|Subject:||RE: [Help-glpk] Using branch and cut starting with relaxed solution|
|Date:||Fri, 19 Dec 2008 08:39:50 -0800|
Thanks for the reply Andrew,|
> There exists so called crossover procedure that allows recovering
> a basic solution corresponding to a given optimal solution. As a rule
> it follows the interior point method to recover the basis. However,
> this feature is not yet implemented in glpk.
Do you have a handy citation for this procedure? I did a quick search and only found links to CPLEX documentation without any algorithmic details.
> To start the search the mip solver needs an optimal *basic* solution
> to lp relaxation. So even the solution you can provide is optimal,
> it is useless for the mip solver until the corresponding basis is known.
Yes, that is my main problem (at least as far as optimization goes).
> Probably, as you said, you can call glp_simplex and then glp_intopt
> and (then) see what happens. I do not think that solving lp relaxation
> will take more time than integer optimization.
You are completely correct. Though, I'm finding the relaxed solution right now via a decomposition method (which is why I have no basis at the end) and I'm finding it up to 100X faster than glp_simplex would otherwise. Since this is the case, I'd love to use that as a starting point for branching. My problems are very big (up to several days to run using glp_simplex).
I look forward to any further advice...
It’s the same Hotmail®. If by “same” you mean up to 70% faster. Get your account now.
|[Prev in Thread]||Current Thread||[Next in Thread]|