[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

RE: [Help-glpk] Using branch and cut starting with relaxed solution

From: Joey Rios
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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]