Sayyed Ehsan Monabbati - Department of Mathematics, Alzahra University, Vanak Street, Tehran, Iran

It is shown that for integer programming problems, the augmented Lagrangian relaxation usually provides tighter bounds than Lagrangian relaxation. In this note we propose a lower bound on the penalty parameter of the augmented Lagrangian of the well-known uncapacitated facility location problem (UFLP). This lower bound depends on the input data of the problem, and with penalty parameter above the proposed lower bound, the value provided by the augmented Lagrangian relaxation is equal to the optimal value of the problem.

Augmented Lagrangian, Uncapacitated Facility Location Problem