Models¶

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 ($\lambda$) in graphs, and continuous or integer variables ($y$), This we also denote a path based MIP or simply a path MIP:

$\begin{aligned} \min{ } & \sum_{k \in K} \sum_{e \in E^k} c_e x_e + \sum_{i \in N} f_i y_i & & & & (1) \\ \text{s.t. } & \sum_{k \in K} \sum_{e \in E^k} \alpha_{je} x_e + \sum_{i \in N} \beta_{ji} y_i = b_j & & j \in M & & (2) \\ & x_e = \sum_{p \in P^k} \Big ( \sum_{ s \in p: s = e} \mathbf{1} \Big ) \lambda_p & & k \in K, e \in E^k & & (3)\\ & L^k \leq \sum_{p \in P^k} \lambda_p \leq U^k && k \in K & & (4)\\ & \lambda_p \in \mathbb{Z}^+ && k \in K, p \in P^k & & (5)\\ & x_e \in \mathbb{Z} && k \in K, e \in E^k && (6) \\ & y_i \in \mathbb{Z} && i \in N && (7) \\ \end{aligned}$

given graphs $G(V^k, E^k),\; k \in K$ with paths $p \in P^k$ subject to resource constraints $R^k$. The expression $\sum_{ s \in p: s = e} \mathbf{1}$ counts the number of times edge $e$ is used on path $p$ and provides a scalar coefficient for the $\lambda_p$ variable. $N$ is an index set of variables and $M$ is and index set of linear constraints.

Variables $x$, $y$, and $\lambda$ may be continuous.

Path based Mixed Integer Programming¶

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 $\lambda$ 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 $\lambda$ are implicitly defined through the definitions of the graphs. The relationship between edge variables $x$ and path $\lambda$ 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.

The model to implement is reduced to

$\begin{aligned} \min{ } & \sum_{k \in K} \sum_{e \in E^k} c_e x_e + \sum_{i \in N} f_i y_i & & & & (1) \\ \text{s.t. } & \sum_{k \in K} \sum_{e \in E^k} \alpha_{je} x_e + \sum_{i \in N} \beta_{ji} y_i = b_j & & j \in M & & (2) \\ & x_e \in \mathbb{Z} && k \in K, e \in E^k && (6) \\ & y_i \in \mathbb{Z} && i \in N && (7) \end{aligned}$

together with graphs $G(V^k, E^k),\; k \in K$ subject to resource constraints $R^k$.

This is solved using the default algorithm PathMIP.

Mixed Integer Programming¶

When not defining any graphs the problem reduces to only $y$ variables and is a general mixed integer programme (MIP).

$\begin{aligned} \min{ } & \sum_{i \in N} f_i y_i \\ \text{s.t. } & \sum_{i \in N} \beta_{ji} y_i = b_j & & j \in M \\ & y_i \in \mathbb{Z} && i \in N \end{aligned}$

Variables $y$ may be continuous.

This can be solved using the build in branch-and-cut solver COIN-OR Cbc by setting the Algorithm parameter to MIP, see setParam.

Dynamic Programming¶

The dynamic programming (DP) algorithm solves the problem

$\begin{aligned} \min{ } & \sum_{e \in E} c_e x_e \\ \text{s.t. } & x_e = \sum_{p \in P^k} \Big ( \sum_{ s \in p: s = e} \mathbf{1} \Big ) \lambda_p & & k \in K, e \in E \\ & 1 \leq \sum_{p \in P^k} \lambda_p \leq 1 \\ & \lambda_p \in \mathbb{Z}^+ && p \in P \\ & x_e \in \mathbb{Z} && e \in E^k \end{aligned}$

given graphs $G(V, E),\;$ with paths $p \in P$ subject to resource constraints $R$. Variables $x$ and $\lambda$ are binary.

This is a resource constrained shortest path problem and finds a minimum cost path in a single graph. Use the dynamic programming algorithm DP by setting the Algorithm parameter, see setParam.