Re: [Help-glpk] solving similar MIP problems

[François Galea]

Hi Erik,

Most MIP solvers can use the result of a previous solving as the 
starting point for solving a new problem, thus I guess GLPK includes 
this functionality.

This functionality allows solving techniques such as column generation 
and constraint programming.

I would like to add another question : Can the solution of a linear (or 
MIP) problem be used as a starting point for a very similar problem, 
with only slight changes in the simplex matrix coefficients ? For 
example using coefficients that only differ for about 0.001% of the 
corresponding coefficients in the original matrix. I guess it is 
possible, but does this improve the performance, compared to solving the 
problem from scratch ?

Thanks,

François.


Erik Rantapaa a écrit :
> This is more of a general question about solving MIPs rather than about using
> GLPK, but I thought I would ask in case anyone had something to say about it.
>
> I have a situation where I am basically solving the same MIP repeatedly.
> The problems are not always exactly the same, but they are largely the
> same modulo a small number of modified/added constraints or a
> modified objective function. In many cases, a solution from one of the problems
> might be a solution (although not necessarily optimal) to another problem.
>
> The question I have is whether the work done in solving one of the problems
> can be applied to more quickly find a solution to another very similar problem.
> Some things I have in mind are:
>
>   * deciding what variable to branch on based on "past performance" in
>     previous runs.
>
>   * using a previous solution as a starting point for solving a new problem
>     to more quickly find an initial feasible solution.
>
> Is anyone familiar with any techniques or research in this area?
>
> Thanks,
>
> ER
>
>
>
>                 
> __________________________________ 
> Do you Yahoo!? 
> Yahoo! Mail - now with 250MB free storage. Learn more.
> http://info.mail.yahoo.com/mail_250
>
>
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/help-glpk