%0 Journal Article
%@holdercode {isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S}
%@nexthigherunit 8JMKD3MGPCW/3ESGTTP
%@archivingpolicy denypublisher denyfinaldraft36
%@issn 0377-2217
%@resumeid
%@resumeid 8JMKD3MGP5W/3C9JHMQ
%@usergroup administrator
%@usergroup sergio
%3 lagrangean.pdf
%@dissemination WEBSCI; PORTALCAPES.
%2 sid.inpe.br/marciana/2004/08.17.15.27.49
%4 sid.inpe.br/marciana/2004/08.17.15.27
%@secondarytype PRE PI
%K relaxation, Lagrangean and surrogate relaxation, generalized assignment problem /  SUBGRADIENT METHOD, KNAPSACK-PROBLEM, SHORTEST-PATH, ALGORITHM, OPTIMIZATION, CONSTRAINTS, MODEL.
%X This work presents Lagrangean/surrogate relaxation to the problem of maximum profit assignment of n tasks to m agents (n > m), such that each task is assigned to only one agent subject to capacity constraints on the agents. The Lagrangean/surrogate relaxation combines usual Lagrangean and surrogate relaxations relaxing first a set of constraints in the surrogate way. Then, the Lagrangean relaxation of the surrogate constraint is obtained and approximately optimized (one-dimensional dual). The Lagrangean/surrogate is compared with the usual Lagrangean relaxation on a computational study using a large set of instances. The dual bounds are the same for both relaxations, but the Lagrangean/surrogate can give improved local bounds at the application of a subgradient method, resulting in less computational times. Three relaxations are derived for the problem. The first relaxation considers a vector of multipliers for the capacity constraints, the second for the assignment constraints and the other for the Lagrangean decomposition constraints. Relaxation multipliers are used with efficient constructive heuristics to find good feasible solutions. The application of a Lagrangean/surrogate approach seems very promising for large scale problems. (C) 1999 Elsevier Science B.V. All rights reserved.
%D 1999
%V 114
%8 Apr.
%N 1
%@group LAC-INPE-MCT-BR
%A Narciso, M. G.,
%A Lorena, Luiz Antonio Nogueira,
%B European Journal of Operational Research
%T Lagrangean/surrogate relaxation for generalized assignment problems
%@language English
%@ 0377-2217
%P 165-177
%@area COMP
%@copyholder SID/SCD
%@secondarykey INPE-11221-PRE/6670