Martin Köhler
I am a PhD student at TU Braunschweig, Germany, specializing in nonlinear optimization and scientific computing in Julia. My research combines functional analysis and large-scale optimization, with a focus on continuous models of complex networks and dynamical systems. I am interested in developing mathematical tools that are also computationally practical.
Session
The cut norm of a matrix measures the largest imbalance, given by the maximum absolute sum of its entries over any choice of row and column subsets. Computing this norm amounts to a combinatorial optimization problem that is NP-hard. It originates in graph theory and it plays a central role in the theory of graph limits, where it defines a notion of distance between large networks.
We first present an integer program, modeled in JuMP.jl, and highlight the limitations in scalability. We then introduce a heuristic based on repeatedly solving a bilinear relaxation of the cut norm problem. Along the way, we utilize NLPModels.jl to efficiently represent the problem and solve the resulting nonlinear program using TRON from JSOSolvers.jl. To explore the solution space effectively, we employ a multi-start strategy initialized via a Sobol sequence generated with Sobol.jl.
Through benchmarks, we show that the heuristic recovers optimal solutions on small instances and scales to significantly larger matrices than the exact formulation. We also illustrate how the algorithm can be used in the context of graph limit theory to measure the distance between large networks.