Valid integer polytope (VIP) penalties for branch-and-bound enumeration

Valid integer polytope (VIP) penalties for branch-and-bound enumeration

0.00 Avg rating0 Votes
Article ID: iaor20052328
Country: Netherlands
Volume: 26
Issue: 3
Start Page Number: 117
End Page Number: 126
Publication Date: Mar 2000
Journal: Operations Research Letters
Authors: , ,
Keywords: duality
Abstract:

We introduce new penalties, called valid integer polytope (VIP) penalties, that tighten the bound of an integer-linear program during branch-and-bound enumeration. Early commercial codes for branch and bound commonly employed penalties developed from the dual simplicial lower bound on the cost of restricting fractional integer variables to proximate integral values. VIP penalties extend and tighten these for ubiquitous k-pack, k-partition, and k-cover constraints. In real-world problems, VIP penalties occasionally tighten the bound by more than an order of magnitude, but they usually offer small bound improvement. Their ease of implementation, speed of execution, and occasional, overwhelming success make them an attractive addition during branch-and-bound enumeration.

Reviews

Required fields are marked *. Your email address will not be published.