リニアペア制約の評価

 残念ながら効果は認められませんでした。

一般に数理ソルバにとって、ANDやORというオペレーションより、リニア制約、の方が簡単です。その発想で、リニアペア制約化すれば、AならばBも上手く行くのでは？という期待があったのですが、残念ながら、分岐限定による整数化で効果は少しだけあるものの、「目に見える効果としてはない」　という結果でした。

＜リニアペア制約実装は無駄ではない＞

では、無駄だったかというと、決してそうではなく、現場で、重宝して早速に使っています。

＜数理ソルバでの求解困難インスタンスの原因＞

依然として、全てではありませんが、ペア制約AならばBが大きな割合を占めていることは間違いなさそうです。リニアペア表現でも上手く行かないということは、恐らく大きな係数にその原因がありそうです。

通常の列制約ならば、

ΣA[i]＝[Min:Max]

です。つまり係数は全て１で単純な加算和が[Min:Max]の範囲内というのが一般形式です。

それに対して、ペア制約は、

ΣACoff[i]*A[i]=[Min:Max]

となる部分が異なります。例えば、会議の制約では、おおきな係数の制約となります。

現状、この部分を打開する手立てを見つけることができません。厳密解を求めたい場合は、次のような手順を取ります。

１）会議等制約含んだ全体を、AL1で解く。

２）１）で求めた会議日を予定としてハード制約化する

３）数理ソルバ（AL4)で解く

１）の時点で、厳密解ではなくなっているのですが、高々31日のBranchを試しても同じです。これで、今まで求められなかった厳密解が出てくるかもしれません。