Improved Penalty Calculations for a Mixed Integer Branch-and-Bound Algorithm.
Abstract
The paper presents an extension of Tomlin's penalties for the branch-and-bound linear mixed integer programming algorithms of Beale and Small. Penalties which are uniformly stronger are obtained by jointly conditioning on a basic variable and the non-basic variable yielding the Tomlin penalty. It is shown that this penalty can be computed with a little additional arithmetic and some extra bookkeeping. The improvement is easy to incorporate for the normal case as well as when the variables are grouped into ordered sets with generalized upper bounds. Computational experience bears out the usefulness of the extra effort for predominantly integer problems. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1973
- Accession Number
- AD0764587
Entities
People
- Prabhakant Sinha
- Ronald D. Armstrong
Organizations
- University of Massachusetts Amherst