Re: [Help-glpk] solving similar MIP problems

[Brady Hunsaker]

Both Erik's and François's questions would be better directed to a forum 
on optimization or operations research, such as the sci.op-research 
newsgroup, rather than this one, since they don't relate to GLPK 
specifically.

For Erik's, there has been work on using the past performance of 
branching decisions to aid in branching decisions in a single b&b 
tree--I don't know whether anyone has considered using the information 
on a new b&b tree for a similar instance.  Heuristics to get good 
feasible solutions are always valuable, but again I don't know if anyone 
has looked at the particular situation Erik describes.

François's question is answered below.

Brady

François Galea wrote:
> 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 ?
Sensitivity analysis for linear programming gives you a great deal of 
information about the effects of these kinds of changes without even 
resolving.  In particular, you could look at the --bounds option in GLPK 
and look up the "100% Rule" in an optimization text.  These apply to the 
objective coefficients and right-hand-side values, but similar analysis 
could be done for the matrix coefficients.

If you do need to resolve, then starting at the optimal solution to the 
similar problem is usually much better than starting 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