Information-based branching schemes for binary linear mixed integer problems

Title: Information-based branching schemes for binary linear mixed integer problems
Creator: Kilinç-Karzan, Fatma; Nemhauser, George L.; Savelsbergh, Martin W. P.
Relation: Mathematical Programming Computation Vol. 1, Issue 4, p. 249-293
Publisher Link: http://dx.doi.org/10.1007/s12532-009-0009-1
Publisher: Springer
Resource Type: journal article
Date: 2009
Description: Branching variable selection can greatly affect the effectiveness and efficiency of a branch-and-bound algorithm. Traditional approaches to branching variable selection rely on estimating the effect of the candidate variables on the objective function. We propose an approach which is empowered by exploiting the information contained in a family of fathomed subproblems, collected beforehand from an incomplete branch-and-bound tree. In particular, we use this information to define new branching rules that reduce the risk of incurring inappropriate branchings. We provide computational results that demonstrate the effectiveness of the new branching rules on various benchmark instances.
Subject: branch-and-bound; variable selection; computational algorithms; mixed integers
Identifier: http://hdl.handle.net/1959.13/937783
Identifier: uon:12619
Identifier: ISSN:1867-2949
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format