【2014年スケジューリングシンポジウム資料】

数理計画法システム最新動向－次世代数理計画法システムの紹介－

2014年9月30日
宮崎 知明（MSI株式会社）miyazaki@msi-jp.com

はじめに・ SCMの浸透により、大規模最適化問題の解決がますます重要になっているが、数理計画法システムの限界で苦労しているのが、現状（MIP、NLP、CP等）。
・ 従来の方法（MIP：分岐限定法）では解けない大規模
組合せ 最適化問題（８００万以上のパターンの組合せから最適な組み合わせを求める）を実用的に解くことができるようなソフトが出現。
・ 従来の数理計画法システムの良い点と最新のIT技術を活用した近傍探索による全く新しい統合数理計画法シス
テム（LocalSolver) が実現された。
・ どんな現実問題をも直接モデル化できる時代（非線形制
約、論理制約、非線形目的関数）になった。
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

2

目次
１．大規模最適化のあゆみ
２．数理最適化ソフト動向
３．SCM事例（従来手法）
４．LocalSolver概要
５．LocalSolverの事例

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

3

１．大規模最適化の歩み

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

4大規模最適化問題の例※過去の事例•毎週数百万トンの鉄鋼生産をスケジューリング
新日鉄、POSCO、USINOR他•毎日500万個以上の荷物を配達
UPS, FEDEX他•毎日170,000人のクルーをスケジューリング
AmericanAirline, UnitedAirline, DELTA, BA他•石油化学での原価配賦計算(数万行)•日本全国のタンクローリの配車日程計画•日本全国のキャリアカーの配車日程計画
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

5

SCM市場動向
ソリューションの進化
Focus
BI & BigData

バリューチェーン

E-Business

サプライチェーン
SCM
全社
ERP
部門
現場
2014/10/8

BPR（ビジネスプロセスリエンジニアリング）

Quality（品質）
80s
90s

2000+

MSI株式会社 Copyright ⓒ 2014.

Time
6

SCMソリューションの進化
SCM：Supply Chain Management（企業内全体最適化）「市場ﾆｰｽﾞを起点とした原料調達から生産,物流,販売までの連鎖を一つのｼｽﾃﾑとして管理すること」

SCPM: Supply Chain Process Management(実行時最適化）「実行系SCMとして、走りながら、予測できない変動をﾘｱﾙﾀｲﾑに感知し、オペレーション指示を意思決定すること」
・市場変動、環境変化、気候変動、ｵﾍﾟﾚｰｼｮﾝﾐｽ、例外処理等の不足事態

CMM: Collaborative Manufacturing Management（企業間最適化）「企業間、組織間に亘って同期的に情報を共有し、業務 （ﾋﾞｼﾞﾈｽﾌﾟﾛｾｽ）を全社的な観点から最適に遂行すること」

RPM: Real-time Performance Management（収益最大化）「リアルタイムで企業活動を把握、評価、予測し、収益の観点から企業にとって最適な意思決定を行うこと」

S&OP: Sales and Operation Management（経営と直結したマネージメント）
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

7

SCMソリューションの概念
LocalSolver

企業戦略

SCM
（SCP)

プランニング

KPI･利益最大化、新製品投入 etc.

（.収益管理）

S&OP

同期

ＯｐＸ
調整

調達
プロセス

製造プロセ
ス

受注納入
プロセス

ﾌﾟﾗﾝﾆﾝｸﾞ・ｽｹｼﾞｭｰﾘﾝｸﾞ

KPI（.費用管理）

同期

受動的

SCPM
+SCE

オペレーションコントロール

ｽｹｼﾞｭｰﾘﾝｸﾞ･欠品、納期、例外処理 etc.

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

ｱﾄﾞﾊﾞﾝｽﾄﾞKPI

セールス ＆ オペレーション マネジメント

自発的
（能動的）

（.利益管理）8

問題解決型アプローチの実現ヘ
営業部門

販売実績

原料部門

販売計画

本社計画部門

工場生産部門 物流部門

生産計画

中長期計画
（随時）

原料購入
計画

在庫実績

LocalSolver

仕掛実績

月次
販売計画

受注実績

月間日別
出荷予定

装置運転
計画

日次ｵｰﾀﾞｰ

製品生産
ｽｹｼﾞｭｰﾙ

月次計画（数回／月）

日次計画
（毎日）

全社月次
生産計画

配送実績

原料処理
計画

配車、
配送計画

ﾎﾞﾄﾙﾈｯｸと絶対制約に着目した問題解決型計画ｴﾝｼﾞﾝの開発
ライブラリエンジン群：
2014/10/8

統計解析

BME

数理計画

制約論理

ﾙｰﾙﾍﾞｰｽ

MSI株式会社 Copyright ⓒ 2014.

GA

ﾋｭｰﾘｽﾃｨｯｸ
9２．数理最適化ソフト動向

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

11大規模最適化の環境が出来た• コンピュータの進歩（ホストからPCへ）––––

計算能力の飛躍的な向上（CPU高速化）
メモリ上での計算（メモリの低価格化）
大量データの保持（ディスクの大容量化）
大容量情報の即時伝達（ブロードバンド）

大規模な計算が可能• 最適化解法の発展––––

OR手法の高速化(LP, MIP)
ヒューリスティク解法の進歩
新解法の出現
ハイブリッド解法の実用化

現実に即した計画立案が可能• 実行、実現環境の整備
–
–
–
–
–
2014/10/8

データの集積（ERP, ＤＷＨ等）
情報伝達手段の普及（インターネット）
一人一台のＰＣ作業環境
専門のＩＳＶの出現
オープンかつデファクトソフトの出現
MSI株式会社 Copyright ⓒ 2014.

何時でも何処でも誰でも計画立案が可能12ＬＰ計算性能の歴史
1988年から2003年の15年間での性能アップ••

アルゴリズム（マシンに無関係） ： 約2,360倍マシン（ワークステーション→ＰＣ） ： 約800倍

2,360 × 800 = 約 1,900,000 倍•

40万式×１５８万変数の生産計画モデル

29.8日から59秒へ“Operations Research” 2002年1月号より※今や100万式、１０００万変数でも問題なく解ける。
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

12

既存数理計画法ソフトの課題• 線形計画法– シンプレックス法が主流（掃出計算での割算が必要）– 事前解析(presoluve）、途中解析の発展（制約論理の導入等）– 理論的に最適解を保証

・実用規模（1000万式以上）
で最適化計算が可能
・計算誤差累積は永遠の課題• 混合整数計画法

・整数変数が1000以上だと– 分枝限定法が主流
指数関数的に資源が必要（シンプレックス計算が必要）– 事前解析、途中解析の発展（実行可能整数解の発見にヒューリスティク解法の導入）– 理論的には最適解探索を保証• CP、NLP、メタ解法– 問題ごとの解法が必要– 現実をどうモデリングするかが勝負
2014/10/8

・解法の設計が必要
・解法のチューニングが必要

MSI株式会社 Copyright ⓒ 2014.

14

３．SCM事例（従来手法）

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

16

全国規模の低温輸配送における最適化例
過去の事例•実務では、ハブを経由しない輸送を行なっている•低温輸配送においては、品質管理上の要求が厳しい•ハブにおける入出庫作業を避
けたい•車両のドアの開け閉めの回数•幹線便トラック1台分の物量があれば, 集配先-集配先間で直接運んだほうが効率的

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

15輸配送パターンの種類
過去の事例•直送（集約、中継せず）•引取（集約せず）•直納（中継せず）•幹線（ハブ間のみ）

Aエリア
ハブ & スポーク

2014/10/8

Bエリア•日本全国でどう運送効率を高める輸送種類を決めるかが重要•通常, 地域集荷および地域配送とセットになるMSI株式会社 Copyright ⓒ 2014.

16

全国規模の輸配送計画アプローチ
過去の事例•全国を6ブロックに分割•幹線輸送はブロック間•ブロック内は通常の地 域輸送計画•ブロックを跨るオーダごとに輸
配送パターンの候補を作成し、最適化•従来手法と比較し、約２０％の改善※しかし、配送パターン候補生成に限界があった。

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

17

大規模部品調達ルート最適化問題
過去の事例［ネットワークの構造］
ノード：部品サプライヤ、工場、スルーセンター
出荷/納入形態：

・工場・・・部品サプライヤorスルーセンターからの多頻度納入
・スルーセンター・・・部品サプライヤからの多頻度納入+工場or他スルーセンターへの出荷
部品の輸送経路：

・直送ルート・・・工場を出発し、部品サプライヤを巡回して部品を集荷し、工場に戻るまでの経路
・ミルクランルート・・・スルーセンターを出発し、部品サプライヤを巡回して部品を集荷し、スルーセンターに戻るまでの経路
・幹線輸送ルート・・・工場/スルーセンター間または2か所のスルーセンター間を往復する経路
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

18

調達物流最適化の目的
過去の事例
全体の物流コストを最小化するように輸送形態（直送・幹線輸送・ミルクラン）および輸送手段（トラック・列車）を決める →日次計画

生産工場
S

S

S
S

S
S

S

S

T/C

S
T/C

S

S

S

S

S
S

S

S

S

S
S

T/C
S
S

S

サプライヤー
S

T/C

S

S

生産工場

スルーセンタS

2014/10/8

S

MSI株式会社 Copyright ⓒ 2014.

S

19

調達物流の形態と数理最適化手法
過去の事例〔従来の納品方式〕
各部品サプライヤがそれぞれ個別に工場に納品する方式→各部品サプライヤごとに運搬経路問題（Vehicle Routing Problem）を適用することにより解決部品の納入頻度の増加に伴う変化〔新しい納品方式〕
部品の輸送効率アップを目的とした、工場から部品メーカを巡回して部品を集める方式→多段階輸送になっているため、単純な運搬経路問題（Vehicle Routing Problem）の適用では解決不可能
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

20

輸送条件
過去の事例

全部で３０種類の制約条件[制約条件の例]• 輸送の平準化（最低納入頻度、遇数回納入）• 立ち寄り数制約• スルーセンタ中継数制約• 特定ルート固定• ルート交差制約（１サプライヤ１ルート/TC）・・
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

21

大規模組合せ最適化の例
過去の事例

実行可能なルートの候補を作成

その候補の中からコスト最適なルートの組合せを選択

S

S

S
S

S

S
S

TC

S

S
TC

S
S

S

S

S
S

最適化

S

S

S

S
S

S

TC

S

S

2014/10/8

S※しかし、ルート候補
S
生成に限界があった。
S
S

S

S

S

S
S

S

S

S
S
TC

S

S

MSI株式会社 Copyright ⓒ 2014.

S
S

22

－最適化事例における成果ー
過去の事例•ロジスティクスコストが１０％削減
企業合併に伴う拠点再配置による生産コストと物流コストの削減•原料費が２％削減
石油化学での原料調達の業務プロセス改善（月次計画４０日以上を1週間で）•部品調達の物流コストが５％削減
自動車メーカでのサプライヤ – 物流センタ – 工場間

計画業務の見直しと数理最適化技術の導入により最低でも、２～１０％のコスト削減が期待できる
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

23

何故、今、次世代数理計画法システムか？（現状）
大規模最適化の現状
課題レベル
出来ないこと課題
大規模組合せ最適化問題が解けない
時間がかかる

適用の課題

大規模なシステム資源が必要（ＣＰＵ，メモリ等）
モデルチューニングがタイムリーに出来ない

運用の課題

モデルの変更が簡単にできない

数理最適化分野で広く利用されているMIP（混合整数計画法）、
CP(制約論理プログラミング)が持つ上記問題を解決するために大規模最適化システムが必要である。

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

24

何故、次世代数理計画法システムか？ （技術的背景）
従来方式（分岐限定法）では実現不可能な世界
現在適用されている最適化（数理計画法）は、混合整数計画法（MIP)または制約プログラミン
グ（ＣＰ）が多くを占めており、分岐限定法をベースにしている。
分岐限定法は、整数変数を一つ一つ固定して子問題、孫問題と枝わかれさせながら、解空間を探索していくため最適解を見つける過程においては解の組合せが親子関係で決まってしまい、
枝別れをして探索していくため、最適解探索時間が指数関数的に増加する。
また、目的関数は一つしか定義できないため、複数目的がある場合の目的計画法的な最適化モデルの記述ができない。

従来方式では理論的には実現可能だが現実的でない世界
何千規模の0-1意思決定変数を含む現実社会の大規模モデルを解こうとすると長時間走行または長時間走行しても解が発見できないことに遭遇する。
費用対効果を度外視したシステムリソース（ＣＰＵ，メモリなど）を潤沢に投入でも、ソリューショ
ンとしての保証ができないことが発生する。

従来方式の運用面（継続的な高い安全性と信頼性）の課題
従来方式では、モデルとして連立方程式を構築する必要があり、モデルの検証に時間がかかるだけでなく、環境変化に対応したタイムリーなモデルチューニングが困難である。
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

25

何故、次世代数理計画法システムか？（経済的背景）
拡大する適用シーン
数理計画法（最適化技術）は、今まで生産現場での最適な生産計画策定や物流分野などで活用され、多くの成果をもたらしている。しかし、近年のクラウドの進展にともなう大量データ（ビックデータ）の存在や、グローバル化に伴う製造・物流拠点の増加などにより、最適化を検討する際の制約条件や与件が複雑化しており、従来の最適化手法やシステムでは、与件の多さにより計算爆発を起こし最適解が得られず、多くの企業では事業機会を逃している。
・
・
・
・
・

製造（生産計画、裁断計画、ブレンディング）
物流、流通（拠点配置計画、配送計画、倉庫管理）
流通・サービス(要員シフトの最適化)
電力（スマートグリッド、ユニットコミットメント（発電機起動停止計画））
運輸（乗務員スケジューリング、荷役計画、バースアロケーション、機材メンテナンス
計画）
・ 金融（ポートフォリオマネージメント）他多数

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

26

何故、次世代数理計画法システムか？（経済と技術的背景）
新たな適用分野（現場とそこに携わる人間を支援する最適化）
ビックデータ活用を中心としたＩＴ技術の向上がもたらす社会、企業の構造変化的に対応する仕組みが必要となりつつある。
経営は本社機構が中心の統制型管理に現場主体の緻密な制御の組み合わせが（月次計画と日次制御の融合）進みつつあり、この変化に対して現場を支援する仕組みが必要である。
溢れる情報から現場業務能力を低下させることなく、本来の接客サービスなどの業務に専念できる時間を確保できる環境整備とも言える。
• 現場に新鮮で有益な情報を提供するためには複雑で瞬時の判断が求められるが、それを現場で使いこなすため(人間がボトルネックにならない)には、現場のさまざまな意思決定（最適化）の支援が最も重要となる。
• ビックデータ活用技術により最適化モデルの変数に投入するパラメタデータの入手がタイムリーに可能となり、ビックデータ活用をもとにした意思決定が必要である。
• センシング＆アラータ技術が発達し、意思決定の時間短縮が必要（警報音が響く職場環境で右往左往）。
また、属人化の危機（熟練者が退職などで伝承が困難）に対応するため、熟練者の知識を最適化モデルとして管理・運用する仕組みが重要である。
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

27

４．LocalSolver概要

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

30

開発背景（現実問題に対する従来アプローチ）
 既存のソルバーを利用
現実問題が既知の問題と一致することは稀であり、 専用ソルバーが利用可能な状態で公開されていることはほとんどない。
混合整数計画問題に定式化して分枝限定法に基づくソルバーを適用(CPLEX, Gurobi, Xpress-MP, NUOPT, SCIP など)するが、実用的に解ける問題の規模は限定的である。

 自分でソルバーを開発
混合整数計画ソルバーで扱えない大規模・複雑な最適化問題に対して問題構造を上手く利用できれば効率的なソルバーの開発は可能であるが、十分な知識・技術と開発期間が必要となる。

LocalSolverはこの問題克服にチャレンジ
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

29

LocalSolverとは• Bouyguesは、フランスで最も大きい
企業グループの1つ--収入は330億€/年• Innovation 24は、ビジネス分析及び最適化を実現するBouyguesの子会社• LocalSolverは、Innovation 24が開発、提供を始めたハイブリッド型統合数理
計画法システム2014/10/8

MSI株式会社 Copyright ⓒ 2014.

32

LocalSolver開発経緯
・ 仏ブイグ社の最適化部門による2000年からの実績（汎用化を試行2000-2005年）
・ フランスのＯＲチーム（准教授２人及び実践家４人）による
2007年から研究開発プロジェクトで成果（国の支援）
・ MIP（混合整数計画法）では解けない大規模組合せ 最適化問題（８００万以上の0-1整数変数）を実用的に解く
・ メタヒューリスティク解法（局所探索解法）をベースにシンプレックス法をも取り込んだ全く新しい汎用解法を実現
・ 非線形制約、非線形目的関数まで拡張した問題を解く：
Mixed-variable non-convex programming
・ 最新のIT技術、数理最適化技術を活用（関数型プログラミング言語、問題解析機能、並列処理等）
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

31

LocalSolver（特長）
実行時間（満足解を得るまで）

問題対応型
メタヒューリスティクス

問題のサイズ（意思決定変数の数）

LocalSolverは両方の良いところを実現
2014/10/8

MSI株式会社 Copyright ⓒ 2013.

32

離散凸解析からから見たLocalSolver
問題の条件

解法

特徴

問題規模

システム

離散（ディスク Ｂ＆Ｂ法＋シン 子問題を生成リート）&凸型 プレックス法
して解く（コンベックス）

整数変数の
数に制約あ
り

汎用ソフト
ＭＩＰ
ＣＰ

離散（ディスクリート）

メタヒューリスティックス（局所探索）

１００万以上 個別ソフトの０－１整数変数の処理 汎用ソフト
LocalSolverが可能

凸型（コンベックス）

線形計画法（シ 線形な連立方
程式を解く
ンプレックス法）

１００万式、
変数でも計
算可能

汎用ソフト
LP

凸型（コンベックス）

専用解法
専用アルゴリ（線形/非線形） ズム

プログラミン
グで決まる

NLP
TLP

０－１変数のタブサーチ（専用
アルゴリズムが多い）等
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

35

ーLocalSolverの適用範囲ー
離散(discreate)

LocalSolver

非線形制約
論理制約

制約論理
遺伝子ｱﾙｺﾞﾘｽﾞﾑ

ＣＰ

大規模組合せ最適化問題

ＧＡ
コンフィギュレーション

凸型(convex)

生産計画

線形計画法

スケジューリング、
順序問題

資源配分計画

線形制約

ＬＰ
ブレンディング
在庫計画

LocalSolver

ｸﾘｭｰｽｹｼﾞｭｰﾘﾝｸﾞ
フライト計画、配車計画

混合整数計画法

ＭＩＰ
実数変数

2014/10/8

LocalSolver
MSI株式会社 Copyright ⓒ 2014.

整数変数

34

LocalSolverで拡がるソリューション分野
従来、大規模問題では、探索空間が離散的であるもしくは離散的なもので表現できる問題は実用的に解けなかったが解くことができるようになった。
集合，順序，割当て，グラフ，論理，整数など離散的な構造を持つ。
多くの場合、混合整数計画問題として定式化できる．
現実世界の多くの問題は大規模組合せ最適化問題となる。
• 車両の優先順位付け（組立）問題• 裁断計画問題 (フィルムなど)• SCM問題 (製造－輸送－在庫－販売など)• 最短路問題 (カーナビのルート検索など)• ネットワーク問題 (交通網，通信網，電気、ガスなどの設計)• 配送計画問題 (宅配便，店舗への商品配送，ゴミ収集など)• 施設配置問題 (工場，店舗，公共施設などの配置など)• 人員スケジューリング問題 (乗務員・看護師の勤務表，時間割の作成など)• 機械スケジューリング問題 (工場の運転計画、装置稼働計画など)
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

35

MIPLIBでのベンチマーク結果

◾最少化問題◾実行CPU時間：５分、◾PC： Intel Core i7-820QM (4 cores, 1.73 GHz, 6 GB RAM, 8 MB cache)2014/10/8

MSI株式会社 Copyright ⓒ 2014.

36

int(lower, upper)
int(lower, upper)

LocalSolver4.5の概要

・ バイナリ(bool)意思決定変数、連続(float(下限、上限)) 意思決定変数
及び整数（int (下限、上限)) 意思決定変数でモデルを定義可能
・ ローカルサーチを基本とし、MIP、LP、CP等の解法の利点を組み込んだ
ハイブリッド型最適化エンジン
・ 数百万以上の意思決定変数問題を実用時間（数分程度）で解く
・ 見つけた実行可能解から近傍探索を開始し、最適解を目指すロジック

適用問題: supply chain optimization,
unit commitment,
portfolio optimization,
numerical optimization arising in engineering (ex: mechanics)
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

37

LocalSolver（何故局所探索か）
局所探索は大規模最適化では、標準的な考え方– 多くの教科書でも採用されているアルゴリズム– 多くの一般的なメタヒューリスティックアプローチの利点を吸収– 最悪の場合でも効率的でないことを結果として出力– 現実的な時間で実践的な最適な解を提供

逐次改善法を実現– 現在のソリューションの近傍を探索– 小さい探索空間から徐々に必要な探索空間を拡大→ 解空間全体から効率的に探索

局所探索による実用化及び汎用化を試行
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

38

LocalSolver研究経緯
局所探索による汎用化を試行
逐次改善法を実現– 現在のソリューションの近傍を探索– 小さい探索空間から徐々に必要な探索空間を拡大→ 解空間全体から効率的に探索

局所探索は大規模最適化では、標準的な考え方– 多くの教科書でも採用されているアルゴリズム– 多くの一般的なメタヒューリスティックアプローチの利点を吸収– 最悪の場合でも効率的でないことを結果として出力– 現実的な時間で実践的な最適な解を提供
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

39

LocalSolver研究成果
2000-2005: 研究開発
– Prologiaに対しOR工学を適用: 従業員スケジューリング– ROADEF2005に挑戦: ルノーの自動車組み立てラインスケジューリング(B.EstellonとK.Nouiouaが最初の賞を受賞)

貢献（成果）– 大規模組合せ最適化問題に対する方法論を提案– 大規模混合整数問題の最適化に対する方法論を提案– 局所探索をベースとして大規模組合せ最適化解法を提案– 大規模かつ混合変数問題（非凸最適化問題）に対するソルバーを提供
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

40

LocalSolver研究成果（理論及び実践でのノウハウの蓄積）
何故局所探索（近傍探索）か
列挙して最適化するのが絶望的なとき– 大規模な順列組み合わせ問題– 緩和か推論が何ももたらさない時(例えば、線形緩和は非常に断片的)– 緩和か推論を計算するのにコストがかかるとき

顧客ニーズに適合– 良質の解（目的計画法：目的順に求解、準最適解であっても着実に）– 速いこと:イタレーション時間が問題サイズに線形で比例すること→ 短い実行時間で大規模モデルが解けること
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

41

LocalSolver研究成果（アルゴリズムの特長）

適切な探索領域の設定– 探索空間の確立を高め、拡大していく– 制約条件からではなく、目的関数に基づいて探索– 現実の問題は良い探索空間を持つモデルになりやすい

局所探索: 「基本」に帰って– 「メタ」に焦点を合わせない– MOVE（イタレーション）の速さと効率性に集中– クライアントからのフィードバックとテストが重要→理論の専門技術とコンピュータ活用技術で高性能な近傍探索を実現
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

42

LocalSolver（探索イメージ）
グローバル探索としての近傍探索• 小さい近傍から探索を広げていく• 近傍探索からダイナミックに探索領域を調整：縮小、拡大、特化• 大規模領域探索にツリー探索(MIP、CP)を導入• 完全な近傍と正確な探索では最適解に到達

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

43

LocalSolver(様々なアーキテクチャを統合)
大規模混合変数、非凸最適化問題に対して、既存の最適化技術(LS, LP/MIP, CP/SAT, NLP, ...)を統合した数理計画法システムを実現。

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

44

汎用モデリング言語：LSP（概要）
LSP言語は、大規模組合せ最適化問題をモデル化し、モデルの検証及び解の検証を行うフェーズでの試行錯誤を行うのに最適な環境を提供することを目的として開発されている。
LSP言語は、最新の関数型プログラミング言語である。
関数型プログラミング言語の特長は、型推論を備えた言語であるため、JavaやC言語と異なり、コンパイラが自動的にデータの種類を推定するため、データの種類（型）をプログラマが指定する必要がない。その結果、プログラムの記述はRubyなど軽量言語のように簡潔であるが、軽量言語では実現できないコン
パイラによるプログラムのチェックが可能になる点にある。

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

47

LocalSolverのモデリング言語
LocalSolverのモデリング言語：LSPの特徴は以下：• 迅速に開発できる（開発生産性が良い。従来比、1/10から1/3の開発量）• バグを抑えやすい（コンパイラが型の間違い等を自動的にチェックする）• アプリケーションの性能を向上させやすい(マルチスレッド）• 簡潔かつシンプルなモデリング言語（できるだけ省略できるよう設計）※大規模問題でも制約条件及びデータがそろっていれば、１日でモデリングと実行が可能である。

• 目的計画法のように目的を順番に複数設定することができる（モデルの開発及び解の検証を段階的に行うことができる）• モデル作成(修正)←→実行が同時にできる（エディタ、DOSコマンドプロンプトの二つのウインドウを交互に利用)
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

46

生産性の高いモデルの記述（LSP言語）
インタプリタ型言語が搭載されており、トライ＆エラー方式で高い生産性でモデルの記述と検証が可能である。モデルは、テキストエディタを使用してLSPファイル（xxx.lsp)として作成する。
モデルは、以下の五つの関数セクションからなる。
セクショ
ン

記述

入力制
御

function
input() { }外部ファイルからデータを取り込み。それをもとにモデルに投入する変数の値を制御

モデル
定義

functionmodel() { }最適化モデルを定義

出力制
御function
output() { }最適化の結果を業務
システムなどとの連携を目的として外部ファ
イルに出力

表示制
御

function
display() { }最適化走行中に標準
出力に変数の値など
を表示

パラメタ
制御

functionparam() { }local-search の実行前にモデルをパラメタ化

2014/10/8

機能
FUNCTION MODEL(){// O-1 decisions
X_1 <-BOOL(); X_2 <-BOOL(); X_3<-BOOL(); X_4<BOOL(); X_5 <-BOOL(); X_6 <-BOOL(); X_7<-BOOL(); X_8<-BOOL();//weight constraint
KnapsackValues <-10*x_1+ 60*x_2+ 30*x_3+ 40*x_4+
30*x_5+ 20*x_6+ 20*x_7+ 2*x_8;
Constraint kNAPSACKwEIGHT<=102;//maximize Value
KnapsackValues <-1*x_1+ 10*x_2+ 15*x_3+ 40*x_4+
60*x_5+ 90*x_6+ 100*x_7+ 15*x_8;
Maximize KaapsackValue;}function output() {println("Selected Products:");for [i in 0..nbProducts-1 : getValue(x[i]) == 1]
println("#"+i+" ("+value[i]+")");}

MSI株式会社 Copyright ⓒ 2014.

49

LSPによるモデリング 意志決定変数の定義
・０－１整数変数の型を持つ意志決定変数を定義
・この意志決定変数の組合せが一つの解となる・探索は意志決定変数の組合せで行われる

 制約式、目的関数の定義
・意志決定変数を使って制約式、目的関数を表現する。
・式の表現に、算術演算子、論理演算子等が使用でき、
非線形表現で記述可能である。

 外部入出力及び、表示
・数値データの外部入力、結果の外部出力機能により、データと問題定義を完全に分離できる。このため、どんなに大きなモデルでも、モデル
本体を簡潔に表現可能である。
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

50

モデル定義（ＬＳＰ言語）
予約語

機能

bool()

意思決定変数（0-1整数変数）

float（下限、上限）
int （下限、上限）

意思決定変数（実数）
意思決定変数（整数）

constraint

制約条件（実行可能性の判定に使用）

Minimize

目的関数（最小）

定義順に最適化が適用

maximize

目的関数（最大）

定義順に最適化が適用<-

内部変数の明示的宣言

モデルの見易さ//

注釈

2014/10/8

摘要

MSI株式会社 Copyright ⓒ 2014.

51

モデルの記述例（ナップザック問題）
積める重量が102Kｇの袋に、8個のアイテムを積める場合にアイテムの価値の合計価値を最大化させる組み合わせを求める。
番号

アイテム

１

X_0

1

10

２

X_1

10

60

３

X_2

15

30

４

X_3

40

40

５

X_4

60

30

６

X_5

90

20

７

X_6

100

20

８

X_7

15

2

2014/10/8

価値

重量MSI株式会社 Copyright ⓒ 2014.

52

function model() {// 0-1 decisions
x_0 <- bool(); x_1 <- bool(); x_2 <- bool(); x_3 <- bool();
x_4 <- bool(); x_5 <- bool(); x_6 <- bool(); x_7 <- bool();

バイナリ意志決定変数

内部変数（整数）// weight constraint
knapsackWeight <- 10*x_0+ 60*x_1+ 30*x_2+ 40*x_3+ 30*x_4+ 20*x_5+ 20*x_6+ 2*x_7;
constraint knapsackWeight <= 102;}// maximize value
knapsackValue <- 1*x_0+ 10*x_1+ 15*x_2+ 40*x_3+ 60*x_4+ 90*x_5+ 100*x_6+ 15*x_7;
maximize knapsackValue;

ユーザーはLSP言語でモデルを記述するだけ！！

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

53

出力制御
function output() {println("Selected Products:");for [i in 0..nbProducts-1 : getValue(x[i]) == 1]
println("#"+i+" ("+value[i]+")");}

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

54

モデルの実行モデルは、DOSコマンドプロンプトを立ち上げ、LSPファイルの格納されているフォルダにカレントディレクトリを設定して実行する。
Cd C:¥localsolver_3_0¥example¥model¥
Localsolver model.lsp lsTimeLimit=1
model.lsp： 実行するLSPファイル
lsTimeLimit=1 ： 実行時間を1秒に設定

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

55

モデルの実行結果（１）モデルが実行され結果がログとして表示される。
:[1sec,38611 itr386111 ] : obj(280),mov=820062,inf=39.55,acc=43.5%,imp=14386111 iterations,820062 moves performed in 1 seconds
Feasible solution: obj(280)
Obj(280): 目的関数の値（解）mov=820062 : 探索回数
inf=39.55: 探索回数のうち、実行不可能解の占める割合
acc=43.5% : 探索回数のうち、実行可能解の占める割合
imp=14: 探索回数のうち、解が完全された回数
時間指定（この例では1秒を設定）などの設定により探索が打ち切られた場合、最適解の検出、実行不可能解の検出の状態を表示します。
Infeasible : 実行不可能解
feasible : 実行可能解
Optimal : 最適解
価格の合計は、実行可能解として280円が検出される。
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

56

モデルの実行結果（２）出力制御部の記述により、実行可能解などの状態や結果の内訳などを表示することができる。
Run output...
Selected Products:#2 (15)#4 (60)#5 (90)#6 (100)#7 (15)function output() {println("Selected Products:");for [i in 0..nbProducts-1 : getValue(x[i]) == 1]
println("#"+i+" ("+value[i]+")");}

価格の合計の実行可能解として検出した280円の内訳は、
X_2(30,15), X_4(30,60), X_5(20,90), X_7(2,15)の五個でその重さは102Kgであることが分かりる。
出力制御部の記述により、状態や結果の内訳などをファイルに出力（ファイル連携）
したり、アプリケーションプログラムに値を通知することもできる。
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

57

Microsoft Windows XP [Version 5.1.2600](C) Copyright 1985-2001 Microsoft Corp.
C:¥Documents and Settings¥miyazaki>cd C:¥localsolver_3_0¥examples¥toy
C:¥localsolver_3_0¥examples¥toy>localsolver toy.lsp lsTimeLimit=1
LocalSolver 3.0 (Win32, build 20121129)
Copyright (C) 2012 Bouygues SA, Aix-Marseille University, CNRS.
All rights reserved (see Terms and Conditions for details).
Run model...
Close model...
Run solver...
Model:
expressions = 38, operands = 50
decisions = 8, constraints = 1, objectives = 1
Param:
time limit = 1 sec, no iteration limit
seed = 0, nb threads = 2, annealing level = 1
Objectives:
Obj 0: maximize, no boundPhases:Phase 0: time limit = 1 sec, no iteration limit, optimized objective = 0
Phase 0:[0 sec, 0 itr]: obj = (0), mov = 0, inf < 0.1%, acc < 0.1%, imp = 0[1 sec, 386111 itr]: obj = (280), mov = 820062, inf = 39.5%, acc = 43.8%, imp =14386111 iterations, 820062 moves performed in 1 seconds
Feasible solution: obj = (280)C:¥localsolver_3_0¥examples¥toy>
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

56
58

事例（MultiObjective Knapsack問題）
function model() {// 0-1 decisions
x[0..7] <- bool();weights = {10,60,30,40,30,20,20,2};
values = {1,10,15,40,60,90,100,15};

算術演算子： prod, min, max, and, or, ifthen-else, …

// weight constraint
knapsackWeight <- 10*x[0]+ 60*x[1]+ 30*x[2]+ 40*x[3]+ 30*x[4]+ 20*x[5]+ 20*x[6]+ 2*x[7];constraint knapsackWeight <= 102;// maximize value
knapsackValue <- 1*x[0]+ 10*x[1]+ 15*x[2]+ 40*x[3]+ 60*x[4]+ 90*x[5]+ 100*x[6]+ 15*x[7];maximize knapsackValue;}// secondary objective: minimize product of minimum and maximum values
knapsackMinValue <- min[i in 0..7](x[i] ? values[i] : 1000);
knapsackMaxValue <- max[i in 0..7](x[i] ? values[i] : 0);
knapsackProduct <- knapsackMinValue * knapsackMaxValue;
minimize knapsackProduct;

予約語
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

59

演算子の例
モデリングで利用可能なおもな演算子
算術演算子

論理演算子

関係演算子

sum

sub

prod

not

==

min

max

abs

and

!=

div

mod

sqrt

or

<=

log

exp

pow

xor

>=

cos

sin

tan

if

<

floor

ceil

round

array + at>

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

60

Modeling APIs
function model() {// 0-1 decisions
x[1..nbItems] <- bool();

C++

Java

// weight constraint
knapsackWeight <- sum[i in 1..nbItems](weights[i] * x[i]);constraint knapsackWeight <= knapsackBound;}// maximize value
knapsackValue <- sum[i in 1..nbItems](values[i] * x[i]);maximize knapsackValue;C#createExpression

addOperand

2014/10/8

59

開発言語比較2014/10/8

MSI株式会社 Copyright ⓒ 2014.

62

５．LocalSolver 事例

2014/10/8

61日本の事例（SCMモデル:超大規模モデル）
１．問題概要顧客要求に合わせて、予め決められた工場ー顧客間の配送便に間に合うように、いつどこ向けになにを生産するかを決める問題（複数工場の生産スケジュール）２．モデル概要
一種類の0-1整数の意思決定変数（Bool変数）で、すべての制約を表現した。また、複数の目的関数を設定し、現実的な解法を実現した。

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

62日本の事例（SCMモデルの実行結果比較）
実行結果（１） 既存システム
全国規模を一つのモデルにすると、実用時間内で解くことができなかった（実行CPU時間を５分程度にするのに、全国規模のモデルを ２０分割にする必要があった)。

実行結果（２） LocalSolver
LocalSolverでは、 ５～６分で全国規模を一つのモデルで解くことができた。
- Bool変数: 219万以上- 複数の目的関数を重要な順番で設定し、順番に最適化計算を実行。

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

63

事例（SCMモデルの実行結果2）
Phase 0:[0 sec, 0 itr]: obj = (75593, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0), mov = 0, inf < 0.1%, acc < 0.1%, imp = 0[1 sec, 27226 itr]: obj = (64967, 0, 6534, 0, 0, 0, 29280, 2838.45, 0, 519, 1059, 28.5621, 10132.2),
mov = 48265, inf = 55%, acc = 45%, imp = 17073[2 sec, 65843 itr]: obj = (46593, 0, 23231, 0, 0, 0, 39820, 3763.47, 0, 1287, 1145, 30.6949, 27794.2),
mov = 124782, inf = 50.3%, acc = 49.6%, imp = 51706[7 sec, 237135 itr]: obj = (11, 0, 51402, 0, 22, 0, 46130, 4122.05, 0, 2702, 1161, 31.1616, 73535.1),
mov = 477135, inf = 60.2%, acc = 38.9%, imp = 146374[8 sec, 280000 itr]: obj = (11, 0, 51402, 0, 22, 0, 46130, 4122.05, 0, 2702, 1161, 31.1616, 73535.1),
mov = 560000, inf = 64.6%, acc = 34.4%, imp = 146374[9 sec, 320000 itr]: obj = (10, 0, 52006, 0, 25, 0, 46150, 4125.65, 0, 2713, 1160, 31.1471, 73522.5),
mov = 640000, inf = 67.9%, acc = 31.1%, imp = 146375[10 sec, 360000 itr]: obj = (10, 0, 52006, 0, 25, 0, 46150, 4125.65, 0, 2713, 1160, 31.1471, 73522.5),
mov = 720000, inf = 70.4%, acc = 28.5%, imp = 146376
360000 iterations, 720000 moves performed in 10 seconds
Feasible solution: obj = (10, 0, 52006, 0, 25, 0, 46150, 4125.65, 0, 2713, 1160, 31.1471, 73522.5)

2014/10/8

MSI株式会社 Copyright ⓒ 2013.

64

日本の事例（人員配置（アルバイト配置計画））
１．意志決定変数の定義（Bool変数）
X(人員、日付、時刻、業務) = {0, 1}
ここまでは装置のスケジューリングとあまり変わらないが･･･

２．人のスケジューリング特有の制約
・ 最大勤務時間
・ 最小勤務時間←あまり短いとアルバイトは出てこない・ １日１シフト←勤務の途中に何もしない時間を入れないを導入。

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

65日本の事例（人員配置計画の実行結果比較）
実行結果（１） 小モデル
人員：２０名、１週間、１時間毎の１６タイムスロット、３業務(0-1意志決定変数： 20 x 7 x 16 x 3 = 9520)
LocalSolver 3.1 ：最適解まで約２０秒
既存MIP：最適解まで約３０秒

実行結果（２） 業務モデル
人員：８３名、１週間、１５分毎の５４タイムスロット、５業務(0-1意志決定変数： 83 x 7 x 54 x 5 = 156870)
LocalSolver3.1：最適解まで約２１０秒
既存MIP：６００秒以上（制約内容等は異なっているが・・・）

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

66

日本の事例（裁断計画）
5000mmの幅をもつフィルム等のロールから、色々な幅を持つ複数製品のロールを要求本数にできるだけ近くなるよう、裁断パターンとパターンの使用回数を求める問題である。
目的関数（複合目的関数）

Valid Roll
3600
～
4600
width
Products width
Request minimum maximum
1
600
10
8
12
2
740
15
12
18
3
920
20
16
24
4
1060
5
4
6
5
1200
10
8
12

１．パターン数最小（＊1000）
２．要求数量とのギャップ最小（＊100）
３．ロス部分(4600mmからの差）。
Patter
1
2
3
4
5
6
16
n No
Produ
volume count in pattern(i)
ct
600
0
0
1
0
0
0
1
740
0
1
0
0
0
0
1
920
1
0
0
0
1
2
1
1060
0
0
0
2
1
0
1
1200
3
3
3
2
2
2
1
Total 4520 4340 4200 4520 4380 4240 4520
rest
80 260 400
80 220 360
80

2014/10/8

17

18

19

26

27

28

51

52

9本

2本

0
1
0
1
2
1
3
1
2
2
1
1
0
0
0
2
1
1
1
0
4520 4380 4340 4380
80 220 260 220

4
0
6
7
0
1
1
0
0
3
0
0
2
1
0
0
0
0
0
0
4520 4560 4340 4200
80
40 260 400

MSI株式会社 Copyright ⓒ 2014.

8本
18本
18本
8本
9本

67

日本の事例（裁断計画実行結果比較）
実行結果（１） 通常モデル
製品種類数：１０、総製品数量：１５３、切断パターン候補数：１２８９８(0-1意志決定変数： 75302)

LocalSolver 3.1 ：11秒で４パターン、要求差＝３
既存MIP：400秒すぎても９パターン、要求差＝１０

実行結果（２） 大規模モデル
製品種類数：１８、総製品数量：５０４、切断パターン候補数：７０９２１(0-1意志決定変数： 399372)

LocalSolver 3.1 ：31秒で８パターン、要求差＝１７
既存MIP：4060秒で10パターン、要求差＝２２
2014/10/8

MSI株式会社 Copyright ⓒ 2014.

68フランスの事例（Car sequencing in enault’s plants）
車両投入計画（塗装及びアセンブル）– 従来はラインに沿って部品を配置する計画– 同一色塗装の連続制約– 二次的目的として色の変更を最小限にしたい
AB

A

B

AB

A

ABC

C

A

B

C

大規模な最適化問題– 1300台の投入順を決める → 400 000 の0-1意志決定変数– MIP or CP ソルバーでは数時間の実行でも実行可能解さえ見つからない– LocalSolver は数秒で実用的な精度を持つ解を Renault に提供

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

69

Car Sequencing at Renault（比較結果）
色に関する自動車配列問題の結果を示す。LP緩和解（上限は3001（万））。
LocalSolver V3.0 (式数： 80850, オペランド数： 295212、意志決定変数： 44184, 制約条件： 636, 目的関数： 3)- 1秒で目的関数：16122の解を見つける- 6秒で3478に達する- 1分後に、3125に達する（この例で最も有名なものは3109である)

Guroubi V5.1 (式数: 29845, 列数：57331, 非零要素数：442093、連続変数：15777, バイナリ変数：41554)- LP緩和解を求めるのに、 87561イタレーション, 312 秒かかる
- B&Bで最初の実行可能解をみつけるのに647秒かかる- 1766秒後に解27720を見つける- 60分後でもコストはまだ25000を越えている
大規模組合せ最適化問題に関しては、 Branch&Boundに基づく探索では、探索が本質的に制限されるため、解くのが難しいのが実体である。
たとえヒューリスティクティクサーチ等の発見的探索法を使用するとしても限界がある。
※かなり良い線形緩和の問題（従来のMIP用ベンチマークデータ）では、従来型でもある程度実用的な時間で解を見つけることは可能である。

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

70

例題集（LocalSolver4.5)

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

73

参照文献
(1)T. Benoist, B. Estellon, F. Gardi, R. Megel, K. Nouioua (2011).
・ 「LocalSolver 1.x: a black-box local-search solver for 0-1 programming」、4OR,
A Quarterly Journal of Operations Research 9(3), pp. 299-316. Springer.
(2)MSI株式会社
・ ｢http://msi-jp.com/localsolver/｣ホームページ(3) Frédéric Gardi(2013)
・ 「Habilitation Thesis in Computer Science:Toward a mathematical programming
solver based on local search」、Université Pierre et Marie Curie (Paris 6) - Facultéd’Ingénierie (UFR 919) École Doctorale Informatique, Télécommunications et
Électronique de Paris (EDITE).
(4) Frédéric Gardi(2013)
・ 「Toward a mathematical programming solver based on local search」、
13th December 2013 ORO Workshop, Nantes.

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

74

有難う御座いました。
miyazaki@msi-jp.com
LocalSolverについてのお問い合わせ
MSI株式会社（日本配給元）〒261-7102千葉市美浜区中瀬2-6 WBGマリブウエスト２階
Tel:043-297-8841 Fax:043-297-8836
Eメール：localsolver@msi-jp.com

2014/10/8

MSI株式会社 Copyright ⓒ 2014.

75