b-matching-lagrange-relaxation

This project is aimed to develop a lagrangian relaxation based upper bound for finding weighted maximum b-matching. The targets of the project is

1. Develop an effiecient computational approach for finding a good upper bound on maximum weighted b-matching in graph.
2. Development of a heuristic for finding feasible soluton
3. Exploration of parallel and distributed algorithms.

For learning about b-matching read the paper https://www.cs.purdue.edu/homes/apothen/Papers/bMatching-SISC-2016.pdf

For learning about lagrangian relaxation for combinatorial optimization see the paper http://www.ece.utah.edu/~kalla/phy_des/lagrange-relax-tutorial-fisher.pdf

We have used subgradient methods for solving the dual problem. See

1. http://www.ece.utah.edu/~kalla/phy_des/lagrange-relax-tutorial-fisher.pdf
2. https://see.stanford.edu/materials/lsocoee364b/02-subgrad_method_notes.pdf