Instance13速度改善

 前回報告よりさらに速度アップしました。(5091sec→3019sec)です。

これは、マルチスレッド方法の見直しによるものです。LpSolverは、CLPのままです。

CPUのUsageをモニタすると下のようになっています。三角の頂点部分は、マルチスレッド化している部分でOPEN_MPにより使用可能なスレッドが全て投入されます。底辺部分は、シングルスレッドで動いている部分です。このCPUは、4threadsなので、シングルスレッドの使用率は25%です。この部分はほぼLPSolverが占有しています。

通常の規模程度（Instance8）では、LPSolverの時間はほぼ無視できる程短いので、下のように、ほぼ、全期間フルスレッドで働いているように見えます。（一方のInstance13は、１monthではありますが、スタッフ数120人と大規模インスタンスですので、LpSolverの計算に食います。）

前記三角頂点部は、大規模になってもスレッド数を増やせば補償できる部分です。ところが、シングルスレッド部である底辺部は、補償できません。よって大規模インスタンスでは、LpSolverの性能がネックになる、ということが言えます。

マルチスレッド数とNSP問題探索速度の関係

一般にインスタンス規模は、指数関数的に増加します。それ故、メタヒューリスティクス系では、マルチスレッド化してもさほど効果は感じられないと思います。

MIPソルバのKeyは、BranchAndBoundですが、Treeの性質を考えると√倍程度の効果（４Threadsで2倍の速度）のように思います。Algorithm4も基本的には、B&Bですので、100%CPUを使い切ったときに、√倍程度の改善と考えられます。