Skip to content

Concepts

Model

Using the Flowty Optimisation Solver you can solve models like

min⁡∑k∈Kckxk+∑(V,E)∈G(∑v∈Vcvxv+∑e∈Ecexe)+∑i∈Nciyis.t. ∑k∈Kαjkxk+∑(V,E)∈G(∑v∈Vαjvxv+∑e∈Eαjexe)+∑i∈Nαjiyi=bjj∈Mxv,xe≥0(V,E)∈G,v∈V,e∈E0≤Lk≤xk≤Ukk∈Kyi∈[R,Z,B]i∈N \begin{aligned} \min{ } & \sum_{k \in K} c_k x_k + \sum_{(V,E) \in G} \Big ( \sum_{v \in V} c_v x_v + \sum_{e \in E} c_e x_e \Big ) + \sum_{i \in N} c_i y_i \\ \text{s.t. } & \sum_{k \in K} \alpha_{jk} x_k + \sum_{(V,E) \in G} \Big (\sum_{v \in V} \alpha_{jv} x_v + \sum_{e \in E} \alpha_{je} x_e \Big ) + \sum_{i \in N} \alpha_{ji} y_i = b_j & & j \in M \\ & x_v, x_e \geq 0 && (V,E) \in G, v \in V, e \in E\\ & 0 \leq L^k \leq x_k \leq U^k && k \in K \\ & y_i \in [\mathbb{R}, \mathbb{Z}, \mathbb{B}] && i \in N \end{aligned}

where \(N\) is the set of general (master) variables, \(M\) is the set of constraints, \((g, s, t) \in K\) is the set of subproblems with graph \((V,E)=g \in G\), vertices \(V\), edges \(E\), resource constraints \(R_g\), and \(s,t \in V\) is the source and target for the feasible paths for the subproblem. Paths usage may be fractional, integral or binary.

Solve regular mixed integer programming models

Use only \(y\) variables and do not add subproblems.

Solve a resource constrained shortest path problem

Add exactly one subproblem and no \(y\) variables or constraints. Set lower and upper bounds to 1 and let the domain be binary.

Graphs

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

Identical source and target is not supported.

Split node in two.

Multi-graphs and self-loops are not supported.

Insert node in middle of multi-edge and remove self-loops.

Resources

Each path is constrained in the network. This is handled in the dynamic programming algorithm by accumulating resources that are used for verifying bounds while traversing the graph.

In the dynamic programming algorithm labels represent states and a resource is an element in the state. The cost component of a label can be considered as an unbounded resource and hence results in a state element.

First Resource

The first resources defines the order in which the labels are handled. There must not exist a cycle in the graph with zero consumption for that resource.

Resource Update Functions (RUF)

Resource update function \(f_r\) defines how resource \(r \in R\) is updated from state \(S_i\) when traversing edge \((i,j) \in E\). Apply all RUFs to obtain new state \(S_j = \{ f_r(S_i) : r \in R \}\).

Example RUFs for an isolated resource \(r \in R\) with state \(s_i^r\) are

  • time windows where travel time \(q_{ij}^r\) is added and then waiting for a window to open \(s_j^r = \max \{ l_v^r, s_i^r + q_{ij}^r \}\).
  • capacity where demand \(q_{ij}^r\) is added \(s_j^r = s_i^r + q_{ij}^r\)
  • mutually exclusive resource where the \(s_i^r\) is a bitset with with ones for visited sets and \(q_{ij}^r\) indicates new set to visits, i.e., \(s_j^r = s_i^r ~|~ q_{ij}^r\)

Several commonly used RUFs are provided with Flowty.

Feasibility

State \(S\) is feasible if it satisfies all rules. Example rules are for an isolated resource \(r \in R\) with state \(s^r\) are

  • time windows where \(s^r\) must be within a window \([l_v^r, u_v^r]\) at vertex \(v \in V\), i.e., \(l_v^r \leq s^r \leq u_v^r\).
  • capacity where \(s^r\) must be less than or equal than a global bound at vertex \(v \in V\), i.e., \(s^r \leq u_v^r\).
  • mutually exclusive resource where \(s^r\) must be bitwise less than or equal to the bit vector representing the set of the current vertex i.e., \((s^r \oplus u_v^r) ~\& ~s^r \leq 0\).

Several commonly used rules are provided with Flowty.

Subproblems

Graph, source, target, lower bound, upper bound (on usage)