ABSTRACT
Overview A network LO-model is a model of which the technology matrix is based on a network (i.e., a graph). In this chapter we consider network models that can be formulated as ILO-models, and use methods from linear optimization to solve them. Many network models, such as the transportation problem, the assignment problem, and the minimum cost flow problem, can be formulated as an ILO-model with a technology matrix that has a special property, namely the so-called ‘total unimodularity’ property. It is shown in this chapter that, for these types of problems, any optimal solution produced by the simplex algorithm (see Chapter 3) when applied to the LO-relaxation is integer-valued. Moreover, we derive an important theorem in combinatorial optimization, namely the so-called max-flow min-cut theorem. We also show how project scheduling problems can be solved by employing dual models of network models.
