A Cross Decomposition Algorithm for Capacitated Facility Location (Q3725832)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3956775
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A Cross Decomposition Algorithm for Capacitated Facility Location |
scientific article; zbMATH DE number 3956775 |
Statements
A Cross Decomposition Algorithm for Capacitated Facility Location (English)
0 references
1986
0 references
cross decomposition method
0 references
primal subproblem
0 references
capacitated facility location
0 references
dual subproblem
0 references
Lagrangean relaxation
0 references
plant location
0 references
dual ascent method
0 references
adjustment procedure
0 references
computational results
0 references
0.8541231155395508
0 references
0.8453081846237183
0 references
The cross decomposition method involves successive solutions to a primal subproblem and to a dual one. The primal subproblem is obtained by fixing all the binary variables in the capacitated facility location problem P: it is a transportation problem which is precisely the subproblem used in the Benders decomposition algorithm applied to P. The dual subproblem is obtained by fixing the dual variables in the Lagrangean relaxation of P relative to the capacity constraints: it is a simple plant location problem which can be solved by a dual ascent method via an adjustment procedure. Both subproblems are used into a single decomposition framework, producing successive upper and lower bounds on the optimal value of P. The method is carefully described. Finally, various computational results are given, showing that, in particular, the cross decomposition approach can be used for solving large capacitated facility location problems.
0 references