There are several formulations and exact solvers for MWCS problem. It is commonly reduced to MIP.

Example paper: https://arxiv.org/pdf/1605.02168

The algorithm is implemented in java and solves three variants of the problem:

https://github.com/ctlab/virgo-solver

An R package:

https://github.com/ctlab/mwcsr