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
      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
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references