# What we Solve¶

Using the Flowty Optimisation Solver you can solve models like

$\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_k, x_v, x_e \geq 0 && (V,E) \in G, v \in V, e \in E\\ & 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.

The Flowty Optimisation Solver is a column generation based solver. It is used to solve mixed integer linear programming models formulated with (resource constrained) paths in specified graphs. The solver is well suited for solving planning & scheduling, routing, and multi-commodity flow problems. The solver is written in C++ with a Python interface.

# Install¶

Install the Flowty python packages

```
pip install flowty
```

Flowty runs with

python | os | platform | notes |
---|---|---|---|

3.9, 3.10, 3.11, 3.12 | Windows 10 | x86_64 | 64-bit Python |

- | Linux (Ubuntu 22.04, Debian 12/Bookworm) | x86_64, arm64 | glibc 2.35+ |

- | MacOS 13 (Ventura) | x86_64, arm64 | glibc 2.35+ |

# Quick Start¶

Let's solve the vehicle routing problem with time windows.

The objective is to minimize the total cost of routing vehicles from a central depot to a set of customers \(C\). Each customer \(v \in C\) must be visited exactly once within a specified time window \([a_v, b_v]\) to deliver their required demand \(d_v\), each customer has a service time it takes to unload the vehicle, and each vehicle has a maximum capacity \(q\) on goods to deliver. Traveling takes time. If a vehicle arrives early it is allowed to wait for the customer's time window to open.

Vehicles are identical so we only need one graph with one subproblem. Let \(g = (V,E,R)\) be a graph of vertices \(V\), edges \(E\), and resources \(R\). The depot is split into vertices indexed by 0 and \(|V|-1\). \(R\) consists of *time* and *load*. *time* has edge consumption (travel + service time) \(t_e : e \in E\) and vertex (time window) bounds \([a_v, b_v] : v \in V\). *load* has vertex consumption (demand) \(d_v: v \in V\) and global (vehicle capacity) bound \([0,q]\). We have one subproblem \(k = (g, v_0, v_{|V|-1})\) with \(L_k=1\) and \(U_k=|C|\). The subproblem paths are binary.

The model can be formulated as

$\begin{aligned} \min & \sum_{e \in E} c_e x_e \\ \text{s.t. } & x_v \geq 1 && v \in C \\ & 1 \leq x_k \leq |C| && \\ \end{aligned}$

with domain of each path binary.## Code¶

Find the model at `examples/v2/vrptw/vrptw.py`

. Let's run through it.

Import libraries and data and initialize the model

Fetching data

To fetch the benchmark data using `fetch_vrptw`

check out the examples.

```
# Vehicle Routing Problem with Time Windows
import flowty
import fetch_vrptw
name, n, m, E, C, D, q, T, A, B, X, Y = fetch_vrptw.fetch("C101")
model = flowty.Model()
```

Add the set partitioning constraints

```
# set partition constriants
for v in graph.vertices[1 : n - 1]:
model += v == 1
```

Construct the graph and it's resources. Time and capacity resources are defined as tuples with consumption and bound properties and values.

```
# one graph with time and demand resources, it is identical for all vehicles
time = "E", T, "V", A, B
capacity = "V", D, "G", q
graph = model.addGraph(costs=C, edges=E, resources=[time, capacity])
```

Add the subproblem with the graph. This is where the source, target, subproblem bounds, and path integrality is defined.

```
subproblem = model.addSubproblem(
graph, source=0, target=n - 1, obj=0, lb=1, ub=n - 2, domain="B"
)
```

Optimise and get back the result.

```
solution = model.getSolution()
if solution:
print(f"Cost {round(solution.cost)}")
for path in solution.paths:
print(f"Path {path.subproblem.id}: {path.x}")
for edge in path.edges:
print(f"{edge}")
```