We consider the effectiveness of a lookahead branching method for the selection of branching variable in branch-and-bound method for mixed integer programming. Specifically, we ask the following question: by taking into account the impact of the current branching decision on the bounds of the child nodes two levels deeper than the current node, can better branching decisions be made? We describe methods for obtaining and combining bound information from two levels deeper in the branch-and-bound tree, demonstrate how to exploit auxiliary implication information obtain in the process, and provide extensive computational experience showing the effectiveness of the new method
Citation
Technical Report 06T-004, Department of Industrial and Systems Engineering, Lehigh University