[Top][All Lists]

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

Re: [Help-glpk] solving similar MIP problems

From: Brady Hunsaker
Subject: Re: [Help-glpk] solving similar MIP problems
Date: Tue, 18 Jan 2005 00:28:19 -0500
User-agent: Mozilla Thunderbird 0.9 (X11/20041124)

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.


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.



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?



reply via email to

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