キャパシティカットの効果

 前回のキャパシティカットをScheduling Benchmarksのインスタンスに適用してみました。

LBとは、LowerBoundで、LPソルバが出力するObjValueになります。一般にはFractionalな値になります。適用前、適用後でどのようにこの値が変化するかをまとめたのが下表です。

例えば、インスタンス７では、キャパシティカット適用前32だったLBが926に急上昇していることが分かります。厳密解UBに近くなってきていることが分かります。

キャパシティカット適用前instance7、Highsは、1日廻しても解けませんでしたが、適用後は、447秒で解けています。

COPTに至っては、僅か18秒で解けました。

このように、絶大な効果を発揮するインスタンスがある一方で、殆どLBが上がらないインスタンスもあります。この違いは何でしょうか？　

恐らくは、エラー発生箇所の違いによるものでしょう。このキャパティカットは、スタッフの土日の休み数制限、言い換えるとスタッフ側勤務可能キャパシティをカバー制約に伝える働きがあると考えられます。土日勤務に関するカバー制約に対するスラックが0でなくなることの理由付けになります。土日勤務で発生するカバー制約エラーに対して作用します。つまり、土日カバー制約エラーが発生しているインスタンスでは効果がありますが、元々、発生していないインスタンスでは効果がない、と考えられます。

＜LBを上げることは正義＞

一般に厳密解を得る上で、重要なのは、LBを上げる操作です。極論を言えば、LBがUBに限りなく等しければ、解けたも同然です。LBがUBに近ければ近い程、打てる手は多くなります。

＜数式だけでは推測しにくい、インスタンス構造に応じたカットを見つける＞

MPSとかLPとかあるいは、CNF/WCNF とか数式モデル化してしまうと、もはや土日の勤務数という、問題構造由来視点での効果的なカットを見つけることは困難です。MIPソルバは、自動でカットを適用しますが、問題構造は分かっていないので往々にして、やみくもカットになることが多いです。もっと効果的なのは、問題自体を作成した作成者自身がインスタンス特性を知っているはずなので、作成者自身がカットを適用することです。