
From:  Brady Hunsaker 
Subject:  Re: [Helpglpk] solving similar MIP problems 
Date:  Tue, 18 Jan 2005 00:28:19 0500 
Useragent:  Mozilla Thunderbird 0.9 (X11/20041124) 
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 treeI 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:
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 righthandside values, but similar analysis could be done for the matrix coefficients.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 ?
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
[Prev in Thread]  Current Thread  [Next in Thread] 