Accession Number : AD0778646
Title : Cross-Branching in Bivalent Programming.
Descriptive Note : Management science research rept.,
Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Personal Author(s) : Jeroslow,R. G.
Report Date : MAR 1974
Pagination or Media Count : 16
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)
Descriptors : *Mathematical programming, Linear programming, Integer programming, Inequalities, Theorems
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE