Title of article :
Maximal closure on a graph with resource constraints
Author/Authors :
Beyime Tachefine، نويسنده , , François Soumis، نويسنده ,
Issue Information :
ماهنامه با شماره پیاپی سال 1997
Pages :
10
From page :
981
To page :
990
Abstract :
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.
Journal title :
Computers and Operations Research
Serial Year :
1997
Journal title :
Computers and Operations Research
Record number :
926881
Link To Document :
بازگشت