最適化セミナーのご案内

14.1 数理計画問題一覧

 Numerical Optimizerでは,以下のような数理計画問題を取り扱うことができます.

  • LP (Linear Programming:線形計画問題)
    目的関数と制約式がすべて線形である問題で,整数変数を含まないものです.
  • MILP (Mixed Integer Linear Programming:混合整数計画問題)
    目的関数と制約式がすべて線形で,整数変数を含むものです.MIP(Mixed Integer Programming)と呼ばれることも多いです.
  • MIQP (Mixed Integer Quadratic Programming:混合整数二次計画問題)
    制約式がすべて線形,目的関数が二次関数で,整数変数を含むものです.
  • MINLP (Mixed Integer Nonlinear Programming:混合整数非線形計画問題)
    制約式および目的関数が非線形で整数変数を含むものです.
  • CQP (Convex Quadratic Programming:凸二次計画問題)
    目的関数が凸な二次関数,制約式がすべて線形であるもの(ただし,目的関数の符号の変更で下に凸な目的関数の最小化に帰着できるもの)です.
  • CP (Convex Programming:凸計画問題)
    目的関数,制約式に非線形なものが含まれていますが,実行可能領域が凸で,目的関数の符号の変更で下に凸な目的関数の最小化に帰着できる問題です.ここでは整数変数は含まないものを言います.
    半正定値計画問題も凸計画問題の一部ですが,ここには含めません.
  • NLP (Nonlinear Programming:非線形計画問題)
    上記以外で,整数変数を含まない一般の非線形計画問題です.
  • SDP (SemiDefinite Programing:半正定値計画問題)
    行列の半正定値制約を含む線形計画問題です.
  • NLSDP (NonLinear SemiDefinite Programing:非線形半正定値計画問題)
    行列の半正定値制約を含み,なおかつ目的関数・制約式に非線形項が含まれる問題です.
  • WCSP (Weighted Constraint Satisfaction Problem:重み付き制約充足問題)
    各々重みの付いた制約条件をなるべく満足するためには値をどのように割り当てると良いかを決定する問題です.制約充足問題ソルバwcspにより高速に解を得ることができます.
  • RCPSP (Resource Constrained Project Scheduling Problem:資源制約付きスケジューリング問題)
    一定の資源制約の下で,決められた作業の開始・終了時刻を決定する問題です.一般の整数計画問題(MILP)として記述することも可能ですが,特殊な記法を行うと資源制約付きスケジューリング問題ソルバrcpspにより高速に実行可能解を得ることができます.

 

 

上に戻る