二千十三年五月 あたらしい数理最適化 出版記念セミナー 主催 近代科学社 オクトーバースカイ 共催 構造計画研究所 http://www.logopt.com/book/gurobi.htm

まずは自己紹介 久保幹雄 東京海洋大学 サプライ・チェイン最適化工学 フェイスブック： http://www.facebook.com/mikio.kubo.737 ホームページ： http://www.logopt.com/mikiokubo/

アジェンダ 13:00-13:50 「あたらしい数理最適化」概説 16:00-16:50 数理最適化の応用例 と実験的解析

前半 「あたらしい数理最適化」概説 この本のどこが新しいのか 数理最適化の基本の基本 定式化のコツ

あたらしい 数理最適化って 本が出たらしいけど 何があたらしいの？

あたらしいこと 0 数理最適化 (Mathematical Optimization) Since 2010

Programming) Up to 2010 its name 昔は．．． 数理計画 (Mathematical Programming) Up to 2010 its name was "Mathematical Programming Society みんなの投票で改名！（最適化に1票！）

Dantzig (1947) Programming in linear structure Koopmans (1948) Linear Programming Dorfman (1949) Mathematical Programming

あたらしいこと　１ 他のテキストとは違って 解法の中身より 使いこなすためのテク

ピボット選択 有限収束の証明 改訂単体法 などは一切なし

双対性 分枝限定法 列生成 分枝カット法 そして二次錘最適化まで！ きちんと解説

あたらしいこと　２ Python言語ですぐ解ける 原案：PythonとGurobi でぐんぐん解ける！（小山社長）

Pythonとは When he began implementing Python, Guido van Rossum was also reading the published scripts from “Monty Python’s Flying Circus”, a BBC comedy series from the 1970s. Van Rossum thought he needed a name that was short, unique, and slightly mysterious, so he decided to call the language Python.

MITの講義の 表紙 http://xkcd.com/353/

import すれば何でもできる！ import gurobipy #数理最適化 import scop #制約最適化 import optseq #スケジューリング import antigravity (空を飛ぶ?)

あたらしいこと　３ 色々なソルバーを紹介 数理最適化 Gurobi 制約最適化 SOCP スケジューリング OptSeq

Gurobiとは Zonghao Gu, Edward Rothberg，Robert Bixby

Gurobiとは Zonghao Gu Edward Rothberg Robert Bixby

なぜGurobi ? （他にもたくさんあるじゃない） 混合整数 線形，凸二次，二次錘最適化 において（たぶん）最速 （MIPソルバーの限界を見極めたい！） これでダメなら，他でもダメ

なぜGurobi ? マルチコア対応 長時間まわしても壊れない（安定性抜群） Pythonからの呼び出しが“容易” （他のソルバーは，呼び出し“可”レベル） 会議中でも実装可能！

なぜGurobi ? その３ プロ仕様の出力（とある実際問題のログ） Optimize a model with 4794 rows, 4777 columns and 13572 nonzeros Presolve removed 4483 rows and 2877 columns Presolve time: 0.05s Presolved: 311 rows, 1900 columns, 4467 nonzeros Variable types: 25 continuous, 1875 integer (1863 binary) Found heuristic solution: objective 1807.9530303 Found heuristic solution: objective 1226.0603030 Root relaxation: objective 6.890000e+02, 351 iterations, 0.01 seconds

SCOPとは 野々部先生，茨木先生作 Tabu Searchに基づく制約最適化ソルバー Gurobiでダメな問題でも大丈夫 （でも最適性の保証はなし！）

SCOP & OptSeq 野々部先生 茨木先生

時間割作成 看護婦スケジューリングの 国際コンペで好成績！ 後で,野々部先生が詳しくお話 してくれると思います

Shift Master （構造計画研究所様）でも採用！

OptSeqとは 野々部先生，茨木先生作 Tabu Searchに基づく 汎用」スケジューリング最適化ソルバー Gurobiでダメな問題でも大丈夫 モデル化の工夫で実務問題の多くをカバー

SCOP, OptSeqともに Pythonインターフェイスあり！ （しかもPythonのソース開示！） 上手なメタヒューリスティクス => 汎用なのに高性能！

あたらしいこと　4 色々な実用的＋代表的な 問題例で比較 後半の講演でお話しします．

あたらしいこと 5 二次錘最適化 (second order cone optimization ) あたらしいこと　5 二次錘最適化 (second order cone optimization ) 後で,村松先生が詳しくお話してくれると思います

数理最適化とは？ お金を儲けたいんだよね－ でも，色々としがらみがあってね－．

数理最適化とは？ maximize 　お金 subject to しがらみ 目的関数 制約条件

数理最適化とは？ maximize f(x) subject to g(x)≧0 x ∈ X

線形最適化とは？ max. cx s.t. Ax≦b x は実数

解法 目的関数 内点法 単体法

使い分け 基本はデフォルト（双対単体法）で 単体法が遅いときには，内点法！

どこまで解ける？ -- GUROBI-5.5.0 内点法 秒 rail4284 4284行 1092610列 12372358非ゼロ L1_d10_40 80477行 420366列 2062656非ゼロ 非ゼロ要素数  http://plato.asu.edu/bench.html (Mittelmannによる実験)

整数最適化とは？ max. cx s.t. Ax≦b x は整数

目的関数 解法：分枝限定法＝基本は線形最適化

目的関数 上界 整数解 実行可能解 下界 分枝操作

コツ　１ 整数最適化に対しては， 良い定式化をしよう！ 上界と下界のギャップが 小さい定式化

そのためには 大きな数Mを用いた 実数変数≦M・整数変数 はなるべく避ける！

コツ　2 解が対称性をもつ場合 には注意！

対称性とは？ グラフ彩色問題 「点」に色を塗る！枝の両端点は別色．

対称性とは？ グラフ彩色問題の解（の１つ） 「点」に色を塗る！枝の両端点は別色．

対称性とは？ 赤，青，黄を交換しても同じ解！

分枝限定法の基本 X1,黄色 = 0.5 緩和問題 点１は黄色 に塗る 点１は黄色に 塗らない X1,黄色 = 1 X1,黄色 = 0

分枝しても限定できない！ 点１は黄色に塗らない

分枝しても限定できない！ 点１は青色に塗らない

やっと限定操作 点１は黄色に塗らない 点１は赤色に塗らない

解決法：対称性を除去 無記名の「色」に優先順序を付加 例： 赤使用 ≧ 青使用 ≧ 黄使用 でも，あまり効かない（実験は後ほど）

対称性の例２ ビンパッキング問題 色々なアイテムを「同じ大きさ」の箱（ビン）に詰める！ 箱の数を最小に！（＝すきまを最小に！）

対称性の例２ 最適解（の１つ） 箱の番号を変えても同じ解！

X1,箱１ = 1 X1,箱１ = 0 分枝限定法を使うと．．． X1,箱１ = 0.5 緩和問題 アイテム１は 箱１に入れる アイテム１は 箱１に入れない X1,箱１ = 1 X1,箱１ = 0

分枝しても限定できない！ アイテム１ 箱１ アイテム１は箱２に入れない アイテム１ アイテム１ アイテム１は箱１に入れない

解決法：パターンの列挙 ・・・・ アイテムをちょうど１つ含むように （たくさんの）パターンから選択

コツ　3 （パターン）変数の数が 非常に多い => 列生成法

min. cx s.t. Ax=b 列生成法 c A 行列 Aが超横長 必要な「列」だけ生成！

コツ　4 制約の数が非常に 多い=> 切除平面法 もしくは分枝カット法

min. cx s.t. Ax=b 切除平面法 A b 行列 Aが超縦長 必要な「行」だけ生成！ 切除平面（カット）

分枝カット法 A b 分枝する度にカットを追加！

例： 巡回セールスマン問題 すべての点をちょうど1回通過する最短巡回路

巡回セールスマン問題 の最適解 すべての点をちょうど1回通過する最短巡回路

定式化 点に接続する枝の本数＝２ for all 点 （次数制約）

定式化 点に接続する枝の本数＝２ for all 点 （次数制約）

足りない制約を付加 枝の本数＜点の数 for all 点の部分集合 （部分巡回路除去制約） この中の枝の本数 2本以下！

コツ　5 特殊順序集合 Special Ordered Setを 使いこなそう！

A>0 or B>0 or C>0 => 変数 A,B,C はSOSと宣言 SOS Type 1 変数のうちの高々１つが正 特殊な分枝操作で高速化 A>0 or B>0 or C>0 => 変数 A,B,C はSOSと宣言

SOS Type 2 連続する高々2つの変数が正 [0 0 0 0.5 0.4 0 0] => OK [0.5 0 0 0 0 0.4 0] => NG [0 0 1 0 0 0 0] => OK 区分的線形関数の宣言で使用

線分の表現        

区分的線形関数の表現                 はSOS Type 2

コツ　6 最大値を最小化する 目的関数には注意！

線形最適化での 常套手段 min. max. f(x,y) y x

線形最適化での 常套手段 min. max. f(x,y) y x =zと置いて

線形最適化での 常套手段 min. max. f(x,y) y x =zと置いて min. z s.t. f(x,y)≦z

（混合）整数最適化では， これをやると終わらない！ 問題に応じた工夫（二分探索） もしくは他の手法を用いる！

謝辞 Acknowledgement

主催 近代科学社　　小山社長，大塚様 オクトーバースカイ　 　　　　　　　　和多田社長，中村様

共催　＆　会場提供 構造計画研究所　斉藤 様 池水 様

SCOP & OptSeq 野々部先生 茨木先生

Experimental Analysis All Python Codes Experimental Analysis ジョアン（ジョン）・ペドロ・ペドロソ先生 「ジョア」ではないらしい

村松先生＠電通大 Another Co-Author Abdur Rais@Porto

樋口（ペドロソ）真美さん 綺麗な表紙をありがとう！

ご来場の皆様 懇親会もあります！