Technical Note—Equivalence of the 0-1 Integer Programming Problem to Discrete Generalized and Pure Networks

We show how to formulate a 0-1 integer programming problem as a “mixed integer” generalized network and as a discrete “0-U” pure network problem. Special integer programming structures allow convenient simplifications. The usefulness of these formulations is in providing new relaxations for integer programming that can take advantage of recent advances in the development of efficient computer programs for network problems. We cite three practical applications in which these ideas have led to marked improvement in solution efficiency.