Dualの考え方

 久保先生の著書中、「最適化理論に関するプロとアマの違いは、双対性や、相補性の意義を理解し活用できるかどうかである」、とあります。私自身、双対性に関しては、完全に使いこなしている訳ではないのですが、最適化を実装する上においては避けて通れません。

DUALは、目的関数ー制約が表裏一体の関係にあるという考え方です。最適化と言った場合、

■制約違反のペナルティ量を最小化する、目的関数の値を最小化すること

■制約を緩和―厳しくすること

は、独立していなくて関係がある、と言うことを示しています。一般にSimplex法で解く場合、Primalで解くかDualで解くかは、指定があります。問題を解くのに、二つのやり方があって、どちらで解いても答えは同じになる、ということでもあります。（しかし、求解時間は一般的にインスタンスにより異なる）

＜リソース制約が効いているかどうかを判定することが出来る＞

例えば、次は、Instance13のログです。

上のログは、COPTが２１３msで解けているにもかかわらず、ラベル設定法では、８９秒もかかっていることを示しています。このとき、row priceの項がDualの値を示しています。

このDualは、制約に対する値で、下の累計制約に対応しています。上で最初の項は、Pythonで書いたWeekEnd勤務の累計、2番目の項は、下の最初の時間和制約に対応します。

ここで重要なのは、Dualが０だとその制約は効いていないことを示している、ということです。殆どのDual項は、0であり、実際に効いているのは、ほぼMIN-MAX時間制約のみ、ということが分かります。