Cross-Branching in Bivalent Programming.
Abstract
A new branching procedure for bivalent branch-and-bound algorithms is developed, by which, in addition to the usual settings of a bivalent variable to zero and to one, two bivalent variables can be chosen and set equal and opposite. The new kind of branching, which we call cross-branching, drops dimensionality of the resulting two subproblems and does not increase the number of linear constraints. The author proves that the usual branching and the cross branching are the only two branchings which drop dimensionality, if a given problem is to be separated into no more than two subproblems. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1974
- Accession Number
- AD0778646
Entities
People
- Robert G. Jeroslow
Organizations
- Carnegie Mellon University