The classical Art Gallery Problem asks for the minimum number of guards that achieve visibility coverage of a given polygon. This problem is known to be NP-hard, even for very restricted and discrete special cases. We present a primal-dual algorithm based on linear programming that provides lower bounds on the necessary number of guards in every step and---in case of convergence and integrality---ends with an optimal solution. In addition, we consider the Art Gallery Problem variant where a polygonal region is to be covered with light sources that emit light fading with distance. We describe a practical approximation algorithm based on the simplex method and primal-dual LP separation. For the case where the light positions are given, we describe a fully polynomial-time approximation scheme. We will also consider the possibility of steering towards integer solutions, e.g., by using cutting planes based on Edge Cover and Set Cover inequalities to eliminate fractional solutions.