トップ > 製品概要 > Numerical Optimizer の更新情報 > Numerical Optimizer V17 の更新情報

Numerical Optimizer V17 更新情報

Numerical Optimizer V17 の新機能等を紹介いたします。

  1. 分枝限定法前処理部の増強
  2. 厳密解法と wcsp ヒューリスティクスの融合
  3. 行列表現を用いない内点法
  4. 入力インタフェース強化

1. 分枝限定法前処理部の増強

常に改良を続けている分枝限定法ですが、今回のリリースでは、論理制約に基いた切除平面の追加と制約式の補強ノウハウの導入、解法エンジンとなる単体法のプライシングの改良が主な眼目となります。「ルート問題で既に最適解」という方向により近づき、大規模問題の対応力が高まっています。

2. 厳密解法と wcsp ヒューリスティクスの融合

Numerical Optimizer にはシフトスケジューリングや時間割などの離散計画問題に大きな強みを発揮する wcsp というヒューリスティクスと分枝限定法による厳密解法を備えておりましたが、解法エンジンとしては独立なもので、ユーザーからの呼び分けが必要でした。V17 からヒューリスティクスアルゴリズム wcsp を、連続変数を含む問題に適用することができるようになりました。その際には分枝限定法ならではの、論理制約に着目した強力な前処理が適用されるので、以前の wcsp が苦手としていた論理制約が解空間を狭くしているケースへの対処が可能です。分枝限定法からも以前の単体法ベースのヒューリスティクスに加えて wcsp が起動されるようになり、大規模問題に対する解の探索力が向上、実務的な難問により強力にアプローチします。

3. 行列表現を用いない内点法

最近の研究で内点法のステップ方向ベクトルを求める際に現れる行列に対する理解が進み、その成果としてソルバーに制約式行列を入力しなくても、制約式行列とベクトルの積を計算するインタフェースがあれば機能する内点法を実装しました。行列がメモリに乗りきらない大規模ネットワークや分布の制御など、数値的な性質よりも規模が問題となる超大規模な線形計画問題に福音となる新技術です。ご期待ください。

4. 入力インタフェース強化

より手軽にお試しになりたい方へ、モデリング言語 SIMPLE を介さずにスタンダードな LP ファイルからの入力インタフェースや、セパレータを半角スペースとする拡張された MPS ファイルからの入力インタフェースを用意しました。 併せて SIMPLE で表現したモデルから LP ファイルを出力する機能も追加しました。

SIMPLELP ファイル
Variable x;
IntegerVariable y;

Objective obj(type = minimize);
obj = 180 * x + 160 * y;

6 * x + y >= 12;
4 * x + 6 * y >= 24;
0 <= x <= 5;
0 <= y <= 5;

lpout(); // LP ファイル作成
MIN
 obj : 180 X1 + 160 X2
SUBJECT TO
 F1 : 6 X1 + X2 >= 12
 F2 : 4 X1 + 6 X2 >= 24
BOUNDS
 X1 <= 5 
 X2 <= 5 
GENERALS
 X2
END