Lookahead Branching for Mixed Integer Programming

Wasu Glankwamdee (wag3lehigh.edu)
Jeff Linderoth (jtl3lehigh.edu)

Abstract: 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

Keywords:

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Technical Report 06T-004, Department of Industrial and Systems Engineering, Lehigh University

Download: [PDF]

Entry Submitted: 10/12/2006
Entry Accepted: 10/12/2006
Entry Last Modified: 10/12/2006

Modify/Update this entry