A GENERALIZATION OF BINARY VARIABLES

Most mixed integer programs include binary variables introduced to express the restriction of some decision variables to one of two possible values. The branch and bound technique solves such problems by forcing the binary variables to either zero or one in a systematic way. It is shown that the concept of a binary variable can be generalized to encompass constraints of form x less-than-or-equal-to u or x greater-than-or-equal-to v. The advantages of this generalization include more easily obtained and smaller formulations which tend to be solved more quickly. Only slight modifications to algorithms, criteria and implementations are required.