Visualizing MIP instances with graph layout algorithms

[merschformann]

Can combinatorial optimization be art? I (finally, over Christmas) implemented a small tool that visualizes MIP instances, which was something I wanted to do all along since visualizing SAT instances for a paper I worked on with Kevin Tierney & Yuri Malitsky back in the day (paper: Structure-Preserving Instance Generation | SpringerLink ). A similar technique used by my colleague Dirk Schumacher from Nextmv for visualizing search spaces reminded me of this.

The tool uses NetworkX’s spring / Fruchterman–Reingold layouting engine and betweenness centrality for coloring the nodes. I experimented with different options, but went with these for now. I like how the spring layout exposes some of the structures. I am curious about other ways of gaining such insights (please let me know).

The tool is available on Github, if you like to take a look (or run it on your own instances): https://github.com/merschformann/exvis

IMHO, visualizations are super helpful when developing any kind of search or optimization algorithm.

[slecht_konijn]

Thanks.
They look quite beautiful, but I need to know what I am looking at.
What is being represented on the axes, nodes and arcs?

[merschformann]

Indeed, I should have put that on here as well.

The nodes are variables and an edge between two variables means that they appear in a constraint together. The color of the nodes is determined by their betweenness centrality value (smaller → blue, larger → yellow). The location of the nodes in the picture (x/y) is determined by running the spring layout / Fruchterman-Reingold layout algorithm (this one).