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