Skip to content

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

minkKeEkcexe+iNfiyi(1)s.t. kKeEkαjexe+iNβjiyi=bjM(2)xe=pPk(sp:s=e1)λpkK,eEk(3)LkpPkλpUkkK(4)λpZ+kK,pPk(5)xeZ,yiZeE,iN(6) \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 \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}, y_i \in \mathbb{Z} && e \in E, i \in N && (6) \end{aligned}

given graphs G(Vk,Ek),  kKG(V^k, E^k),\; k \in K with paths pPkp \in P^k subject to resource constraints RkR^k. The expression sp:s=e1\sum_{ s \in p: s = e} \mathbf{1} counts the number of times edge ee is used on path pp and provides a scalar coefficient for the λp\lambda_p variable. NN is an index set of variables and MM is and index set of linear constraints.

Variables xx, yy, 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 xx and yy variables are defined. Path variables λ\lambda are implicitly defined through the definitions of the graphs. The relationship between edge variables xx 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

minkKeEkcexe+iNfiyi(1)s.t. kKeEkαjexe+iNβjiyi=bjM(2)xeZ,yiZeE,iN(6) \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 \in M & & (2) \\ & x_e \in \mathbb{Z}, y_i \in \mathbb{Z} && e \in E, i \in N && (6) \end{aligned}

together with graphs G(Vk,Ek),  kKG(V^k, E^k),\; k \in K subject to resource constraints RkR^k.

This is solved using the default algorithm PathMIP.

Mixed Integer Programming

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

miniNfiyis.t. iNβjiyi=bjMyiZiN \begin{aligned} \min{ } & \sum_{i \in N} f_i y_i \\ \text{s.t. } & \sum_{i \in N} \beta_{ji} y_i = b & & j \in M \\ & y_i \in \mathbb{Z} && i \in N \end{aligned}

Variables yy 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

mineEcexes.t. xe=pPk(sp:s=e1)λpkK,eE1pPkλp1λpZ+pPxeZeE \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 \end{aligned}

given graphs G(V,E),  G(V, E),\; with paths pPp \in P subject to resource constraints RR. Variables xx 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.