Lagrangian Relaxation and the Single-Source Capacitated Facility-Location Problem
本文指出在单源容量设施选址问题中，拉格朗日松弛方法若松弛容量约束，无论乘子如何取值都会得到不可行解，且边界较差，建议先做可行性分析。
Lagrangian relaxation has been widely used in solving a number of hard combinatorial optimization problems. The success of the approach depends on the structure of the problem and on the values assigned to the Lagrange multipliers. A recent paper on the single-source capacitated facility-location problem proposed the use of Lagrangian relaxation in which the capacity constraints were relaxed. In this paper, a class of such problems is defined for which the proposed relaxation is guaranteed to result in an infeasible solution, irrespective of the values assigned to the Lagrange multipliers. In these cases, the bounds on the optimal solution, obtained from the relaxation, are generally poor. It is concluded that, when using Lagrangian relaxation, it may be worthwhile carrying out a preliminary analysis to determine the potential viability of the approach before extensive development takes place.