Valid Integer Polytope (VIP) Penalties for Branch-and-Bound Enumeration

Abstract

The authors 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. Integer-linear programming; Branch and bound; Penalties

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2000
Accession Number
ADA487314

Entities

People

  • Gerald G. Jerry Brown
  • Michael P. Olson
  • Robert F. Dell

Organizations

  • Naval Postgraduate School

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Computations
  • Inequalities
  • Information Operations
  • Linear Programming
  • Observation
  • Operations Research
  • Simplex Method
  • Supply Chain
  • Symmetry

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Educational Psychology
  • Operations Research