株式会社オクトーバー・スカイ October Sky Co., Ltd.loading
  1. HOME
  2. 製品情報
  3. サポートしている解法

サポートしている解法

Gurobi Optimizerを使用することで、数理最適化問題を解くことができます。数理最適化問題は、解の候補の中から最も評価の良いものを見つける問題です。数理最適化問題が数式で表現されている時、評価を表す関数を目的関数と言い、解が候補となる条件を制約条件式と言います。

LP(線形計画問題)

目的関数や制約条件がすべて一次式で表現されている場合の 数理最適化問題を、LP(Linear Programming /線形計画問題)と言います。

LPの例題

1g 10 円の原料 A と 1g 20 円の原料 B を混ぜて、製品を 100g以上作らなければならない。最も安価にすませるには、どのように混ぜるとよいでしょうか?

回答

原料 A をxg、B をyg とした場合、原料費を最も安価したいので目的関数は 10x+20y となり、この目的関数を最小化する解を求めます。この場合の制約条件は、x+y≧100、x,y≧0。

解:x=100, y=0。

例題では目的関数と制約条件を表す式がすべて変数xとyの一次式なので、この問題は線形計画問題です。この例は簡単な例なのですぐに解を求められますが、一般の線形計画問題は多くの変数および制約条件式からなり複雑です。また、一見すると非線形計画問題と思われる問題の中にも、線形計画問題として定式化できるものがあります。
例えば、絶対値が目的関数に入っている場合は線形化できますし、最大値と最小値の差が目的関数に入っている場合も線形化できます。
本来は、非線形計画問題であっても近似的に線形計画問題と見なせる場合や、比較のために線形計画問題として近似するなどの場合もあります。
また、別の数理最適化問題の緩和問題として利用されることもあり、線形計画の適用例は、広範囲に渡ると言ってもいいでしょう。現在では、シンプレックス法の改良や内点法の発展により、これらの問題に対して、 最適解を高速に求めることができます。最適化であることは理論的に保証され、また双対変数を利用した感度情報も得られます。

ビジネスシーンでの線形計画問題例

  • 輸送問題:

    変数は輸送量、目的関数は輸送コスト(最小化)、制約条件は需要の充足、センターの最大保管量などです。

  • 配合問題:

    変数は原料使用量、目的関数は原料コスト(最小化)、制約条件は成分の上限/下限

  • 資金計画問題:

    変数は投資金額、目的関数は利益、制約条件は資金量

QP(二次計画問題)

目的関数が二次式で制約条件が一次式の問題をQP(Quadratic Programming/二次計画問題)と言います。例えば、輸送費が輸送量に一定の係数を掛けて求めていて、その係数が輸送量の一次式である場合は二次計画問題になります。また、概念自体が二次のものもあります。例えば、三角形の土地に最も大きな正方形の家を建てたい時、どれだけの大きさの家が建てられるかは二次計画問題になります。面積が辺の長さの二乗になるからです。

パラメータの最小二乗推定問題は、目的関数がすべて二次式ですのでQPになります。また、実験データのフィッティング問題、線形動的システムの同定問題などがあります。金融におけるポートフォリオ最適化に対する平均・分散モデルもそうです。
そこでは、期待利益がある値以上という制約の下で、リスク分散(二次式)を最小にします。その他、製造業では負荷の平準化の概念がよく用いられますが、負荷を分散ととらえるとQPになります。

世の中にQPは数多く存在しています。面積や輸送における距離と重量の積および分散などは自然に二次式の形になるからです。
すべてのQPが効率よく解けるわけではありませんが、目的関数が凸二次式の場合は、効率よく解くことができます。関数が凸というのは、関数上の任意の異なる2点をとった時、その2点を結ぶ線分が関数より上にあるという性質を持つことです。目的関数を行列形で

と書いた時、二次の項を形成する行列Fが半正定値の場合、関数は凸になります。
y=2x2はその特別なケースで、二次の係数2が正なので凸です。よく知られているように、このような二次関数は閉区間では最小解を持ち、極小解は持ちません。

QCP(二次制約問題)

制約条件が二次式の場合の数理最適化問題を、QCP(Quadratic Constrained Programming/二次制約問題)と言います。目的関数は、一次式または二次式です。

QPところでも説明しましたが、線形計画問題における一次式制約の係数が定数でなく変数の一次式で表される場合は、QCPになります。また、QPを最小化すべき目的関数に上限変数を導入し、新たな目的関数はその上限変数の最小化となり、元の目的関数が上限変数以下という制約条件のある問題に定式化し直すと、QCPになります。

金融におけるポートフォリオ最適化に対する平均・分散モデルで、リスク分散を指定値以下に抑えるという制約条件で期待利益率を最大にするという問題や客先からの距離がある値以下となる場所に拠点を選ぶという問題は、QCPになります。

二次制約条件が形成する実行可能領域が凸集合の場合には、効率的に解くことができます。
凸集合というのは、その中の任意の異なる2点をとった時、その2点を結ぶ線分が必ずその中に入っているという性質を持つ集合です。凸集合の共通集合は凸集合ですので、凸集合になる二次制約がいくつあっても同じです。
変数をxとすると、一般に二次制約式は行列形で

と書けますが、このとき二次の項を形成する行列 F が半正定値行列の場合は、領域が凸集合になります。直観的には、楕円(楕円体)をイメージしてください。

それ以外に、二次制約条件式が二次錐制約になる場合も、領域は凸集合になります。二次錐制約というのは

という形で書ける二次制約条件式です。n は、変数の次元です。

円錐をイメージすると、直感的に分かりやすくなります。前述の凸二次制約式も、二次錐制約に変換することができます。y≧|x| は二次元の、z2≧x2+y2 および yz≧x2 は三次元の、二次錐制約の代表例です。

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の例題

太郎君は、今手元につぎの3種類のお菓子を持っています。

  • 菓子A 1個120円で重さ100g、5個
  • 菓子B 1個300円で重さ200g、3個
  • 菓子C 1個400円で重さ300g、3個

これを袋に詰めて花子さんに持って行きたいのですが、袋には1,000gまでしか入れられません。合計金額が最も高くなるようにするには、どのお菓子を何個詰めるとよいでしょうか?

回答

変数は、菓子A、B、Cの個数xA、xB、xCですので整数変数です。目的関数と制約条件は以下のようになります。

目的関数:120xA+300xB+400xC → 最大
制約条件:100xA+200xB+300xC ≦ 1000
xA, xB, xC ≧ 0、整数

ビジネスシーンでのMILPの例

実は数理最適化問題の中で、応用上多く現れるにも拘わらず主として計算時間がかかるために解くのが難しいとされている組合せ最適化問題の多くが、MILPでモデル化できます。組合せ最適化問題では制約条件が論理的な条件で表されることが多いですが、それらは、条件の成否に対応して1と0の値をとる論理変数を導入することにより表現できます。また、スケジューリング問題などで時間の概念を扱う場合でも、開始時刻に対応する離散変数を導入したり、計画対象の時間範囲を細かい間隔に離散化するなどの方法によって、MILPとしてモデル化することができます。

このように多くの問題が、MILPとして表現できます。

  • 施設配置計画問題:

    統廃合問題では、施設を使用するかどうかの0-1変数、新設計画では候補施設の中で選ぶかどうかの0-1変数が導入される。

  • 輸配送問題:

    輸送品の個数、トラックの台数などが整数変数。

  • スケジューリング問題:

    開始時刻、ジョブの先行、マシン上でジョブが重ならないなどの定式化に、0-1変数が導入される。

  • カッティングストック問題:

    各カッティングパターンを選ぶ個数が整数変数。

また一見すると非線形計画問題と思われる問題の中にも、MILPとして定式化できるものがあります。それは、目的関数や制約条件に非線形関数が入っている場合です。非線形関数と言っても定義されている範囲内で有界であればその範囲をいくつかに分割し、各部分区間内では一次関数で近似することができます。この区分線形近似は、MILPで定式化できます。

MIPは分枝限定法の分枝操作の工夫、効果的なカットの導入、行列操作の工夫、並列化などにより高速に解けるようになってきています。仮に計算時間がかかる難しい問題を計算途中で打ち切っても、ギャップの値(上界と下界の差)から最適解にどの程度近いかを知ることもできます。

MIQP(混合整数二次計画問題)

二次計画問題の変数の中に整数変数が混じっている時、その二次計画問題はMIQP(Mixed Integer Quadratic Programming/混合整数二次計画問題)と言います。

MIQPの例題

地域のイベントに特産のお菓子をA、B、Cの3種類提供することになりました。A、B、Cそれぞれ少なくとも2個は用意し、合わせて10個以上を用意したいと思っています。ただ単価がAとBは手間がかかるので、Aは1個だと1,000円、それより多い注文に対しては1個あたり200円割り増しされます。同様に、Bは1個だと1,100円、それより多い注文に対しては1個あたり120円割り増しされます。Cは、個数に関係なく1個あたり1,500円です。合計金額をできるだけ抑えるには、A、B、Cをそれぞれ何個注文すればよいでしょうか?

回答

変数xA、xB、xCをそれぞれA、B、Cの注文個数とすると、この数理最適化問題は次のように定式化されます。

目的関数: (800+200xA)xA+(980+120xB)xB+1500xC → 最小
制約条件:xA, xB, xC ≧ 10
xA, xB, xC ≧ 2、整数
これは、変数が整数変数で目的関数が二次式ですので、MIQPです。

二次計画問題の多くは、変数に使用個数制限や論理条件に対応する0-1変数が導入されることにより、MIQPになります。

例えば、パラメータの推定問題に最小二乗法を適用する場合、その問題は二次計画問題になりますが、パラメータの数は多すぎると過剰推定を引き起こすことはよく知られており、パラメータの数はある基準を満たすように決定するのが良いとされています。

赤池情報量基準(AIC)は、その一つです。そこでパラメータを選択するかしないかの0-1変数を導入し、パラメータの数も評価に加えると、その問題はMIQPになります。それ以外にも、金融におけるポートフォリオ最適化問題の平均・分散モデルにおける銘柄選択数に制限をつける場合の問題があります。最適制御あるいはモデル予測制御において、装置の起動/停止に対応する0-1変数を導入して最適制御問題を解くという問題は、論理条件に対応する0-1変数が導入されたMIQPの例です。

MIQCP(混合整数二次制約問題)

二次制約問題では変数がすべて連続ですが、これに整数変数が混じるとMIQCP(Mixed Integer Quadratic Constrained Programming/混合整数二次制約問題)になります。

MIQCPの例題

地域のイベントに特産のお菓子A、B、Cの3種類提供することになりました。A、B、Cそれぞれ少なくとも2個は用意し、できるだけ数を多く揃えたいのですが、予算は20,000円しかありません。単価は、AとBは手間がかかるのでAは1個だと1,000円、それより多い注文に対しては1個あたり200円割り増され、同様に、Bは1個だと1,100円、それより多い注文に対しては1個あたり120円割り増されます。Cは個数に関係なく1個あたり1,500円です。予算内でお菓子の総数をできるだけ多くするには、A、B、Cをそれぞれ何個注文すればよいでしょうか?

回答

変数xA、xB、xCをそれぞれA、B、Cの注文個数とすると、この数理最適化問題はつぎのように定式化されます。

目的関数: xA + xB + xC → 最小
制約条件:(800+200xA)xA+(980+120xB)xB+1500xC ≧ 20000
xA, xB, xC ≧ 2、整数

これは、変数が整数変数で制約条件が二次式ですので、MIQCPです。

MILPに二次制約が付加された問題が、MIQCPの典型例です。要員のばらつきを指定値以下に抑えるという制約も加わったスケジューリング問題は、そのような例です。


数理最適化技術の導入をご検討されている方へ

知識と経験豊富な弊社コンサルタントがお客様の抱える問題を解決します!

  • 製品入門トレーニング
PAGE TOP
Menu