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

This is a pre-release version

pip install flowty --pre

Flowty runs with

python	os	platform	notes
3.9, 3.10, 3.11, 3.12	Windows 10+	x86_64	64-bit Python
3.9, 3.10, 3.11, 3.12	Linux (Ubuntu 22.04, Debian 12/Bookworm)	x86_64	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.

status = model.solve()
print(f"Status {status}")

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

License¶

Flowty is a commercial product but ships with a community license that is free to use with some limitations. Browse below to identify your needs.

Commercial License¶

For an unrestricted commercial license contact Flowty at sales@flowty.ai.

Community License¶

The community license is free for non-commercial or academic use, it may have limited features and/or additional restrictions, and it comes with limited support and no warranties.

Support¶

Flowty offers various support options.

Github Issues¶

Create an issue in Flowty's github repository to report a bug or ask a question.

E-mail¶

Holders of a commercial license can contact support at support@flowty.ai.

Response Time¶

We strive to respond within 1 business day.