Graphs

Graphs describe the connectivity of vertices using edges. All graphs are weighted with cost and directed and have a source and a sink vertex.

The $\lambda$ variables in the network model are linked to paths in the graph.

Source and Sink

Identical source and sink vertices are not supported.

Multi-Graphs and Self-Loops

It is possible to construct multi-graphs by adding multiple edges with the same source and target.

Likewise, self-loops are allowed by adding edges with source and target pointing to the same vertex.

Identical Graphs

For the purpose of solving network models it is possible to specify identical graphs. This correspond to identical subproblems in the underlying Dantzig-Wolfe decomposition and provides a significant performance speed-up.

This is the $U$ from constraint (4) in the network model which indicates the number of identical graphs. The $L$ allows to indicate a minimum usage of flow on a path from a graph.

Integer, Binary and Continuous Flows

Flows $> 1$ is captured in the same manner as for identical graphs. Think of it as a identical graphs with flow between $[0,1]$. Hence, integer and continuous flows with upper bounds $> 1$ can be achieved by playing with the $U$.

Binary Flows for $U = 1$

Binary variables is a special case of integer variables for $U = 1$. However, for $U > 1$ binary variables can be enforced as a modeling decision.