[Symphony] Warm starting and rhs modification

[Ted Ralphs]

Warm starting in integer programming is very tricky. It is not at all like
the LP case and certainly not always guaranteed to help. It tends to work
best when the problem modifications are slight, but if the tree that would
have generated from scratch for two different instances is much different,
then it may not very well. Basically, we are trying to re-use the same tree
and continue the solution process from there after modifying the LP
relaxations in the leaf nodes. If you warm start with a whole sequence of
problems, the warm start tree may get larger and larger. At some point, you
have to either start again from scratch or prune back the tree because the
advantages of the warm start will be overcome.

There are some parameters you can play with that try different warm-starting
strategies---it is certainly not guaranteed that the default is going to
perform well. For example, in some cases, you may want to prune the tree
back a little to generate the warm start each time, but this is
problem-dependent. As with any effort to improve the efficiency of an
algorithm for solving an NP-hard problem, the tuning process is both an art
and a science.

Cheers,

Ted

On Fri, Sep 30, 2011 at 7:56 AM, Alexander Sviridenko <
oleks.sviridenko at gmail.com> wrote:

> It seems like the problem was solved. Thank you for support.
>
> However, since I was able to use warm starting, I have a question. I'm
> taking a problem and solve it. Then I'm changing rhs bounds and
> resolve it and so a lot of times. But the profit from warm starting in
> this case in comparison with a simple use of branchAndBound() for each
> resolving is very small. And sometimes even leads to negative result
> when the warm starting case works longer. Maybe you have some thoughts
> about this?
>
> Thank you.
>
> Alexander
>



-- 
Dr. Ted Ralphs
Associate Professor, Lehigh University
(610) 628-1280
ted 'at' lehigh 'dot' edu
coral.ie.lehigh.edu/~ted
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/symphony/attachments/20111004/a5cbfe60/attachment.html>