The core model of the network optimization solver is the path based model which is a mixed integer programme (MIP) with variables representing edges (x) and paths (λ) in graphs, and continuous or integer variables (y), This we also denote a path based MIP or simply a path MIP:
given graphs G(Vk,Ek),k∈K with paths p∈Pk subject to resource constraints Rk. The expression ∑s∈p:s=e1 counts the number of times edge e is used on path p and provides a scalar coefficient for the λp variable. N is an index set of variables and M is and index set of linear constraints.
To solve the path based mixed integer programme (path MIP) the preferred algorithm is a branch-and-cut-price algorithm that solves resource constrained shortest pah problems as subproblems. That is, the paths variables λ are priced in when needed in a column generation fashion. The dynamic programming algorithm is used for solving the subproblems.
When building path based models only x and y variables are defined. Path variables λ are implicitly defined through the definitions of the graphs. The relationship between edge variables x and path λ for a graph is derived from the graph definition, i.e., constraints (3). Constraints (4)-(5) is related to identical subproblems and path flows above 1, see the details on graphs.