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

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 r...

Full description

Saved in:
Bibliographic Details
Published in:Operations research letters 2000-04, Vol.26 (3), p.117-126
Main Authors: Brown, Gerald G., Dell, Robert F., Olson, Michael P.
Format: Article
Language:English
Subjects:
Branch and bound
Integer-linear programming
Penalties
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0167-6377
1872-7468
DOI:10.1016/S0167-6377(99)00072-3