LP（線形計画問題）
目的関数や制約条件がすべて一次式で表現されている場合の数理最適化問題を、LP（Linear Programming / 線形計画問題）と言います。
例題では目的関数と制約条件を表す式がすべて変数との一次式なので、この問題は線形計画問題です。この例は簡単な例なのですぐに解を求められますが、一般の線形計画問題は、多くの変数および制約条件式からなり複雑です。また、一見すると非線形計画問題と思われる問題の中にも、線形計画問題として定式化できるものがあります。
例えば、絶対値が目的関数に入っている場合は線形化できますし、最大値と最小値の差が目的関数に入っている場合も線形化できます。
本来は、非線形計画問題であっても近似的に線形計画問題と見なせる場合や、比較のために線形計画問題として近似する等の場合もあります。
また、別の数理最適化問題の緩和問題として利用されることもあり、線形計画の適用例は、広範囲に渡ると言ってもいいでしょう。現在では、シンプレックス法の改良や内点法の発展により、これらの問題に対して、 最適解を高速に求めることができます。最適解であることは理論的に保証され、また双対変数を利用した感度情報も得られます。
ビジネスシーンでの線形計画問題例
輸送問題：変数は輸送量、目的関数は輸送コスト(最小化)、制約条件は需要の充足、センター最大保管料等
配合問題：変数は原料使用量、目的関数は原料コスト(最小化)、制約条件は成分の上限/下限
資金計画問題：変数は投資金額、目的関数は利益、制約条件は資金量
QP（二次計画問題）
目的関数が二次式で制約条件が一次式の問題を、QP（Quadratic Programming / 二次計画問題）と言います。例えば、輸送費が輸送量に一定の係数を掛けて求めていて、その係数が輸送量の一次式である場合は二次計画問題になります。また、概念自体が二次のものもあります。例えば、三角形の土地に最も大きな正方形の家を建てたい時、どれだけの大きさの家が建てられるかは二次計画問題になります。面積が辺の長さの二乗になるからです。
パラメータの最小二乗推定問題は、目的関数がすべて二次式ですのでQPになります。また、実験データのフィッティング問題、線形動的システムの同定問題等があります。金融におけるポートフォリオ最適化に対する平均・分散モデルもそうです。
そこでは、期待利益がある値以上という制約の下で、リスク分散（二次式）を最小にします。その他、製造業では負荷の平準化の概念がよく用いられますが、負荷を分散ととらえるとQPになります。
世の中にQPは、数多く存在します。面積や輸送における距離と重量の積および分散等は、自然に二次式になるからです。 すべてのQPが効率よく解けるわけではありませんが、目的関数が凸二次式の場合は、効率よく解くことができます。関数が凸というのは、関数上の任意の異なる2点をとった時、その2点を結ぶ線分が関数より上にあるという性質を持つことです。目的関数を行列形で
と書いた時、二次の項を形成する行列Fが半正定値の場合、関数は凸になります。
y = 2x² はその特別なケースで、二次の係数2が正なので凸です。よく知られているように、このような二次関数は閉区間では最小解を持ち、極小解は持ちません。
QCP（二次制約問題）
約条件が二次式の場合の数理最適化問題を、QCP（Quadratic Constrained Programming / 二次制約問題）と言います。目的関数は、一次式または二次式です。
QPのところでも説明しましたが、線形計画問題における一次式制約の係数が定数でなく変数の一次式で表される場合は、QCPになります。また、QPを最小化すべき目的関数に上限変数を導入し、新たな目的関数はその上限変数の最小化となり、元の目的関数が上限変数以下という制約条件のある問題に定式化し直すとQCPになります。
金融におけるポートフォリオ最適化に対する平均・分散モデルで、リスク分散を指定値以下に抑えるという制約条件で期待利益率を最大にするという問題や、客先から距離がある値以下となる場所に拠点を選ぶという問題は、QCPになります。
二次制約条件が形成する実行可能領域が凸集合の場合には、効率的に解くことができます。凸集合というのは、その中の任意の異なる2点をとった時、その2点を結ぶ線分が必ずその中に入っているという性質を持つ集合です。凸集合の共通集合は凸集合ですので、凸集合になる二次制約がいくつあっても同じです。
変数 x をとすると、一般に二次制約式は行列形で
と書けますが、このとき二次の項を形成する行列が半正定値行列の場合は、領域が凸集合になります。直観的には、楕円（楕円体）をイメージしてください。
それ以外に、二次制約条件式が二次錐制約になる場合も、領域は凸集合になります。二次錐制約というのは
という形で書ける二次制約条件式です。n は、変数の次元です。
円錐をイメージすると、直感的に分かりやすくなります。前述の凸二次制約式も、二次錐制約に変換することができます。 y ≧ |x| は二次元の、 z² ≧ x² + y² および yz ≧ x² は三次元の二次錐制約の代表例です。
MILP（混合整数線形計画問題）
原料の重量や体積などを変数にとる場合、その値としては10.23、10.23567、・・・などのような小さい値をとることができます。このような変数は、連続変数と呼ばれます。
これに対し1個、2個とか1日目、2日目などのような値が変数になる場合、途中の1.2個とか1.7日目などは除外されますので、許容される変数はとびとびの値しかとりません。このように、とびとびの値しかとらない変数は、離散変数と言われます。
離散変数は先に挙げた例のように、基本的に整数変数とみなすことができます。0.1ピッチで0.1、0.2、0.3…という値しかとらない変数も見かけ上、整数ではありませんが、これは1、2、3…を0.1倍したものですから、基本的には整数変数とみなすことができます。
変数の中に連続変数だけでなく整数変数が混じっている数理最適化問題は、その頭に混合整数が付きます。従って、MILP（Mixed Integer Linear Programming / 混合整数線形計画問題）は線形計画問題であって、変数の中に整数変数が混じっているものということになります。
ビジネスシーンでの混合整数線形計画問題例
実は数理最適化問題の中で応用上多く現れるにも拘わらず、主として計算時間がかかるために解くのが難しいとされている組合せ最適化問題の多くが、MILPでモデル化できます。組合せ最適化問題では制約条件が論理的な条件で表されることが多いですが、それらは、条件の成否に対応して1と0の値をとる論理変数を導入することにより表現できます。また、スケジューリング問題等で時間の概念を扱う場合でも、開始時刻に対応する離散変数を導入したり、計画対象の時間範囲を細かい間隔に離散化するなどの方法によって、MILPとしてモデル化することができます。
このように多くの問題が、MILPとして表現できます。
施設配置計画問題
統廃合問題では、施設を使用するかどうかの0-1変数、新設計画では、候補施設の中で選ぶかどうかの0-1変数が導入される。輸配送問題
輸送品の個数、トラックの台数などが整数変数スケジューリング問題
開始時刻、ジョブの先行、マシン上でジョブが重ならないなどの定式化に0-1変数が導入される。カッティングストック問題
各カッティングパターンを選ぶ個数が整数変数
また一見すると非線形計画問題と思われる問題の中にも、MILPとして定式化できるものがあります。それは、目的関数や制約条件に非線形関数が入っている場合です。非線形関数と言っても、定義されている範囲内で有界であればその範囲をいくつかに分割し、各部分区間内では一次関数で近似することができます。この区分線形近似は、MILPで定式化できます。
MIPは分枝限定法の分枝操作の工夫、効果的なカットの導入、行列操作の工夫、並列化などにより高速に解けるようになってきています。仮に計算時間がかかる難しい問題を計算途中で打ち切っても、ギャップの値（上界と下界の差）から最適解にどの程度近いかを知ることもできます。
MIQP（混合整数二次計画問題）
二次計画問題の変数の中に整数変数が混じっている時、その二次計画問題はMIQP（Mixed Integer Quadratic Programming / 混合整数二次計画問題）と言います。
二次計画問題の多くは、変数に使用個数制限や論理条件に対応する0-1変数が導入されることによりMIQPになります。
例えば、パラメータの推定問題に最小二乗法を適用する場合、その問題は二次計画問題になりますが、パラメータの数は多すぎると過剰推定を引き起こすことはよく知られており、パラメータの数はある基準を満たすように決定するのが良いとされています。
赤池情報量基準（AIC）は、その一つです。そこでパラメータを選択するかしないかの0-1変数を導入し、パラメータの数も評価に加えると、その問題はMIQPになります。それ以外にも、金融におけるポートフォリオ最適化問題の平均・分散モデルにおける銘柄選択数に制限をつける場合の問題があります。最適制御あるいはモデル予測制御において、装置の起動/停止に対応する0-1変数を導入して最適制御問題を解くという問題は、論理条件に対応する0-1変数が導入されたMIQPの例です。
MIQCP（混合整数二次制約問題）
二次制約問題では変数がすべて連続ですが、これに整数変数が混じるとMIQCP（Mixed Integer Quadratic Constrained Programming / 混合整数二次制約問題）になります。
MILPに二次制約が付加された問題が、MIQCPの典型例です。要員のばらつきを指定値以下に抑えるという制約も加わったスケジューリング問題は、そのような例です。
Non-convex MIQCP（混合整数非凸二次制約）
お気軽にお問い合わせください
以下の中からお問い合わせしたい内容に最も合うものを選択して、お問い合わせフォームに必要事項をご入力ください。なお、営業目的のメールはご遠慮ください。
製品見積・購入関連
当社製品の価格・オプションについては、こちらより営業チームにご相談ください。
評価版ライセンス関連
当社製品の評価版ライセンスの申請については、こちらよりお申し込みください。
その他
当社製品に関するコンサルティングサービス、ライセンス更新関連、パートナープログラム等については、こちらよりお問い合せください
当社製品に関するサポートは、こちらをご覧ください。
取材やプレス関連お問合せは、marketing-japan@gurobi.com までご連絡ください。
