liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Experiments with primal - dual decomposition and subgradient methods for the uncapacitatied facility location problem
Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.ORCID iD: 0000-0001-5907-0087
2001 (English)In: Optimization, ISSN 0233-1934, E-ISSN 1029-4945, Vol. 49, no 5-6, 495-516 p.Article in journal (Refereed) Published
Abstract [en]

For optimization problems that are structured both with respect to the constraints and with respect to the variables, it is possible to use primal–dual solution approaches, based on decomposition principles. One can construct a primal subproblem, by fixing some variables, and a dual subproblem, by relaxing some constraints and king their Lagrange multipliers, so that both these problems are much easier to solve than the original problem. We study methods based on these subproblems, that do not include the difficult Benders or Dantzig-Wolfe master problems, namely primal–dual subgradient optimization methods, mean value cross decomposition, and several comtbinations of the different techniques. In this paper, these solution approaches are applied to the well-known uncapacitated facility location problem. Computational tests show that some combination methods yield near-optimal solutions quicker than the classical dual ascent method of Erlenkotter

Place, publisher, year, edition, pages
2001. Vol. 49, no 5-6, 495-516 p.
Keyword [en]
decomposition methods, Lagrange multipliers, subgradient optimization, uncapacitated facility location
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-48348DOI: 10.1080/02331930108844546OAI: oai:DiVA.org:liu-48348DiVA: diva2:269244
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2017-12-12

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Holmberg, Kaj

Search in DiVA

By author/editor
Holmberg, Kaj
By organisation
Department of MathematicsThe Institute of Technology
In the same journal
Optimization
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 332 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf