Re: [Help-glpk] branch and bound for MILP - improvement possible?

[Brady Hunsaker]

On Sat, 2004-06-19 at 16:00, address@hidden wrote:
> While reading some articles about exact algorithms for TSP, I stumpled 
> about a (possible) improvement for branch and bound at MLP: A delta can 
> be calculated to some extent what will happen in the future branches 
> without doing all branches. By this you can faster prune nodes.
> As a mathematican (now programming with SAP) I was quite pleased with 
> myself, but everyone tells me that I must prove the effectness of this 
> approach.
> As I am quite busy and not very ambitious to earn merits, I am very 
> interested, that someone else could do the coding and write some kind 
> of official work (diploma...) with it. I think that my idea would 
> really fit for such a thing. Is there someone interested in more 
> details?
> I think that this algorithm might have never been implemented in no LP-
> package before.
> 
> Best regards
> Harald.
> 

It sounds like you mean that it is possible to find a bound on a given
branch that is better than the default bound based on the LP
relaxation.  If it fast enough to compute then it may be beneficial, as
you say.  I'm interested to hear more and will try implementing it if it
looks promising.

Brady

-- 
Brady Hunsaker
Assistant Professor
Industrial Engineering
University of Pittsburgh
http://www.engr.pitt.edu/hunsaker/