Technical Note—Enforcing Constraints on Expanded Networks

Abstract

Any pure integer program can be cast as a shortest-route problem in an expanded network, subject to a set of side constraints. Here we select side constraints and alter the network to enforce them or surrogates for them. Logical constraints prove especially amenable to this treatment; we handle generalized upper bounds, variable upper bounds, and others simply by reconnecting arcs. Enforcing such constraints increases the fidelity of the expanded network to the integer program and tightens the relaxations that occur when the integer program is solved by implicit enumeration of the expanded network's paths.