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 va riables, and proposes a solution approach based on Lagrangian relaxati on. The subgradient and bundle methods for solving the dual problem ar e compared. The subproblem resulting from relaxing the resource constr aints is the classical maximal closure problem, which is solved using a maximal flow algorithm. This article proposes a heuristic to transfo rm closures that do not satisfy resource constraints into feasible clo sures. The heuristic finds feasible integer solutions that are close t o the upper bound provided by the Lagrangian relaxation. (C) 1997 Else vier Science Ltd.