Groupe d’études et de recherche en analyse des décisions


Maximal Closure on a Graph with Resource Constraints


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

Ce cahier a été révisé en mars 1997