Back

G-95-44

Maximal Closure on a Graph with Resource Constraints

and

BibTeX reference

This paper 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 Lagrangean relaxation. The subgradient and bundle methods for solving of 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 Lagrangean relaxation.

, 21 pages

This cahier was revised in March 1997

Research Axis