拉格朗日啟發式算法

拉格朗日鬆弛算法有兩個用途，一個是提供計算值的下界（用於評價計算結果）；另一個就是拉格朗日鬆弛啟發式算法。

定義

拉格朗日鬆弛算法有兩個用途，一個是提供計算值的下界（用於評價計算結果）；另一個就是拉格朗日鬆弛啟發式算法。

拉格朗日啟發式算法主要包括兩部分：拉格朗日次梯度的最佳化計算；對第一部分得到的解進行改進，使其可行。

舉例

對於集合覆蓋問題有如下數學模型：

假設

則有如下式子成立：

此時第三行沒有被覆蓋，可在覆蓋第三行中選取費用最小列

替代

得到

此時，LR 的最優解為