講演の 目的 産業や学術の幅広い分野における多くの現実問題が整数計画問題として定式化できます. 近年年では分枝限定法に様々なアイデアを盛り込んだ 高性能な整数計画ソルバーがいくつか公開されています. 最適化の専 門家でない利利 用者にとって現実問題を整数計画問題に定式化することは決して容易易な作業で

組合せ最適化⼊入⾨門

線形計画から整数計画まで

⼤大阪⼤大学  ⼤大学院情報科学研究科 科学技術振興機構 梅⾕谷 　俊治 2013年年3⽉月12⽇日 ⾔言語処理理学会第19回年年次⼤大会(NLP2013)

講演の⽬目的

•  産業や学術の幅広い分野における多くの現実問題が整数計画問題と して定式化できます． •  近年年では分枝限定法に様々なアイデアを盛り込んだ⾼高性能な整数計 画ソルバーがいくつか公開されています． •  最適化の専⾨門家でない利利⽤用者にとって現実問題を整数計画問題に定 式化することは決して容易易な作業ではありません． •  多くの利利⽤用者が現実問題を整数計画問題に定式化できるようになる ことを⽬目指して，線形計画法と整数計画法の基本から始めて，定式 化のテクニック，整数計画ソルバーの利利⽤用法までを解説します．

利利⽤用法と定式化が中⼼心で解法や原理理にはほとんど触れません

講演の概要

1.  整数計画ソルバーとその利利⽤用法

2.  線形計画問題の定式化と解法

3.  整数計画問題の定式化と解法

最適化⼿手法による問題解決アプローチ

•  最適化は意思決定・問題解決のための⼀一つの⼿手段． •  最適化問題に定式化  ＋  最適解の計算  ＋  最適解の分析・検証 現実問題 最適化問題 最適解 モデリング アルゴリズムの_{開発と適⽤用} 検証・分析 最適化問題 制約条件を満たす解の中で⽬目的関数を最⼩小（最⼤大）にする解を求める問題

minimize

f (x)

subject to x

_{2 F}

最適化問題に定式化する

⽣生産計画問題 あるシャトーでは3種類のブドウ，カルベネ，メルロー，セミヨンを原 料料として，3種類のワイン，⾚赤ワイン，⽩白ワイン，ロゼワインを製造し ている．収益が最⼤大となる各ワインの1⽇日当たりの製造量量を求めよ． 種類 ⾚赤ワイン ⽩白ワイン ロゼワイン 最⼤大供給量量 カルベネ 2 0 0 4(t/⽇日) メルロー 1 0 2 8(t/⽇日) セミヨン 0 3 1 6(t/⽇日) 収益 3 4 2 (百万円/⽇日)

最適化問題に定式化する

•  3つの変数x₁,x₂,x₃を導⼊入する． x₁:  ⾚赤ワインの製造量量(t/⽇日) x₂:  ⽩白ワインの製造量量(t/⽇日) x₃:  ロゼワインの製造量量(t/⽇日) →  収益を最⼤大化 →  カルベネの使⽤用量量は4t/⽇日以内 →  メルローの使⽤用量量は8t/⽇日以内 →  セミヨンの使⽤用量量は6t/⽇日以内 →  各ワインの製造量量は⾮非負

maximize

3x

₁

+ 4x

₂

+ 2x

₃

subject to 2x

₁

_{ 4,}

x

₁

+ 2x

₃

_{ 8,}

3x

₂

+ x

₃

_{ 6,}

x

₁

, x

₂

, x

₃

0.

線形計画問題と整数計画問題

•  線形計画問題(Linear  Program;  LP)

–  線形制約の下で線形関数を最⼩小化（最⼤大化）

•  整数計画問題(Integer  Program;  IP)

–  広義：変数に整数条件の付いた最適化問題 –  狭義：線形計画問題＋変数の整数条件 連続変数と整数変数が混 在する問題は，混合整数 計画問題(Mixed  Integer   Program;  MIP) ⾮非線形計画問題(Non-‐‑‒ Linear  Program;  NLP) は⾃自然⾔言語処理理(NLP)と 混同しそう？ LPの実⾏行行可能領領域 IPの実⾏行行可能領領域 MIPの実⾏行行可能領領域

min

n

X

j=1

c

_j

x

_j

s.t.

n

X

j=1

a

ij

x

j

b

i

, i = 1, ... , m,

x

_j

0, j = 1, ... , n.

x

₁

x

₂ 8

線形計画法と整数計画法

•  線形計画問題(LP)は⾼高速に解ける！

–  単体法(simplex  method)，内点法(interior  point  method) –  普通のPCと公開されている（商⽤用・⾮非商⽤用）ソルバーで100 万変数程度度の⼤大規模な問題でも⼯工夫なしに解ける． •  整数計画問題(IP)は⾮非常に⼿手強い！ –  NP困難(NP-‐‑‒hard)と呼ばれるクラスに属する計算困難な組合 せ最適化問題の⼀一つ． –  産業や学術の幅広い分野の現実問題を定式化できる． –  近年年のソルバーは性能が⾶飛躍的に向上． 今野浩，役に⽴立立つ１次式，⽇日本評論論社，2005． 1982:特別な問題を除けば，200〜～300変数の問題を解くのがやっとだった...この分野の研究者は  　 　 　肩⾝身の狭い思いをしていたのである． 2003:CPLEXを使うと，われわれの⽅方法よりも10倍速く解けるという...0-‐‑‒1変数が2000個もある  　 　 　問題でも，数⼗十秒で解けてしまうのである．

計算困難な問題に対するアプローチ

•  厳密解法と近似解法 –  厳密解法：最悪の場合に指数時間かかっても最適解を求める． –  近似解法：現実的な計算時間で良良い実⾏行行可能解を求める． •  汎⽤用解法と専⽤用解法 –  汎⽤用解法：整数計画問題や制約充⾜足問題などに定式化して汎 ⽤用ソルバーを適⽤用する． –  専⽤用解法：問題特有の性質を利利⽤用した専⽤用ソルバーを適⽤用も しくは開発する． a b c d e 整数計画問題 分枝限定法 現実世界の問題 a b c d e 問題  a アルゴリズム  a 現実世界の問題 問題  b 問題  e アルゴリズム  b アルゴリズム  e 汎⽤用解法アプローチ _{専⽤用解法アプローチ}

現実問題に対するアプローチ

•  既存の汎⽤用ソルバーを利利⽤用 –  現実問題が既知の最適化問題と完全に⼀一致することは稀． –  専⽤用ソルバーが利利⽤用可能な状態で公開されていることは稀． –  (混合)整数計画問題に定式化して厳密解法に基づく汎⽤用ソル バーを適⽤用する． –  実⽤用的に解ける問題の規模は限定的． •  ⾃自分で専⽤用ソルバーを開発 –  (混合)整数計画ソルバーでは解けない⼤大規模・複雑な問題． –  問題構造を上⼿手く利利⽤用すれば効率率率的なソルバーが開発可能． –  ⼗十分な知識識・技術と開発期間が必要． 問題の分割や定式化の⼯工夫などで対応できる場合も多い 梅⾕谷の本業はこちらですが，早くて安 い問題解決が必要な場合は，既存の汎 ⽤用ソルバーを使います． 汎⽤用ソルバーはアカデミックのみフリー な場合が多いので企業の⽅方は残念念なこと になるかも知れません．

整数計画ソルバーの現状

•  商⽤用ソルバー

FICO  Xpress  Optimization  (FICO  Corporation),  Gurobi  Optimizer   (Gurobi  Optimization),  IBM  ILOG  CPLEX  (IBM),  LINDO  (LINDO   Systems),  NUOPT  (数理理システム),  SOPT  (Saitech,  Inc.)など．

•  ⾮非商⽤用ソルバー

ABACUS,  BCP,  BonsaiG,  CBC,  GLPK,  lp_̲solve,  MINTO,  SYMPHONY,   SCIPなど． •  商⽤用・⾮非商⽤用ソルバー性能の現状 –  線形計画問題：商⽤用  ≧  ⾮非商⽤用 –  整数計画問題：商⽤用  ≫  ≫  ⾮非商⽤用  　（⾮非線形な整数計画問題：実⽤用的なソルバーは皆無に近い） 整数計画を含めた最適化ソルバー全般は，H.  D.  Mittelmannの Decision  Tree  for  Optimization  Softwareが詳しい．

(http://plato.asu.edu/guide.html)

整数計画問題を解こうと思うな ら商⽤用ソルバーを使うべき

整数計画ソルバーの現状(続き)

•  宮代隆平，ここまで解ける整数計画―近年年の発展―  (2008)によると •  整数計画問題を解くソルバーの進歩は著しく，「15年年間で100万倍 ⾼高速化した」といわれる．この100万倍の内訳は，ハードウェアの ⾼高速化で1000倍，アルゴリズムの⾼高速化で1000倍である．この数 字は数年年前に⾔言われていたものであり，現在では「20年年間で1000万 倍(=3000倍×3000倍)」と⾔言っても過⾔言ではない． •  どのぐらいの規模の問題を解けるのだろうか？⼀一概に⾔言うことはで きないが，個⼈人的には以下のような感覚を持っている． –  変数が1000個未満：何も考えずにソルバーで解かせる –  変数が5000個程度度：おそらくが解ける –  変数が10000個程度度：最適性の証明が難しいこともある –  変数が50000個程度度：問題が簡単なら解ける 整数計画問題の難しさは必ずしも⼊入⼒力力サイズに⽐比例例しないので，変数が少なくても解けない難問に出会

利利⽤用例例(1)：電気⾃自動⾞車車の充放電計画

•  電気⾃自動⾞車車に充放電させて蓄電池の代替として利利⽤用する． •  電気⾃自動⾞車車を適切切なタイミングで充放電させることで，ピーク時 間帯での配電系統からの受電量量の平準化と低減を実現する． •  電気⾃自動⾞車車は放電時には直流流電源，充電時には負荷となり，出庫 時には電⼒力力ネットワークから離離脱する． 配電系統 AC 負荷 AC/DC コンバータ インバータDC/AC 太陽光発電 交流流系統 EV1 DC 負荷 EV2 AC/DC コンバータ 直流流系統

利利⽤用例例(1)：電気⾃自動⾞車車の充放電計画

•  電⼒力力ネットワークを時間軸⽅方向に拡張  →時空間ネットワーク •  各枝のフロー量量を決定する(混合)整数計画問題として定式化する． •  線形計画緩和問題と簡易易な整数丸めにより精度度良良い近似解を⾼高速 に計算する． 配電系統 AC負荷 EV1 DC負荷 EV2 太陽光発電 交流流系統 コンバータ インバータ 時刻 AC DC 直流流系統 交流流系統 直流流系統 交流流系統 直流流系統

利利⽤用例例(1)：電気⾃自動⾞車車の充放電計画

•  中規模ビル(床⾯面積11822m2)に40台の電気⾃自動⾞車車を想定する． •  充放電によりピーク時間帯での受電量量を平準化・低減する．   •  2段階法により充電要求量量や出庫時刻の変動に対してロバストな 充放電計画を計算する． 0   100   200   300   400   500   600   0:00   4:00   8:00   12:00   16:00   20:00   0:00   4:00   8:00   12:00   受電量 (kW ) EV無し 放電のみ 充放電 5000   5500   6000   6500   7000   7500   8000   8500   9000   9500   10000   EV無し 放電のみ 充放電 総受電量 (kW h) ピーク時間帯での 総受電量 ピーク時間帯以外での 総受電量 EV充電による増加量量 低減

利利⽤用例例(2)：機械翻訳のフレーズ対応

•  ⼤大量量の対訳⽂文から確率率率モデルに基づく翻訳規則を学習する． •  連続する単語列列(フレーズ)を最⼩小単位として翻訳する． •  確率率率が最⼤大となる⼊入⼒力力⽂文のフレーズ区切切りと翻訳前後の訳語関係  (フレーズ対応)  を求める． 原言語文 f : 目的言語文 e : this is a sentence . これ は 文 です 。 a it is sentence . 。 一つの それ は 文 0.34 0.52 0.69 0.81 フレーズ対 翻訳確率 フレーズテーブル 最適フレーズ対応 this is a sentence . これ は 文 です 。 フレーズアライナ (phrase aligner) 対訳文からフレーズ対応を得るシステム

利利⽤用例例(2)：機械翻訳のフレーズ対応

•  塗りつぶした矩形の縦横に重複が起きないよう全単語を被覆する． •  フレーズ対応問題を整数計画問題として定式化する． フレーズ対kの翻訳スコア(定数) フレーズ対kが被覆する原⾔言語⽂文の単語(定数) フレーズ対kが被覆する⽬目的⾔言語⽂文の単語(定数) フレーズ対kを使⽤用する→x_k=1，使⽤用しない→x_k=0  (変数)

t

k

:

F :

E :

x

_k

:

max

X

k_2K

t

k

x

k

s.t.

Fx = 1,

Ex = 1,

x

k

2 {0, 1}, k 2 K .

整数計画ソルバーの利利⽤用法

•  GUIを利利⽤用する．

•  CUIを利利⽤用する  →LP形式，MPS形式，モデリング⾔言語:  AIMMS,  

AMPL,  GAMS,  LINGO,  MPL,  MathProg,  ZIMPLなど．

•  API(Application  Programming  Interface)を利利⽤用する  →C,  C++,  

Java,  Matlab,  Pythonなど．

max 3x

₁

+ 4x

₂

+ 2x

₃

s.t.

2x

₁

_{ 4,}

x

₁

+ 2x

₃

_{ 8,}

3x

₂

+ x

₃

_{ 6,}

x

₁

, x

₂

, x

₃

0.

minimize

3 x1 + 4 x2 + 2 x3

subject to

c1: 2 x1 <= 4

c2: x1 + 2 x3 <= 8

c3: 3 x2 + x3 <= 6

end

線形計画問題をLP形式で記述した例例

整数計画ソルバーの利利⽤用法

•  ⾮非商⽤用ソルバーでは最も⾼高速なものの⼀一つ（いくつかの商⽤用ソル バーよりも⾼高速）であるSCIPを例例に⼿手順を⽰示す． •  SCIPのウェブサイト(http://scip.zib.de/scip.shtml)から実⾏行行フ ァイルをダウンロード（アカデミックユーザのみ無償利利⽤用可能） •  解きたい整数計画(線形計画)問題をLP形式で記述したテキストフ ァイルを⽤用意する（hogehoge.lpとする） •  SCIPを起動するとコマンド⼊入⼒力力待ちとなるので，hogehoge.lpの 読み込み，最適化開始，解の出⼒力力のコマンドを順に⼊入⼒力力する．

SCIP> read hogehoge.lp SCIP> optimize

SCIP> write solution hogehoge.sol

←⼊入⼒力力データの読み込み ←最適化の開始

←解の出⼒力力 SCIPの使⽤用法の詳しい使⽤用⽅方法については以下の⽂文献が詳しい．

宮代隆平，整数計画ソルバー⼊入⾨門，オペレーションズ・リサーチ，57(2012)，183-‐‑‒189． T.Berthold,  A.M.Gleixner,  S.Heinz,  T.Koch,  品野勇治,  SCIP  Optimization  Suite  を利利⽤用した   混合整数  (線形/⾮非線形)  計画問題の解法,  ZIB-‐‑‒Report  12-‐‑‒24,  2012,  http://opus4.kobv.de/ opus4-‐‑‒zib/frontdoor/index/index/docId/1559/

整数計画ソルバーの利利⽤用法

•  LP形式は⽂文法が平易易で可読性が⾼高く，多くのソルバーが対応してい るが，配列列のように変数をまとめて取り扱う機能はない． •  ⼤大規模な問題例例を扱いたい場合には， –  LP形式のテキストファイルを出⼒力力するプログラムを作成  　  →  プログラミングの経験があるならお⼿手軽 –  モデリング⾔言語を利利⽤用  　  →  直感的だがモデリング⾔言語を覚えるのが⼿手間 –  APIを利利⽤用して直接問題を⽣生成  　  →  ⾊色々と⼿手間がかかる⼀一⽅方でできることをもまた多い for(i = 0; i < 10; i++){ printf("+ x%d ",i); } printf("<= 3\n");

線形計画問題

•  ⽬目的関数が線形関数，制約式も線形式の最適化問題． •  全ての線形計画問題は標準形に変形できる． ⽬目的関数は最⼤大化，最⼩小化 のどちらでもOK 制約式の不不等号は ≧，≦，＝のいずれ でもOK 変数の⾮非負制約はあっ てもなくてもOK 不不等式標準形：⽬目的関数は最⼤大 化，不不等号は≦，変数は⾮非負

min 3x

1

+ 4x

2

2x

3

s.t.

2x

1

= 4,

x

1

2x

3

 8,

3x

2

+ x

3

6,

x

1

, x

2

0.

max

3x

₁

+ 4x

₂

+ 2x

₃0

2x

₃00

s.t.

2x

₁

_{ 4,}

2x

₁

_{ 4,}

x

₁

2x

₃0

+ 2x

₃00

_{ 8,}

3x

₂

x

₃0

+ x

₃00

_{ 6,}

x

₁

, x

₂

, x

₃0

, x

₃0

0.

例例：栄養問題

•  ある飲料料メーカーでは野菜ジュースを製造しており，n種類の野菜 を混合してm種類の栄養素を充⾜足している．どの野菜をどれだけ 購⼊入するのが最も経済的だろうか？ 野菜jに含まれる栄養素iの量量(定数) 栄養素iの必要量量(定数) 野菜jの単位量量当たりの値段(定数) 野菜jの購⼊入量量を変数x_jとすると

a

ij

:

b

i

:

c

j

:

min

n

X

j=1

c

j

x

j

s.t.

n

X

j=1

a

_ij

x

_j

b

_i

, i = ... , m,

x

j

0, j = 1, ... , n.

例例：輸送問題

1 2 m 1 2 n c11 c12 c1n •  mヵ所の⼯工場からnヵ所の⼩小売店に製品を輸送する際に，各⼯工場 の⽣生産量量を超えない範囲で各⼩小売店が需要を満たすように輸送し たい．輸送費⽤用が最⼩小となる計画は？ ⼯工場iの⽣生産量量(定数) ⼩小売店jの需要量量(定数) ⼯工場iから⼩小売店jへの単位量量当たりの輸送費⽤用(定数) ⼯工場iから⼩小売店jへの輸送量量(変数)

a

i

:

b

j

:

c

_ij

:

x

_ij

:

min m X i=1 n X j=1 cijxij s.t. n X j=1 xij  ai, i = 1, ... , m, m X i=1 xij bj, j = 1, ... , n,

線形計画問題に定式化する

•  線形計画法の⽣生みの親であるGeorge  Dantzigは，1948年年にウィス コンシン⼤大で講演した際にH.Hotellingに「でも我々はみんな世界が ⾮非線形だと知っている」と厳しく批評されたそうですが... •  線形計画問題で記述できる事はそんなに少ないでしょうか？ •  現実問題を厳密に正確に定式化することは可能でしょうか？ •  どんなに厳密な正確な定式化でも最適解が求まらない問題に定式化 してしまってはダメではないでしょうか？ •  ⾮非線形関数じゃないとダメですか？整数変数じゃないとダメですか？ •  定式化は融通が利利くものだと思えば線形計画問題でできることは⾊色 々あります． •  ⼀一⾒見見，⾮非線形計画問題に⾒見見える問題でも厳密さを失うことなく線形 計画問題に変換できる場合もあります．

ちなみに，この時John  von  Neumannが「線形計画の公理理を満たす応⽤用があれば使えばよいし，そうで なければ使わなければよい」と弁護したそうです（Neumannは双対定理理の証明に深く関わっていた）

min m X i=1 zi s.t. yi (axi + b) zi, i = 1, ... , n, yi (axi + b)  zi, i = 1, ... , n, zi 0, i = 1, ... , n.

区分線形関数の最⼩小化

•  観測で得られたn個の⼊入出⼒力力データ(x_i,y_i)(i=1,...,n)から⼊入出⼒力力の 関係を⼀一次式  y=ax+b  で近似する（係数a,bの値を変数として求 めるいわゆる回帰問題） 誤差 (x_i,  y_i)

x

y

誤差を表す 変数z_iを⽤用いる L₁ノルムの最⼩小化

|y

i

(ax

i

+ b)

| min

n

X

i=1

|y

i

(ax

i

+ b)

|

min t

s.t.

a

i

x + b

i

 t, i = 1, ... , m.

区分線形関数の最⼩小化（続き）

•  ⾮非線形関数を区分関数で近似する． •  区分関数が凸であれば等価な線形計画問題に変換できる．  　（凸でない場合は混合整数計画問題に変換できる） 凸な区分線形関数はmax 関数で書き換えられる y=f(x) x

min f (x) = max

i=1,...,m

(a

i

x + b

i

)

min z s.t. n X j=1 c_j1xj  z, n X j=1 c_j2xj  z, · · · n X j=1 c_jkx_{j  z,} n X j=1 aijxj bi, i = 1, ... , m, min n X j=1 c_j1xj, n X j=1 c_j2xj, ... , n X j=1 c_jkxj, s.t. n X j=1 aijxj bi, i = 1, ... , m, x_j 0, j = 1, ... , n.

最⼤大値の最⼩小化（最⼩小値の最⼤大化）

•  複数の⽬目的関数を同時に最⼩小化したい場合には，これらの⽬目的関 数の最⼤大値を最⼩小化する⽅方法が考えられる． •  逆に，資源をなるべく公平に配分したい場合には，配分量量の最⼩小 値を最⼤大化する⽅方法が考えられる． k個の⽬目的関数を同時に最⼩小化 最⼤大値を表す 変数zを⽤用いる

⽐比率率率の最⼩小化

•  ⽐比率率率を最⼩小化する⾮非線形な関数を線形計画問題に変換できる場合 もある． min n X j=1 cjxj n X j=1 djxj s.t. n X j=1 aijxj bi, i = 1, ... , m, n X j=1 djxj > 0, xj 0, j = 1, ... , n. t = _n 1 X j=1 djxj , yj = txj min n X j=1 cjyj s.t. n X j=1 a_ijy_j b_it 0, i = 1, ... , m, n X j=1 djyj = 1, yj 0, j = 1, ... , n, t 0.

max x

₁

+ 2x

₂

s.t.

x

₁

+ x

₂

_{ 6,}

x

₁

+ 3x

₂

_{ 12,}

2x

₁

+ x

₂

_{ 10,}

x

₁

0,

x

₂

0.

線形計画問題を解く

•  制約式をm本，変数をn個とする． •  実⾏行行可能領領域は(m+n)個の超平⾯面に囲まれている  →  凸多⾯面体 •  n個の超平⾯面が交差する頂点のいずれかに最適解がある！

x

₂

 

最適解 最⼤大化

x

₁   ① ② ③ ④ ⑤ →  ① →  ② →  ③ →  ④ →  ⑤ 調べる頂点の数が 個となって効率率率的ではない

✓

m + n

n

◆

=

(m + n)!

m!n!

単体法

•  凸多⾯面体のある頂点（実⾏行行可能解）から出発して，⽬目的関数値が改 善する隣隣接頂点への移動を繰り返す． •  各頂点ではn個の超平⾯面が交差しているので，n本の線形式からな る連⽴立立⽅方程式を解けば頂点に対応する実⾏行行解が得られる．  　（実際の単体法では連⽴立立⽅方程式を解き直さなくても済むよう⼯工夫されている）

x

₂

 

x

₁  

x

1  

x

₂

 

f  (x

₁

,x

₂

)

内点法

•  単体法：実⾏行行可能領領域の境界を通って最適解にたどり着く． –  実⽤用的には⾼高速だが，理理論論的には最悪で指数時間かかる例例も． •  内点法：実⾏行行可能領領域の内部を通って最適解にたどり着く． –  理理論論的に最悪でも多項式時間で抑えられて，実⽤用上も⾼高速． •  ⼤大規模な問題を１回だけ解くなら内点法の⽅方が⾼高速． •  ⼊入⼒力力データを変更更して解き直す際に，変更更前の最適解を出発点と して変更更後の最適解を求める再最適化では単体法の⽅方が⾼高速． 初期解 最適解 近道 遠回り 初期解 最適解

組合せ最適化問題

•  探索索空間が離離散的であるもしくは離離散的なものに減らせる最適化 問題，解が集合，順序，割り当て，グラフ，論論理理，整数などの離離 散構造で記述される場合が多い． •  多くの組合せ最適化問題は整数計画問題として定式化できる． 組合せ最適化問題の例例 •  最短路路問題（カーナビのルート検索索など） •  ネットワーク設計問題（ライフライン，交通網，通信網，⽯石油・ ガス等のパイプライン網など） •  配送計画問題（宅宅配便便，店舗・⼯工場への製品配送，ゴミ収集など） •  施設配置問題（⼯工場，店舗，公共施設など） •  スケジューリング問題（⼯工場の操業計画，乗務員・看護師等の勤 務表作成，スポーツの対戦表・⽇日程表の作成，時間割の作成など） 現実問題の多くが組合せ最適化問題として定式化できる！

整数計画問題

•  線形計画問題＋変数の整数条件．

•  ⼀一部の変数のみが整数条件を持つ場合は混合整数計画問題(Mixed  

Integer  Program;  MIP)と呼ばれる．

•  全ての変数が{0,1}の2値条件を持つ場合は0-‐‑‒1整数計画問題(0-‐‑‒1  

Integer  Program;  0-‐‑‒1IP)と呼ばれる．

LPの実⾏行行可能領領域 IPの実⾏行行可能領領域 MIPの実⾏行行可能領領域 1

x

2

x

Jは整数変数の添字集合

min

n

X

j=1

c

j

x

j

s.t.

n

X

j=1

a

_ij

x

_j

b

_i

, i = 1, ... , m,

x

j

0, j = 1, ... , n,

x

j

: integer, j

2 J.

例例：ナップサック問題

•  最⼤大でc(>0)の重さまで荷物を詰め込める袋が1つとn個の荷物が 与えられる．重さの合計がcを超えない範囲で荷物の価値の合計 が最⼤大となる詰込み⽅方は？ 袋に詰め込める重さ合計の上限(定数) 荷物iの重さ(定数) 荷物iの価値(定数) 荷物iを袋に詰め込む→x_i=1,  つめ込まない→x_i=0(変数)

c :

w

_i

:

p

_i

:

x

_i

:

max

n

X

i=1

p

_i

x

_i

s.t.

n

X

i=1

w

_i

x

_i

_{ c,}

x

i

2 {0, 1}, i = 1, ... , n.

例例：割当て問題

•  m⼈人の学⽣生をn個のクラスに割り当てる．ただし，各クラスの受 講者数には上下限が与えられている．学⽣生の満⾜足度度を最⼤大にする クラスの編成は？ クラスjの受講者数の上限(定数) クラスjの受講者数の下限(定数) 学⽣生iのクラスjに対する満⾜足度度(定数) 学⽣生iをクラスjに割り当てる  →x_ij=1,  割り当てない  →x_ij=0(変数)

u

_j

:

l

_j

:

p

_ij

:

x

_ij

:

max m X i=1 n X j=1 p_ijx_ij s.t. lj  m X i=1 xij  uj, j = 1, ... , n, n X j=1 xij = 1, i = 1, ... , m, xij 2 {0, 1}, i = 1, ... , m, j = 1, ... , n. 38

例例：最短路路問題

•  n個の点からなるグラフG=(V,E)と隣隣接する点間の距離離が与えら れる．指定された始点sから終点tまでの距離離が最短となるルートは？ A B C E F D 4km 5km 9km 10km 3km 3km 4km 3km 4km 点(i,j)間の距離離(定数) 枝(i,j)を通る→x_ij=1,  通らない→x_ij=0(変数)

d

_ij

:

x

_ij

:

min X (i,j)_2E d_ijx_ij s.t. X j:(s,j)_2E xsj = 1, X j:(j,i)_2E xji X j:(i,j)_2E xij = 0, i 2 V \ {s, t}, X j:(j,t)_2E x_jt = 1, xij 2 {0, 1}, (i, j) 2 E .

整数計画問題に定式化する

•  離離散的な状態の切切り替えを記述するために離離散変数を導⼊入する． –  集合，順序，割り当て，グラフ，論論理理などを記述する． –  ⼈人数や⾞車車両の台数など扱うデータが整数値だからと整数変数 を⽤用いる定式化が良良いとは限らない． –  変数の値が⽐比較的⼤大きな値を取る場合は連続変数として扱う と良良い（線形計画問題の⽅方がはるかに解き易易い） •  整数変数より{0,1}の2値変数で事⾜足りる場合が多い． –  数を表す変数→整数，状態を表す変数→2値変数 –  例例：4つの状態を切切り替えたい場合は？

x

_{2 {0, 1, 2, 3}}

⇢

x

₁

, x

₂

, x

₃

, x

₄

_{2 {0, 1},}

x

1

+ x

2

+ x

3

+ x

4

= 1.

論論理理関係を表す

•  ナップサック問題を例例としていくつか追加条件とその表現を考える． 1.  袋に詰め込める荷物は⾼高々k個 2.  袋に詰め込まない荷物は⾼高々k個 3.  荷物iまたは荷物jを詰め込む 4.  荷物iを詰め込むなら荷物jを詰め込む

x

₁

+ x

₂

+

_{· · · + x}

_n

_{ k}

(1

x

1

) + (1

x

2

) +

· · · + (1

x

n

)

 k

x

i

+ x

j

1

x

i

 x

j

論論理理関係を表す(続き)

•  ナップサック問題を例例としていくつか追加条件とその表現を考える． ５．荷物1,...,nのうち詰め込める荷物は0または2 (1,1,0)   (1,0,1)   (0,0,0)   (0,1,1)   制約を満たす解のみを含む凸包を記述する もしくは と表現することもできる．

x

1

+ x

2

+

· · · + x

n

= 2y , y

2 {0, 1}

+x

₁

+ x

₂

+

_{· · · + x}

_n

_{ 2,}

x

₁

+ x

₂

+

_{· · · + x}

_n

0,

+x

₁

x

₂

+

_{· · · + x}

_n

0,

· · ·

+x

1

+ x

2

+

· · ·

x

n

0.

x

₁

x

₂

x

₃

min f (x) = c

1

+ c

2

y

s.t.

x

_{ Cy,}

y

_{2 {0, 1}.}

0

_{ x  C .}

固定費⽤用の有無を表す

•  製品量量によって⽣生じる変動費⽤用と段取り替えによって⽣生じる固定 費⽤用の両⽅方を扱うには？ •  単位費⽤用c₁で⽣生産される製品の⽣生産量量をxとする． •  わずかでも製品が⽣生産されると初期費⽤用c₂が発⽣生する． •  総費⽤用f(x)を線形式で表すには？ 傾きc₁ c_{2 x>0ならば1}

0

C x

f(x)

_{f (x) =}

⇢

0

x = 0

c

1

x + c

2

0 < x

 C

例例：ビンパッキング問題

•  ⼗十分な数の最⼤大でc(>0)の重さまで荷物を詰め込める箱とn個の 荷物が与えられる．全ての荷物を詰め込むのに必要な箱の数が最 ⼩小となる荷物の詰込み⽅方は？ 箱に詰め込める重さ合計の上限(定数) 荷物iの重さ(定数) 箱jを使う→y_j=1,  箱jを使わない→y_j=0(変数) 荷物iを箱jに詰め込む→x_ij=1,  詰め込まない→x_ij=0(変数) ちなみに，ビン(bin)は⼤大箱の意味であって瓶ではありません．

c :

w

i

:

y

j

:

x

ij

:

min n X j=1 yj s.t. n X i=1 wixij  cyj, j = 1, ... , n, n X j=1 xij = 1, i = 1, ... , n, xij 2 {0, 1}, i = 1, ... , n, j = 1, ... , n, yj 2 {0, 1}, j = 1, ... , n. 44

8 > > > > > > > > < > > > > > > > > : n X j=1 a1jxj  b1 + M(1 y1), n X j=1 a_2jx_{j  b2} + M(1 y₂), y₁ + y₂ = 1, y1, y2 2 {0, 1}.

離離接した制約式

•  k個の制約式の少なくとも⼀一⽅方の制約式が成⽴立立する場合に，これら は離離接している制約式と呼ばれる． •  順序付け，⾮非凸な区分線形関数などが表現できる． and  ではなく  or 離離接した制約式を0-‐‑‒1変数を⽤用いて記述 制約式の実質的な 有無を決定する 0-‐‑‒1変数 ⼗十分⼤大きな定数 x₁ x₂ n X j=1 a_1jx_{j  b1} n X j=1 a2jxj  b2 n X j=1 a1jxj  b1 _ n X j=1 a2jxj  b2

例例：1機械スケジューリング問題

•  n個の仕事とこれらの仕事を処理理する1台の機械が与えられる．全 ての仕事の納期遅れの総和を最⼩小化する仕事の処理理順は？ •  全ての仕事は時刻0で開始可能．仕事は⼀一度度始めたら中断はでき ない．1台の機械で同時に2つ以上の仕事はできない． 仕事iの処理理時間(定数) 仕事iの納期時刻(定数) 仕事iの開始時刻(変数) 仕事iが仕事jに先⾏行行する→x_ij=1,  先⾏行行しない→x_ij=1(変数) min n X i=1 max_{si + pi di, 0} s.t. si + pi  sj + M(1 xij), i = 1, ... , n, j 6= i, xij + xji = 1, i = 1, ... , n, j 6= i, xij 2 {0, 1}, i = 1, ... , n, j 6= i, si 0, i = 1, ... , n.

p

i

:

d

_i

:

s

_i

:

x

_ij

:

時刻 i j s_{i di} s_i+p_i p_i s_i+p_i-‐‑‒d_i s_j p_j 線形式でない 46

例例：1機械スケジューリング問題

•  n個の仕事とこれらの仕事を処理理する1台の機械が与えられる．全 ての仕事の納期遅れの総和を最⼩小化する仕事の処理理順は？ •  全ての仕事は時刻0で開始可能．仕事は⼀一度度始めたら中断はでき ない．1台の機械で同時に2つ以上の仕事はできない． 仕事iの処理理時間(定数) 仕事iの納期時刻(定数) 仕事iの開始・終了了時刻(変数) 仕事iが仕事jに先⾏行行する→x_ij=1,  先⾏行行しない→x_ij=1(変数) min n X i=1 ti s.t. si + pi  sj + M(1 xij), i = 1, ... , n, j 6= i, xij + xji = 1, i = 1, ... , n, j 6= i, si + pi di  ti, i = 1, ... , n, xij 2 {0, 1}, i = 1, ... , n, j 6= i, s , t 0, i = 1, ... , n. 時刻 i j s_{i di} s_i+p_i p_i s+p-‐‑‒d s_j p_j

p

i

:

d

_i

:

s

_i

, t

_i

:

x

_ij

:

⾮非凸な区分線形関数を表す

•  ⾮非凸な⾮非線形関数を区分線形関数で近似する． •  区分線形関数上の点(x,y)はいずれかの線分上にある． •  (x₁,y₁),(x₂,y₂)で結ばれる線分上にある場合は以下の通り表現できる． •  これを⼀一般化すると(x,y)は… (x₁,y₁) (x2,y2) (x3,y3) (x₄,y₄) ⾼高々2つの隣隣り合うt_iが正(⾮非ゼロ) (x, y ) = t1(x1, y1) + t2(x2, y2), t1 + t2 = 1, t1, t2 0 (x, y ) = t₁(x₁, y₁) + t₂(x₂, y₂) + t₃(x₃, y₃) + t₄(x₄, y₄), t1 + t2 + t3 + t4 = 1, t1, t2, t3, t4 0, t1  z1, t2  z1 + z2, t3  z2 + z3, t4  z3, z1 + z2 + z3 = 1, z1, z2, z3 2 {0, 1}.

整数変数から2値変数への変換

•   　 　 　      は2値変数で表現できる？ •  x_jが限られた離離散値を取る場合は？，例例えばx_j={3,4,9}だと？ 解の対称性と冗⻑⾧長性を排除 するための制約式 0 _{ xj  9, xj} : integer ⇢ xj = y1j + 2y2j + 22y3j + 23y4j, y1j, y2j, y3j, y4j 2 {0, 1}. 8 < : x_j = y_1j + y_2j + y_3j + _{· · · + y9j}, y1j y2j · · · y9j, y1j, ... , y9j 2 {0, 1}. 8 < : x_j = y_1j + 2y_2j + 3y_3j + _{· · · + 9y9j}, y1j + · · · + y9j  1, y1j, ... , y9j 2 {0, 1}. 8 < : xj = 3y1 + 4y2 + 9y3, y1 + y2 + y3 = 1, y1, y2, y3 2 {0, 1}.

制約充⾜足問題

•  制約充⾜足問題は⽬目的関数を持たないけど？ →適当な⽬目的関数を作る •  ⽬目的関数の係数c_jが全て1(または0)，最⼩小値最⼤大化(最⼤大値最⼩小化) だと，整数計画ソルバーの探索索効率率率が著しく悪くなる(理理由は後述) →⽬目的関数の係数c_jを適当な整数乱数に設定する．

0-‐‑‒1整数2次計画問題

•  xTQxで表される2次関数でも2値変数でかつ⾏行行列列Q=[q_ij]が疎なら， 線形関数に変換できる． 1

Q

2 j n 1 2 n i q_ij i q_ij j 無向グラフ に変換する y_ij=x_i  x_j  とおけば と書ける •  さらに，y_ij=x_i  x_j  で(x_i,  x_j,  y_ij)が取る値の組み合わせは，(0,0,0), (1,0,0),(0,1,0),(1,1,1)で，      は以下の通り 書き換えられるので，xT_{Qx  +  c}T_{x  も線形関数に変換できる．} ちなみに,  y=x1  x2  ...  xk  だと min n X i=1 X j_6=i qijyij yij = xixj, xi, xj 2 {0, 1} 8 < : xi + xj yij  1, x_i y_ij 0, x_j y_ij 0, xi, xj 2 {0, 1}. 8 < : Pk i=1xi y  1, xi y 0, i = 1, ... , k, x _{2 {0, 1}, ı = 1, ... , k.}

整数計画問題を解く

•  計算困難な最適化問題では最適値が簡単に求まらない． •  最適値の上界と下界を求めて最適値の取り得る範囲を限定する． •  緩和問題：原問題の⼀一部の制約条件を緩めた問題 •  線形計画緩和問題：整数変数の整数条件を外す→線形計画問題 最 ⼩小 化 最適値 上界 下界 実行不可能 実行可能 整数計画問題 線形計画緩和問題 MIPの実⾏行行可能領領域⊆LPの実⾏行行可能領領域 ⽬目的関数値 x₁ x₂ x₂ x₁

分枝限定法

•  最適化問題に対する汎⽤用的な厳密解法． •  分枝操作：実⾏行行可能領領域を分割して部分問題を⽣生成する．  　（緩和解が実数値を取る変数x_tを選んで，      を追加した問題      と，      を追加した問題に分割する） •  限定操作：緩和問題から得られる下界値を⽤用いて最適解が得られる ⾒見見込みのない部分問題を省省く．  　（分枝前の下界値  z  ≦  分枝後の下界値  min{z₁,  z₂}） LPの最適解 LPの最適解 x x x₂ x₂ x_{t  b¯xtc} xt d¯xte

切切除平⾯面法

•  全ての実⾏行行可能な整数解を含む凸包は凸多⾯面体→線形計画問題 •  前もって凸包の不不等式表現を知ることは困難だしその数も膨⼤大． •  線形計画問題の最適解xが整数解でないとき，xを切切除する制約式 を追加する． •  LP最適解をカットして，整数解をカットしてはいけない． •  切切除平⾯面を追加するに従って最適解に近づく． 最⼩小化 LP最適解 切切除平⾯面(カット) LP最適解 LP最適解 ＝整数解！ 最近の整数計画ソルバーは分枝限定法と切切除平⾯面法を組み合わせた 分枝切切除平⾯面法を⽤用いている

良良い定式化とは？

•  制約式が少ない⽅方が⾒見見栄えも良良くて計算時間も短い？ –  線形計画緩和問題を解くのに必要な計算時間は減る  ←影響⼩小 –  線形計画緩和問題から得られる下界値は悪くなる  ←影響⼤大 →制約式は⼀一⾒見見無駄に⾒見見えてもできるだけ沢⼭山加えた⽅方が良良い 整数計画問題の解となる整数格⼦子点のみ を含む凸多⾯面体は⼀一意ではない •  どんな⽬目的関数でも⼤大丈夫？ –  限定操作が働かなくなると探索索効率率率が著しく落落ちる． –  係数c_jが全て1(または0)，最⼩小値最⼤大化(最⼤大値最⼩小化)では， 同点の実⾏行行可能解が多数⽣生じて限定操作が働かない． →線形和でかつ係数c_jがバラバラな値を取る⽅方が良良い

最適解が求まらないときは？

•  整数計画ソルバーの基本戦略略は分枝限定法 •  最適解が求まらない理理由  →限定操作が⼗十分に働いていない 解けない問題の特徴 •  線形計画問題の下界値が悪い →  制約式を追加する，⼀一部の変数の値を固定して問題を縮⼩小する •  部分問題が実⾏行行不不可能になり易易い →  ⼀一部の制約条件を緩和してペナルティ項として⽬目的関数に移す •  対称性が⾼高い，最適解が異異常に多い →  ⽬目的関数を変形する，対称性を除去する制約式を追加する •  問題の規模が⼤大きい →  ⼦子問題を分割する •  数値的に不不安定，線形計画緩和問題が解きにくい →  ⼊入⼒力力データの数値の桁数を減らす，数値の⼤大きさを揃える

まとめ

1.  整数計画ソルバーとその利利⽤用法 –  最適化問題の紹介 –  整数計画ソルバーの現状，利利⽤用例例，利利⽤用法 2.  線形計画問題の定式化と解法 –  凸な区分線形関数，最⼤大値の最⼩小化，⽐比率率率の最⼩小化 –  単体法，内点法 3.  整数計画問題の定式化と解法 –  論論理理関係，固定費⽤用，離離接した制約式，⾮非凸な区分線形関数， 整数変数→2値変数，0-‐‑‒1整数2次計画問題 –  分⼦子限定法，切切除平⾯面法 –  良良い定式化とは？最適解が求まらないときは？ 線形関数と整数変数だけでも多くの現実問題を定式化できます！ ぜひご活⽤用下さい！

参考⽂文献(1)

•  久保幹雄，J.P.ペドロソ，村松正和，A.レイス，あたらしい数理理最適化―Python⾔言語 とGurobiで解く―，近代科学社，2012． •  久野誉⼈人，繁野⿇麻⾐衣⼦子，後藤順哉，数理理最適化，オーム社，2012． •  藤澤克樹，後藤順哉，安井雄⼀一郎郎，Excelで学ぶOR，オーム社，2011． •  福嶋雅夫，新版 　数理理計画⼊入⾨門，朝倉書店，2011． •  加藤直樹，数理理計画法，コロナ社，2008． •  ⼑刀根薫，数理理計画，朝倉書店，2007． •  森雅夫，松井知⼰己，オペレーションズ・リサーチ，朝倉書店，2004． •  久保幹雄，⽥田村明久，松井知⼰己(編)，応⽤用数理理計画ハンドブック，朝倉書店，2002． •  久保幹雄，組合せ最適化とアルゴリズム，共⽴立立出版，2000． •  宮代隆平，整数計画ソルバー⼊入⾨門，オペレーションズ・リサーチ，57(2012)， 183-‐‑‒189． •  藤江哲也，整数計画法による定式化⼊入⾨門，オペレーションズ・リサーチ，57(2012)， 190-‐‑‒197． •  宮代隆平，松井知⼰己，ここまで解ける整数計画，システム/制御/情報，50(2006)， 363-‐‑‒368． •  宮代隆平，ここまで解ける整数計画―近年年の発展―，第20回RAMPシンポジウム報 告集，1-‐‑‒21，2008．

参考⽂文献(2)

•  今野浩，役に⽴立立つ⼀一次式：整数計画法「気まぐれ王⼥女女の50年年」，⽇日本評論論社，2005． •  L.A.Wolsey,  Integer  Programming,  Wiley,  1998.

•  H.P.Williams,  Model  Building  in  Mathematical  Programming  (4th  _{edition),Wiley,}    

1999.(前⽥田英次郎郎  監訳，⼩小林林英三  訳，数理理計画モデルの作成，産業図書，1995)

•  V.Chvatal,  Linear  Programming,  W.H.Freeman  and  Company,  1983. •  H.D.  Mittelmann,  Decision  Tree  for  Optimization  Software,  

http://plato.asu.edu/guide.html  

•  A.Atamturk,  M.W.P.Savelsbergh,  Integer  Programming  Software  Systems,  

Annals  of  Operations  Research,  140  (2005),  67-‐‑‒124.

•  J.T.Linderoth,  T,K.Ralphs,  Noncommercial  Software  for  Mixed-‐‑‒Integer  Linear   Programming,  Integer  Programming  –  Theory  and  Practice,  J.K.  Karlof  (ed.),   Taylor  and  Francis,  2006.

•  T.Berthold,  A.M.Gleixner,  S.Heinz,  T.Koch,  品野勇治,  SCIP  Optimization  Suite   を利利⽤用した  混合整数  (線形/⾮非線形)  計画問題の解法,  ZIB-‐‑‒Report  12-‐‑‒24,  2012,

http://opus4.kobv.de/opus4-‐‑‒zib/frontdoor/index/index/docId/1559/

•  SCIP  (Solving  Constraint  Integer  Programs),  Zuse  Institute  Berlin  (ZIB),

参考⽂文献(3)

•  T.Koch  et  al.,  MIPLIB2010,  Mathematical  Programming  Computation,  3  (2011),   103-‐‑‒163.

•  T.Achterberg,  T.Koch,  A.Martin,  MIPLIB2003,  Operations  Research  Letters,  34   (2006),  361-‐‑‒372.

•  Y.Fukushima,  S.Umetani,  H.Morita,  S.Iida  and  M.Kobayashi:  Robust  energy   management  system  with  electric  vehicles,  Proceedings  of  International   Symposium  on  Scheduling  2011  (ISS2011),  117-‐‑‒122,  July  2-‐‑‒4,  2011.

•  越川  満,  内⼭山  将夫,  梅⾕谷  俊治,  松井  知⼰己,  ⼭山本  幹雄:  統計的機械翻訳におけるフレ

ーズ対応最適化を利利⽤用したN-‐‑‒best翻訳候補のリランキング,  情報処理理学会論論⽂文誌,  51