This paper describes how the cut-and-solve framework and semi-Lagrangean based dual ascent algorithms can be integrated in two natural ways in order to solve the single source capacitated facility location problem. The first uses the cut-and-solve framework both as a heuristic and as an exact solver for the semi-Lagrangean subproblems. The other uses a semi-Lagrangean based dual ascent algorithm to solve the sparse problems arising in the cut-and-solve algorithm. Furthermore, we developed a simple way to separate a special type of cutting planes from what we denote the effective capacity polytope with generalized upper bounds. From our computational study, we show that the semi-Lagrangean relaxation approach has its merits when the instances are tightly constrained with regards to the capacity of the system, but that it is very hard to compete with a standalone implementation of the cut-and-solve algorithm. We were, however, able to increase the size of the instances solvable by almost 25 percent compared to methodologies proposed in the literature.