Fixed-Charge Network Design Problems

This chapter introduces problems and models that involve design decisions captured with arc-based binary variables that typically model fixed costs. We distinguish whether the demand can be represented as a single commodity or as multiple commodities, whether or not there are capacities, and whether or not there are variable transportation costs in the objective function, in addition to the fixed design costs. These characteristics yield different variants of network design problems and models, with various degrees of complexity. We identify a few basic modeling approaches in network design, including the use of path flow variables instead of arc flow variables, and the derivation of cut-set-based inequalities.