[Coin-discuss] Removing Deadwood in Bcp

[Laszlo Ladanyi]

Yes, it'd be nice to purge those cuts... I'll try to get to it later this
week or early next week.

--Laci

On Thu, 20 Apr 2006, Francois Margot wrote:

> 
> Jonathan:
> 
> I have seen the numbers reported by top go up and down for the memory usage.
> It is true that the down movement is usually quite small, so it might
> be non significant. Nevertheless, I can run large Branch-and-Bound 
> with Bcp in DFS on less than 1% of the memory. Running a Branch-and-Cut
> with DFS sees the memory usage increases regularly.
> 
> Tracking down the creation and destruction of algorithmic cuts shows the
> following:
> 
> LP level: Cuts are created by cut generation or unpacking. Cuts are destroyed
> from BCP_lp_clean_up_node() and BCP_lp_delete_cols_and_rows().
> 
> TM level: Cuts are created by unpacking. Cuts are destroyed only
> from ~BCP_tm_prob at the very end of the execution.
> 
> When deadwood is removed from the tree, it would be nice to remove the 
> corresponding algorithmic cuts stored in BCP_tm_prob.
> 
> Francois
> 
> 
> On Wed, 19 Apr 2006, Jonathan Eckstein wrote:
> 
> > Francois -- perhaps you know this already, but "top" reports the total memory 
> > size of the process, including memory in the free pool.  Most programs don't 
> > return freed memory to the operating system, but just keep it in their own 
> > free pool.  In unix/linux, I think it is only possible to return memory to 
> > the OS (via sbrk()) if it is at the end of the virtual address space.  Thus, 
> > never seeing "top" return smaller memory amounts isn't necessarily a sign of 
> > a memory problem.  However, if the memory reported by "top" always goes up 
> > and never stabilizes, that might be a sign of a leak.
> >
> > -- Jonathan
> >
> >
> > Francois Margot wrote:
> >> Laci:
> >> 
> >> The RemoveExploredBranches does not create problems, apparently,
> >> but its efficiency seems quite limited. I have never seen the
> >> memory usage going down (as reported by top) even when running
> >> large BC with depth first. Are the generated cuts corresponding
> >> to deadwood removed from "cuts" in BCP_tm_prob? I can not see where this
> >> is done. It should not be that hard to do, since it is possible
> >> to store the index of the node where a cut was generated and remove the cut
> >> when its "generating node" is removed.
> >> 
> >> Francois
> >> 
> >>> I have added code that removes the "deadwood" from the search tree, i.e.,
> >>> immediately removes subtrees that are completely explored. I have done 
> >>> some
> >>> quick testing and it seems to work. However, by default it is turned off, 
> >>> just
> >>> to make sure that noone's code breaks. I wonder if people could give it a 
> >>> try
> >>> and let me know whether it works fine or not. I am interested in both 
> >>> serial
> >>> and parallel settings. To enable the feature add
> >>>     BCP_RemoveExploredBranches 1
> >>> to your parameter file.
> >>> 
> >>> --Laci
> >> 
> >> _______________________________________________
> >> Coin-discuss mailing list
> >> Coin-discuss at list.coin-or.org
> >> http://list.coin-or.org/mailman/listinfo/coin-discuss
> >
> >
> >
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-discuss
>