/maxcut

Python implementation of various max-cut problem solvers.

Primary LanguagePythonGNU General Public License v3.0GPL-3.0

maxcut: Max-Cut problem solving tools following a variety of approaches

Implementation realized in the context of scholar project on the max-cut problem.

Implemented Max-Cut solving approaches

maxcut.MaxCutSDP interfaces external solvers (such as SCS or CVXOPT) to solve the SDP (Semi-Definite Programming) formulation of the Max-Cut optimization problem.

maxcut.MaxCutBM implements the Burer-Monteiro approach, which consists in using a riemannian trust-regions algorithm to solve a non-convex formulation of the Max-Cut problem.

References

N. Boumal, V. Voroninski and A. Bandeira (2016). The non-convex Burer-Monteiro approach works on smooth semidefinite programs. In proceedings NIPS 2016. available here

N. Boumal (2016). A Riemannian low-rank method for optimization oversemidefinite matrices with block-diagonal constraints. arXiv preprint. available here

N. Boumal, B. Mishra, P.-A. Absil and R. Sepulchre (2014). Manopt, a Matlab toolbox for optimization on manifolds. Journal of Machine Learning Research. matlab source code

P.-A. Absil, R. Mahony, and R. Sepulchre (2008). Optimization Algorithms on Matrix Manifolds. Princeton University Press.

License

Copyright 2019 Paul Andrey

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.