制約付最短経路問題

 は、Algorithm4の中で主要な問題です。SchedulingBenchmarksのInstance13とInstance21以上で解けない、あるいは、実務問題で解けない原因は、このSUB問題が解けないことに起因しています。たとえば、

https://ci.nii.ac.jp/naid/110002812520

は、Boostでも実装されているパレート解法の一種ですが、上記問題を解こうとすると途端にメモリが破綻するのは同じです。

Boost Graph Library: Resource-Constrained Shortest Paths - 1.40.0

実務問題の多くは、上記と同様に基数制約を多く含むこと、シフト数が多いことにより、厳密解を得ようとすると多くの実務問題で破綻します。結果Al4は使えません。

あるアイデアを思いついて試していたのですが、良いところまでは、行くのですが、厳密解を得ようとすると長大な時間がかかる場合があることが判明しました。厳密解をベースを諦め、Heuristicsの一解法ベースとして構築してもよいのですが、もう少しだけトライしてみることにしました。今までやってきた知見をフルに生かせば、多分解決できるだろうという着想を得ました。これを解決して、初めてAl4が実務問題へ投入可能になります。

https://www.jstage.jst.go.jp/article/sicejl/56/12/56_967/_pdf