ラグランジェ緩和問題

ラグランジェ緩和の説明は、こちらが分かりやすいです。
https://www.jstage.jst.go.jp/article/bjsiam/23/3/23_KJ00008829092/_pdf/-char/en

双対問題との関連はこちら。
http://tomomi.my.coocan.jp/text/relax1.pdf

ナーススケジューリングでも一定の試みがなされています。
https://thesis.eur.nl/pub/45916/Dopheide.pdf

私もトライしてみたのですが、期待したほどよい下界値は得られませんでした。なので別な方法を採っています。　こちらは、簡単で近い上界値が得られます。