EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1389. Flowty - a network optimisation solver

Invited abstract in session MD-30: Optimization Solvers, stream Software for Optimization.

Monday, 14:30-16:00
Room: 064 (building: 208)

Authors (first author is the speaker)

1. Simon Spoorendonk
Flowty
2. Bjørn Petersen
Flowty

Abstract

Network optimization problems are recognised by their underlying graph(s) and constraints. Examples are within planning & scheduling, vehicle routing, and multi-commodity flow problems. Flowty’s solver exploits the graph structure and solves resource constrained shortest path problems to generate variables using a column generation scheme.

Graphs are described as edge sets and a source and target vertices for a path. Paths can additionally be constrained with a set of resources. Constraint modeling is done directly on the vertices and edges of the graphs, the subproblem itself, as well as on traditional mixed integer variables. This allows for very compact models, e.g., set partitioning constraints on vertices and edge design variables in network design problems, and the graph and resource constraints avoids the need for linearisation of constraints (big-M).

The literature has shown that column generation based algorithms are superior for many network optimization problems. The solver combines the familiarity of mixed integer programming models and graph structures with algorithmic speed.

In this talk we will dive into modeling examples in Python, take a quick look under the hood, and present recent performance benchmarks.

Keywords

Status: accepted

Back to the list of papers