EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
1389. Flowty - a network optimisation solver
Invited abstract in session MD-30: Optimization Solvers, stream Software for Optimization.
Monday, 14:30-16:00Room: 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
- Large Scale Optimization
- Column Generation
- Graphs and Networks
Status: accepted
Back to the list of papers