| 1. Identity statement | |
| Reference Type | Journal Article |
| Site | mtc-m16.sid.inpe.br |
| Holder Code | isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S |
| Identifier | 6qtX3pFwXQZsFDuKxG/DbM9M |
| Repository | sid.inpe.br/marciana/2004/08.17.15.27 (restricted access) |
| Last Update | 2004:08.17.03.00.00 (UTC) administrator |
| Metadata Repository | sid.inpe.br/marciana/2004/08.17.15.27.49 |
| Metadata Last Update | 2018:06.05.01.28.42 (UTC) administrator |
| Secondary Key | INPE-11221-PRE/6670 |
| ISBN/ISSN | 0377-2217 |
| ISSN | 0377-2217 |
| Citation Key | NarcisoLore:1999:LaReGe |
| Title | Lagrangean/surrogate relaxation for generalized assignment problems  |
| Year | 1999 |
| Month | Apr. |
| Access Date | 2024, Apr. 28 |
| Secondary Type | PRE PI |
| Number of Files | 1 |
| Size | 158 KiB |
| 2. Context | |
| Author | 1 Narciso, M. G. 2 Lorena, Luiz Antonio Nogueira |
| Resume Identifier | 1 2 8JMKD3MGP5W/3C9JHMQ |
| Group | 1 LAC-INPE-MCT-BR |
| Journal | European Journal of Operational Research |
| Volume | 114 |
| Number | 1 |
| Pages | 165-177 |
| History (UTC) | 2006-09-28 22:36:24 :: administrator -> sergio :: 2008-01-07 12:49:58 :: sergio -> administrator :: 2018-06-05 01:28:42 :: administrator -> marciana :: 1999 |
| 3. Content and structure | |
| Is the master or a copy? | is the master |
| Content Stage | completed |
| Transferable | 1 |
| Content Type | External Contribution |
| Keywords | relaxation Lagrangean and surrogate relaxation generalized assignment problem / SUBGRADIENT METHOD KNAPSACK-PROBLEM SHORTEST-PATH ALGORITHM OPTIMIZATION CONSTRAINTS MODEL |
| Abstract | 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. |
| Area | COMP |
| Arrangement | urlib.net > BDMCI > Fonds > Produção anterior à 2021 > LABAC > Lagrangean/surrogate relaxation for... |
| doc Directory Content | access |
| source Directory Content | there are no files |
| agreement Directory Content | there are no files |
| 4. Conditions of access and use | |
| Language | en |
| Target File | lagrangean.pdf |
| User Group | administrator sergio |
| Visibility | shown |
| Copy Holder | SID/SCD |
| Archiving Policy | denypublisher denyfinaldraft36 |
| Read Permission | deny from all and allow from 150.163 |
| 5. Allied materials | |
| Next Higher Units | 8JMKD3MGPCW/3ESGTTP |
| Dissemination | WEBSCI; PORTALCAPES. |
| Host Collection | sid.inpe.br/banon/2003/08.15.17.40 |
| 6. Notes | |
| Empty Fields | affiliation alternatejournal archivist callnumber copyright creatorhistory descriptionlevel documentstage doi e-mailaddress electronicmailaddress format isbn label lineage mark mirrorrepository nextedition notes orcid parameterlist parentrepositories previousedition previouslowerunit progress project readergroup rightsholder schedulinginformation secondarydate secondarymark session shorttitle sponsor subject tertiarymark tertiarytype typeofwork url versiontype |
| 7. Description control | |
| e-Mail (login) | marciana |
| update | |