[Scip] Forking and LP Basis updates

[Tobias Achterberg]

Hi Sid,

yes, you are absolutely right. The LP warm start information is associated with the fork 
node. Then, the number of nodes that depend on this is recorded (typically 2, but it could 
be that you are not solving the LP at every node, and then it would be more than 2). If 
the warm start info is used by a node, the counter gets decremented, and if it reaches 
zero, the info is discarded.

I did not think about your idea of storing the warm start information incrementally. 
Actually, it is a good idea, but it has some implementation challenges. First of all, the 
warm start information is an abstract object that is only implemented by the LP solver 
interface. Depending on the LP solver, this could be different data. Typically, it 
contains the simplex basis, but it can also contain additional data like steepest edge 
norms, or completely different data (like an x and pi vector for the volume algorithm, or 
some bundle information for bundle methods). If you go with this incremental approach, 
then this had to be implemented by each LP solver interface. Moreover, it would be much 
harder to know when a certain piece of information is no longer needed and can be discarded.


Tobias


Siddhartha Jain wrote:
> Hi,
>
> I had two questions.
>
>  From what I understand, forking a node means the node has been marked
> as an internal node in the search tree with children. Is this correct?
>
> I was looking around the SCIP source code to figure out how the LP basis
> is updated to give a warm start at each node where the LP needs to be
> solved. As far as I could figure out, it seems like the entire basis
> information for every node that is forked is stored when the fork
> happens and is later restored for the children nodes if and when it is
> needed. Is my understanding correct? If it is, then why is the basis
> information not stored incrementally for the nodes (i.e. a child node
> could only store the basis information which has changed between it and
> the parent, etc.)?
>
> Thanks a lot,
> --Sid
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip