[Top][All Lists]

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

Re: [Help-glpk] Simplex

From: Andrew Makhorin
Subject: Re: [Help-glpk] Simplex
Date: Fri, 4 Dec 2009 20:12:06 +0300

> just a simple (and perhaps dummy!) question I cound #39;t find the
> answer on GLPK documentation: supose I have a glp_prob and solve it
> with glp_simplex. Now, if I add a new column does glpk solve the new
> problem from scratch?

If the LP presolver is disabled (it is disabled by default),
glp_simplex always starts the search from the current basis stored
in the problem object (glp_prob). The current basis is either an
initial basis or basis provided by previous call to glp_simplex.
If you add new rows to the problem object, by default they become
basic (i.e. non-active), and if you add new columns, they become
non-basic, so the current basis remains valid and can be used for

> I mean, it is possible to obtain 2 different solutions to a problem
> (but with the same optimal cost, of course!), for example one solution
> obtained solving the complete (with all columns) version of the
> problem and the other solving a restricted version of the problem then
> add the new columns and solving this new lp.

Yes, it is possible to use column generation. You can start from
a subset of columns and, once the instance has been solved to
optimality, add new columns having non-feasible reduced costs, and
perform re-optimization using the primal simplex.

reply via email to

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