新解探索プログラム

SchedulingBenchmarkサイトで、解の更新がなされ、手持ちの新解は、全て発見されてしまいました。可能性が残っているのは、Instance15のみです。そこで、新解を発見できなくてもLBの更新を目指すことにしました。現在LBは、3823がKnown Best値となっており、3827が現在、私が持っている結果です。この時点で報告してもよいのですが、残念ながらEvidenceがありません。

計算機を廻すのは、一週間以上を想定します。次のStarategyでLBの更新を狙います。

１）DFS→ルート周りはBFSに変更


これで、少なくともLBが更新できると思います。今までは、DFS一辺倒だったのですが、LBを更新するとなると、全ての探索木で、LB以上となる証明が必要となります。そのためには、DFSではなく、BFSが必須です。しかし、全部をBFSにすると爆発して一生、Feasibleな解は見つかりません。なので、ある程度以上のdepthでは、DFSとします。これで、LBの更新と、それまでのBest解の両方を作戦です。一度限りのプログラムなので、Ifdefで作成しました。


２）部分的に問題そのものを緩和
問題を簡単にすれば、自動的にLBも下降します。しかし、そのLBがKnownBest以上である限りにおいては、LBを求める意味はあります。問題が緩和されたLBは、緩和される前のLBよりも確実に小さくなるはずです。つまり問題が緩和されたLBは、元の問題のLBとして担保できます。
しかし、注意しなければならないのは、得られた解が、元の問題上でのFeasibleな解には必ずしもならない、ということです。こうまでして緩和を行うのは、探索速度の向上が期待できるからですが、これは、問題構造を熟知しているからできることであって、汎用手段ではありません。なりふり構わず新LBを得ようとしています

略語の説明

DFS：Depth　First　Search
BFS:Breadth　First　Search
LB:　Lower　Bound