[Top][All Lists]

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

Re: [Help-glpk] solving similar MIP problems

From: François Galea
Subject: Re: [Help-glpk] solving similar MIP problems
Date: Thu, 06 Jan 2005 12:09:54 +0100
User-agent: Mozilla Thunderbird 0.9 (X11/20041124)

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 ?



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?



__________________________________ Do you Yahoo!? Yahoo! Mail - now with 250MB free storage. Learn more.

Help-glpk mailing list

reply via email to

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