Accession Number : AD0764587

Title :   Improved Penalty Calculations for a Mixed Integer Branch-and-Bound Algorithm.

Descriptive Note : Technical rept.,

Corporate Author : MASSACHUSETTS UNIV AMHERST DEPT OF GENERAL BUSINESS AND FINANCE

Personal Author(s) : Armstrong,Ronald D. ; Sinha,Prabhakant

Report Date : JUN 1973

Pagination or Media Count : 21

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)

Descriptors :   (*LINEAR PROGRAMMING, ALGORITHMS), SET THEORY, MATRICES(MATHEMATICS), OPTIMIZATION

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE