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

Direct link
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, 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
URN: urn:nbn:se:liu:diva-48348DOI: 10.1080/02331930108844546OAI: diva2:269244
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2013-08-29

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 320 hits
ReferencesLink to record
Permanent link

Direct link