[Top][All Lists]

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

Re: [Help-glpk] Suggestions to solve the master problem faster in a Bran

From: Andrew Makhorin
Subject: Re: [Help-glpk] Suggestions to solve the master problem faster in a Branch-and-Price model.
Date: Mon, 24 Mar 2014 19:27:43 +0400

> When I have to remove a basic variable, I fix its bound using the
> GLP_FX constant as Heinrich suggested, and when I have to remove a
> non-basic constraint, I unbind it using GLP_FR, before removing them
> from the problem object in a further iteration where the variable is
> no more basic or the constraint becomes basic. I used this logic to
> obtain the output I sent in the first e-mail. If I had directly
> removed from the problem object at least either one basic variable or
> one non-basic constraint, the output would have started at iteration 1
> with an objective value of 0.

Make sure that the lp presolver is disabled and no basis construction
routine (like glp_adv_basis) is used when you call glp_simplex to
perform reoptimization.

> Note that the infeasibility value of 1995 at the first iteration must
> be the cause of the rather high processing time. In this example
> really a lot of variables and constraints were removed using the logic
> I described (although now I don't know exactly how many).
> The other possibility you give is making a variable non-basic (instead
> of fixing its bounds) or making a constraint basic (instead of
> "freeing" its bounds). Would it make GLPK solve the problem faster?
> How can it be done? Is it just setting the status of the given
> variable/constraint? (but this would make the basis invalid, wouldn't
> it?)

Rather than to remove active rows and basic columns immediately, to keep
the basis valid (that is necessary for reoptimization) you may make the
rows free (unbounded) and the columns fixed. It may happen that after
reoptimization some of these rows/columns become non-active/non-basic,
in which case you can safely remove them from the working lp to reduce
its size.

reply via email to

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