Maximal closure on a graph with resource constraints

This article formulates the problem of maximal closure on a graph with resource constraints as an integer programming problem with binary variables, and proposes a solution approach based on Lagrangian relaxation. The subgradient and bundle methods for solving the dual problem are compared. The subproblem resulting from relaxing the resource constraints is the classical maximal closure problem, which is solved using a maximal flow algorithm. This article proposes a heuristic to transform closures that do not satisfy resource constraints into feasible closures. The heuristic finds feasible integer solutions that are close to the upper bound provided by the Lagrangian relaxation.