Gurobi Optimizer：ソルバー
Gurobi Optimizerを使用することで、数理最適化問題を解くことができます。数理最適化問題は、解の候補の中から最も評価の良いものを見つける問題です。数理最適化問題が数式で表現されている時、評価を表す関数を目的関数と言い、解が候補となる条件を制約条件式と言います。
LP（線形計画問題） | QP（二次計画問題） | QCP（二次制約問題） | MILP（混合整数線形計画問題） | MIQP（混合整数二次計画問題） | MIQCP（混合整数二次制約問題） | Non-convex MIQCP（混合整数非凸二次制約）
LP（線形計画問題）
目的関数や制約条件がすべて一次式で表現されている場合の数理最適化問題を、LP（Linear Programming / 線形計画問題）と言います。
1g 10円の原料Aと1g 20円の原料Bを混ぜて、製品を100g以上作らなければならない。最も安価にすませるには、どのように混ぜるとよいでしょうか?
［解答］
原料Aを\(x\)g、Bを\(y\)gとした場合、原料費を最も安価したいので目的関数は\(10x+20y\)となり、この目的関数を最小化する解を求めます。この場合の制約条件は、\(x+y≧100、x,y≧0\)
解:\(x=100、y=0\)
例題では目的関数と制約条件を表す式がすべて変数との一次式なので、この問題は線形計画問題です。この例は簡単な例なのですぐに解を求められますが、一般の線形計画問題は、多くの変数および制約条件式からなり複雑です。また、一見すると非線形計画問題と思われる問題の中にも、線形計画問題として定式化できるものがあります。
例えば、絶対値が目的関数に入っている場合は線形化できますし、最大値と最小値の差が目的関数に入っている場合も線形化できます。
本来は、非線形計画問題であっても近似的に線形計画問題と見なせる場合や、比較のために線形計画問題として近似する等の場合もあります。
また、別の数理最適化問題の緩和問題として利用されることもあり、線形計画の適用例は、広範囲に渡ると言ってもいいでしょう。現在では、シンプレックス法の改良や内点法の発展により、これらの問題に対して、 最適解を高速に求めることができます。最適解であることは理論的に保証され、また双対変数を利用した感度情報も得られます。
ビジネスシーンでの線形計画問題例
- 輸送問題
変数は輸送量、目的関数は輸送コスト(最小化)、制約条件は需要の充足、センター最大保管料等 - 配合問題
変数は原料使用量、目的関数は原料コスト(最小化)、制約条件は成分の上限/下限 - 資金計画問題
変数は投資金額、目的関数は利益、制約条件は資金量
QP（二次計画問題）
目的関数が二次式で制約条件が一次式の問題を、QP（Quadratic Programming / 二次計画問題）と言います。例えば、輸送費が輸送量に一定の係数を掛けて求めていて、その係数が輸送量の一次式である場合は二次計画問題になります。また、概念自体が二次のものもあります。例えば、三角形の土地に最も大きな正方形の家を建てたい時、どれだけの大きさの家が建てられるかは二次計画問題になります。面積が辺の長さの二乗になるからです。
パラメータの最小二乗推定問題は、目的関数がすべて二次式ですのでQPになります。また、実験データのフィッティング問題、線形動的システムの同定問題等があります。金融におけるポートフォリオ最適化に対する平均・分散モデルもそうです。
そこでは、期待利益がある値以上という制約の下で、リスク分散（二次式）を最小にします。その他、製造業では負荷の平準化の概念がよく用いられますが、負荷を分散ととらえるとQPになります。
世の中にQPは、数多く存在します。面積や輸送における距離と重量の積および分散等は、自然に二次式になるからです。 すべてのQPが効率よく解けるわけではありませんが、目的関数が凸二次式の場合は、効率よく解くことができます。関数が凸というのは、関数上の任意の異なる2点をとった時、その2点を結ぶ線分が関数より上にあるという性質を持つことです。目的関数を行列形で
と書いた時、二次の項を形成する行列\(F\)が半正定値の場合、関数は凸になります。
\(y=2x^2\)はその特別なケースで、二次の係数2が正なので凸です。よく知られているように、このような二次関数は閉区間では最小解を持ち、極小解は持ちません。
QCP（二次制約問題）
制約条件が二次式の場合の数理最適化問題を、QCP（Quadratic Constrained Programming / 二次制約問題）と言います。目的関数は、一次式または二次式です。
QPのところでも説明しましたが、線形計画問題における一次式制約の係数が定数でなく変数の一次式で表される場合は、QCPになります。また、QPを最小化すべき目的関数に上限変数を導入し、新たな目的関数はその上限変数の最小化となり、元の目的関数が上限変数以下という制約条件のある問題に定式化し直すとQCPになります。
金融におけるポートフォリオ最適化に対する平均・分散モデルで、リスク分散を指定値以下に抑えるという制約条件で期待利益率を最大にするという問題や、客先から距離がある値以下となる場所に拠点を選ぶという問題は、QCPになります。
二次制約条件が形成する実行可能領域が凸集合の場合には、効率的に解くことができます。
凸集合というのは、その中の任意の異なる2点をとった時、その2点を結ぶ線分が必ずその中に入っているという性質を持つ集合です。凸集合の共通集合は凸集合ですので、凸集合になる二次制約がいくつあっても同じです。
\(x^TFx+g^Tx+h≤0\)
と書けますが、このとき二次の項を形成する行列\(F\)が半正定値行列の場合は、領域が凸集合になります。直観的には、楕円（楕円体）をイメージしてください。
それ以外に、二次制約条件式が二次錐制約になる場合も、領域は凸集合になります。二次錐制約というのは
という形で書ける二次制約条件式です。\(n\)は、変数の次元です。
円錐をイメージすると、直感的に分かりやすくなります。前述の凸二次制約式も、二次錐制約に変換することができます。\(y≧|x|\) は二次元の、\(z^2≧x^2+y^2\) および \(yz≧x^2\) は三次元の二次錐制約の代表例です。
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 / 混合整数線形計画問題）は線形計画問題であって、変数の中に整数変数が混じっているものということになります。
仕事が1、2、3の3つあり、これらを工程1、2で処理しなければならない。仕事1の工程1、2での処理時間は10分、3分、仕事2は4分、6分、仕事3は5分、8分である。どの仕事も工程1が終了してから工程2で処理する。すべての仕事を最も早く終了させるにはどのようなスケジュールにすればいいでしょうか？
［解答］
仕事番号と工程番号をペアにして“活動”と呼ぶことにします。この問題に対しては(1,1)、(1,2)、(2,1)、(2,2)、(3,1)、(3,2)の6つの活動ができ、それぞれ活動1、2、…、6と呼ぶことにします。さらに、全仕事の終了に対応して活動7を作ります。そして、1分刻みの時間区間を30個用意します。
変数として
\(x(j,t)\)：活動\(j\)が時刻\(t\)で開始するとき1、そうでないとき0
という0-1変数を用意します。7つの活動の中には満たされなければならない先行順序関係があり、(1,2)、(3,4)、(5,6)、(2,7)、(4,7)、(6,7)の6個です。
また、活動1、3、5は工程1を、活動2、4、6は工程2を使用すると定義しておきます。このとき本問題は、次のような最適化モデルとして表せます。
制約条件： （どの活動もどこかの時刻で開始する）
\((i,j)\)は、先行関係の活動ペア
（工程で処理時間帯が重ならない）
\(p(j)\)は活動\(j\)の処理時間、\(r(j,k)\)は活動\(j\)が工程\(k\)のとき1、それ以外は0の値を持ちます。最適解は、工程1では時刻0から仕事3、2、1の順に、工程2では時刻5から仕事3、2、1の順に待ち時間無しで行うことになります。全仕事は、22分で完了します。
ここでは0-1変数を用いましたが、時間メッシュを用いず、各活動の開始時刻や終了時刻を連続変数として用いることもできます。その場合は完全なMILPになり、制約条件も増えます。
ビジネスシーンでの混合整数線形計画問題例
実は数理最適化問題の中で応用上多く現れるにも拘わらず、主として計算時間がかかるために解くのが難しいとされている組合せ最適化問題の多くが、MILPでモデル化できます。組合せ最適化問題では制約条件が論理的な条件で表されることが多いですが、それらは、条件の成否に対応して1と0の値をとる論理変数を導入することにより表現できます。また、スケジューリング問題等で時間の概念を扱う場合でも、開始時刻に対応する離散変数を導入したり、計画対象の時間範囲を細かい間隔に離散化するなどの方法によって、MILPとしてモデル化することができます。
このように多くの問題が、MILPとして表現できます。
- 施設配置計画問題
統廃合問題では、施設を使用するかどうかの0-1変数、新設計画では、候補施設の中で選ぶかどうかの0-1変数が導入される。 - 輸配送問題
輸送品の個数、トラックの台数などが整数変数 - スケジューリング問題
開始時刻、ジョブの先行、マシン上でジョブが重ならないなどの定式化に0-1変数が導入される。 - カッティングストック問題
各カッティングパターンを選ぶ個数が整数変数
また一見すると非線形計画問題と思われる問題の中にも、MILPとして定式化できるものがあります。それは、目的関数や制約条件に非線形関数が入っている場合です。非線形関数と言っても、定義されている範囲内で有界であればその範囲をいくつかに分割し、各部分区間内では一次関数で近似することができます。この区分線形近似は、MILPで定式化できます。
MIPは分枝限定法の分枝操作の工夫、効果的なカットの導入、行列操作の工夫、並列化などにより高速に解けるようになってきています。仮に計算時間がかかる難しい問題を計算途中で打ち切っても、ギャップの値（上界と下界の差）から最適解にどの程度近いかを知ることもできます。
MIQP（混合整数二次計画問題）
二次計画問題の変数の中に整数変数が混じっている時、その二次計画問題はMIQP（Mixed Integer Quadratic Programming / 混合整数二次計画問題）と言います。
2000個の製品をA、B、Cの3工場で生産したい。各工場の製造能力は、それぞれ1000、500、800個である。各工場の稼働率をできるだけ均等にするには、何個ずつ生産するとよいでしょうか？
［解答］
\(x_A、x_B、x_C\)を各工場での生産量とすると、稼働率はそれぞれ、\(\frac{x_A}{1000}、\frac{x_B}{500}、\frac{x_C}{800}\)となる。稼働率の均等を平均からの2乗誤差の最小化と捉えると、最適化モデルは次のようになります。
（稼働率の平均）
最適解は、\(x_A=869、x_B=435、x_C=696\)です。
二次計画問題の多くは、変数に使用個数制限や論理条件に対応する0-1変数が導入されることによりMIQPになります。
例えば、パラメータの推定問題に最小二乗法を適用する場合、その問題は二次計画問題になりますが、パラメータの数は多すぎると過剰推定を引き起こすことはよく知られており、パラメータの数はある基準を満たすように決定するのが良いとされています。
赤池情報量基準（AIC）は、その一つです。そこでパラメータを選択するかしないかの0-1変数を導入し、パラメータの数も評価に加えると、その問題はMIQPになります。それ以外にも、金融におけるポートフォリオ最適化問題の平均・分散モデルにおける銘柄選択数に制限をつける場合の問題があります。最適制御あるいはモデル予測制御において、装置の起動/停止に対応する0-1変数を導入して最適制御問題を解くという問題は、論理条件に対応する0-1変数が導入されたMIQPの例です。
MIQCP（混合整数二次制約問題）
二次制約問題では変数がすべて連続ですが、これに整数変数が混じるとMIQCP（Mixed Integer Quadratic Constrained Programming / 混合整数二次制約問題）になります。
ある仕事をさせるのにAグループの人達とBグループの人達に働いてもらい、所定の作業量の仕事を完了させてもらいたい。ただし、作業可能な総人数には制限があり、労務費にも制限がある。1人あたり作業量は、Aグループの人は1.0、Bグループの人は0.8である。1人の時間あたり労務費は、Aグループの人は3000円、Bグループの人は2000円である。総作業量40の仕事を8人以下、労務費11万円以下で達成したい。作業時間を最小にするには、人数をどのように割り当てればよいでしょうか？
［解答］
\(x_A、x_B\)をグループA、Bの人数（整数変数）、\(y\)を作業時間（連続変数）とすると、最適化モデルは次のようになります。
\(x_A+x_B≤8\) （人数制約）
\(3000x_A y+2000x_B y≤110000\) （労務費制約）
最適解は、\(x_A=3、x_B=5、y=5.7143\)です。すなわち、Aグループ3人、Bグループ5人とし、最小時間は、5.7143時間です。
モデルの中の総作業量制約と労務費制約が二次制約、とくに非凸双線形制約です。
MILPに二次制約が付加された問題が、MIQCPの典型例です。要員のばらつきを指定値以下に抑えるという制約も加わったスケジューリング問題は、そのような例です。
Non-convex MIQCP（混合整数非凸二次制約）
週40時間を割り振って製品Aを少なくとも200と製品Bを少なくとも100、合わせて400以上作りたい。製品Aは装置1台1時間あたり4、製品Bは装置1台1時間あたり2作ることができる。製品Aの装置は1台あたりのコストが固定費10万円、1時間あたり1万円である。製品Bの装置は1台あたりのコストが固定費5万円、1時間あたり1万円である。製品AとBをそれぞれ何台の装置で何時間稼働させると、コスト最小で所望の量を作ることができるでしょうか？
［解答］
\(x_A、x_B\)を製品A、Bの装置の数（整数変数）、\(y_A、y_B\)を製品A,Bの作業時間（連続変数）、\(z\)をコストの上界とすると、最適化モデルは次のようになります。
\(4x_A y_A≥200\) （製品Aの生産量制約）
\(2x_B y_B≥100\) （製品Bの生産量制約）
\(y_A+y_B=40\) （時間制約）
\(10000x_A+10000x_A y_A+50000x_B+10000x_B y_B≤z\) （コスト制約）
最適解は、\(x_A=3、x_B=4、y_A=27.5、y_B=12.5、z=1825000\)です。すなわち、製品Aは装置3台を27.5時間、製品Bは装置4台を12.5時間稼働させると、コストが最小の1,825,000円で済むことになります。なおこのとき、製品A,Bの生産量はそれぞれ330と100です。
変数として整数変数と連続変数を含み、4番目以外の制約は二次でありかつ凸ではないので、この問題はNon-Convex MIQCPです。
