Accelerating Interior Point Methods using Graph Neural Networks

Sammanfattning

Interior Point Methods are among the most efficient algorithms for solving large-scale linear programs. However, their performance is bottlenecked by the cost of solving ill-conditioned linear systems at each iteration. This thesis investigates the potential of data-driven preconditioning to accelerate these solves, focusing on systems arising from minimum-cost network flow problems. Leveraging the natural graph structure of the problem, we employ message-passing Graph Neural Networks (GNNs) to learn structured, sparse preconditioners that approximate Cholesky-type factorisations. Our approach is grounded in the framework of Learning to Optimise, where a GNN is trained offline on a distribution of symmetric positive definite matrices to produce preconditioners that aim to reduce the condition number and iteration count of the Conjugate Gradient method by minimising the Frobenius distance to the input matrix. The proposed method is evaluated on small and large problem instances generated using NETGEN – a program for generating synthetic minimum-cost network flow problems – and benchmarked against classical preconditioners such as Jacobi and Incomplete Cholesky. Results show that our learned preconditioner can outperform traditional methods in terms of conjugate gradient iterations, condition number, total solving time of the minimum cost network flow problem, aswell as conjugate gradient solving time. However, further optimisation of the model needs to be made to improve the overall solution times of our interior point method.