# 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.