Aarhus University Seal / Aarhus Universitets segl

An improved Lagrangian relaxation and dual ascent approach to facility location problems

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisTidsskriftartikelForskningpeer review

Standard

An improved Lagrangian relaxation and dual ascent approach to facility location problems. / Jörnsten, Kurt; Klose, Andreas.

I: Computational Management Science, Bind 13, Nr. 3, 2016, s. 317-348.

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisTidsskriftartikelForskningpeer review

Harvard

APA

CBE

MLA

Vancouver

Author

Jörnsten, Kurt ; Klose, Andreas. / An improved Lagrangian relaxation and dual ascent approach to facility location problems. I: Computational Management Science. 2016 ; Bind 13, Nr. 3. s. 317-348.

Bibtex

@article{104a7b6811dd4262ab52d94f64271c7c,
title = "An improved Lagrangian relaxation and dual ascent approach to facility location problems",
abstract = "The literature knows semi-Lagrangian relaxation as a particular way of applying Lagrangian relaxation to certain linear mixed integer programs such that no duality gap results. The resulting Lagrangian subproblem usually can substantially be reduced in size. The method may thus be more efficient in finding an optimal solution to a mixed integer program than a “solver” applied to the initial MIP formulation, provided that “small” optimal multiplier values can be found in a few iterations. Recently, a simplification of the semi-Lagrangian relaxation scheme has been suggested in the literature. This “simplified” approach is actually to apply ordinary Lagrangian relaxation to a reformulated problem and still does not show a duality gap, but the Lagrangian dual reduces to a one-dimensional optimization problem. The expense of this simplification is, however, that the Lagrangian subproblem usually can not be reduced to the same extent as in the case of ordinary semi-Lagrangian relaxation. Hence, an effective method for optimizing the Lagrangian dual function is of utmost importance for obtaining a computational advantage from the simplified Lagrangian dual function. In this paper, we suggest a new dual ascent method for optimizing both the semi-Lagrangian dual function as well as its simplified form for the case of a generic discrete facility location problem and apply the method to the uncapacitated facility location problem. Our computational results show that the method generally only requires a very few iterations for computing optimal multipliers. Moreover, we give an interesting economic interpretation of the semi-Lagrangian multiplier(s).",
keywords = "Mixed integer programming , Lagrangian relaxation, Semi-Lagrangian relaxation, Facility location, Uncapacitated facility location problem",
author = "Kurt J{\"o}rnsten and Andreas Klose",
year = "2016",
doi = "10.1007/s10287-015-0244-z",
language = "English",
volume = "13",
pages = "317--348",
journal = "Computational Management Science",
issn = "1619-697X",
publisher = "Springer",
number = "3",

}

RIS

TY - JOUR

T1 - An improved Lagrangian relaxation and dual ascent approach to facility location problems

AU - Jörnsten, Kurt

AU - Klose, Andreas

PY - 2016

Y1 - 2016

N2 - The literature knows semi-Lagrangian relaxation as a particular way of applying Lagrangian relaxation to certain linear mixed integer programs such that no duality gap results. The resulting Lagrangian subproblem usually can substantially be reduced in size. The method may thus be more efficient in finding an optimal solution to a mixed integer program than a “solver” applied to the initial MIP formulation, provided that “small” optimal multiplier values can be found in a few iterations. Recently, a simplification of the semi-Lagrangian relaxation scheme has been suggested in the literature. This “simplified” approach is actually to apply ordinary Lagrangian relaxation to a reformulated problem and still does not show a duality gap, but the Lagrangian dual reduces to a one-dimensional optimization problem. The expense of this simplification is, however, that the Lagrangian subproblem usually can not be reduced to the same extent as in the case of ordinary semi-Lagrangian relaxation. Hence, an effective method for optimizing the Lagrangian dual function is of utmost importance for obtaining a computational advantage from the simplified Lagrangian dual function. In this paper, we suggest a new dual ascent method for optimizing both the semi-Lagrangian dual function as well as its simplified form for the case of a generic discrete facility location problem and apply the method to the uncapacitated facility location problem. Our computational results show that the method generally only requires a very few iterations for computing optimal multipliers. Moreover, we give an interesting economic interpretation of the semi-Lagrangian multiplier(s).

AB - The literature knows semi-Lagrangian relaxation as a particular way of applying Lagrangian relaxation to certain linear mixed integer programs such that no duality gap results. The resulting Lagrangian subproblem usually can substantially be reduced in size. The method may thus be more efficient in finding an optimal solution to a mixed integer program than a “solver” applied to the initial MIP formulation, provided that “small” optimal multiplier values can be found in a few iterations. Recently, a simplification of the semi-Lagrangian relaxation scheme has been suggested in the literature. This “simplified” approach is actually to apply ordinary Lagrangian relaxation to a reformulated problem and still does not show a duality gap, but the Lagrangian dual reduces to a one-dimensional optimization problem. The expense of this simplification is, however, that the Lagrangian subproblem usually can not be reduced to the same extent as in the case of ordinary semi-Lagrangian relaxation. Hence, an effective method for optimizing the Lagrangian dual function is of utmost importance for obtaining a computational advantage from the simplified Lagrangian dual function. In this paper, we suggest a new dual ascent method for optimizing both the semi-Lagrangian dual function as well as its simplified form for the case of a generic discrete facility location problem and apply the method to the uncapacitated facility location problem. Our computational results show that the method generally only requires a very few iterations for computing optimal multipliers. Moreover, we give an interesting economic interpretation of the semi-Lagrangian multiplier(s).

KW - Mixed integer programming

KW - Lagrangian relaxation

KW - Semi-Lagrangian relaxation

KW - Facility location

KW - Uncapacitated facility location problem

U2 - 10.1007/s10287-015-0244-z

DO - 10.1007/s10287-015-0244-z

M3 - Journal article

VL - 13

SP - 317

EP - 348

JO - Computational Management Science

JF - Computational Management Science

SN - 1619-697X

IS - 3

ER -