julia

In a previous post, we pushed the boundaries of the LightGraphs.jl abstraction to see how conforming the algorithms are to the declared interface, noticing some implied assumptions that were not stated. This has led to the development of VertexSafeGraphs.jl and soon to some work on LightGraphs.jl itself. Another way to push the abstraction came out of the JuliaNantes workshop: leveraging some special structure of graphs to optimize some specific operations. A good parallel can be established be with the LinearAlgebra package from Julia Base, which defines special matrices such as Diagonal and Symmetric and Adjoint, implementing the AbstractMatrix interface but without storing all the entries.

In various graph-related algorithms, a graph is modified through successive operations, merging, creating and deleting vertices. That’s the case for the Blossom algorithm finding a best matching in a graph and using contractions of nodes. In such cases, it can be useful to remove only the vertex being contracted, and maintain the number of all other vertices. LightGraphs.jl offers a set of abstractions, types and algorithms to get started with graphs.

Cracking Benders decomposition, one cut at a time.

Some digging in representations for optimization modelling

Making social events easier as a graph problem.

Pushing the type system for more compile-time information

Leveraging one of Julia central features for clearer formulation of an optimization problem.

Who needs libraries when from scratch looks so good

A column generation algorithm for the cutting width problem using Julia and JuMP