All-In-One を目指した
LocalSolver数理計画法システムの最新動向‐LocalSolver 5.5の最新動向‐組合せ最適化問題へのLocalSolverの適用事例
2015年9月27日
宮崎 知明（MSI株式会社）

【スケジューリング・シンポジウム２０１５発表資料】【OS1-1】All-In-One Solver:LocalSolver5.5の概要紹介

2015年9月27日
宮崎 知明（MSI株式会社）

０．はじめに・ SCMの浸透により、大規模最適化問題の解決がますます重要になっているが、数理計画法システムの限界で苦労しているのが、現状。

・ 従来の方法（MIP：混合整数計画法）では解けない大規模
組合せ 最適化問題（８００万以上のパターンの組合せから最適な組み合わせを求める）を実用的に解くことができるようなソフトが出現。
・ 従来の数理計画法システムの良い点と最新のIT技術を活用した近傍探索による全く新しいハイブリッドな統合
数理計画法システム（LocalSolver) が実現された。

・ どんな大規模現実問題をも汎用的に直接モデリングできる（非線形制約、論理制約、非線形目的関数）ようになった。
2015/10/8

MSI株式会社 Copyright ⓒ 2015.

3

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

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

43

ーLocalSolverの適用範囲ー
離散(discreate＆Non-linear)

LocalSolver
制約論理

論非
理線
制形
約制
約

遺伝子ｱﾙｺﾞﾘｽﾞﾑ

ＧＡ

非線形

ＣＰ

大規模組合せ最適化問題

NLＰ

スケジューリング、

非線形最適化問題

凸型(convex)

生産計画

線形計画法

資源配分計画
順序問題

ＬＰ

線
形
制
約

ブレンディング
在庫計画

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

混合整数計画法

ＭＩＰ
実数変数

2015/10/8

LocalSolver
MSI株式会社 Copyright ⓒ 2015.

整数変数

5

MIPLIBでのベンチマーク結果

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

MSI株式会社 Copyright ⓒ 2015.

6

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

MSI株式会社 Copyright ⓒ 2015.

7

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

MSI株式会社
2014.
MSI株式会社 Copyright
Copyright ⓒ ⓒ
2015.

8

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

適用問題: supply chain optimization,
unit commitment,
portfolio optimization,
numerical optimization arising in engineering (ex: mechanics)
http://msi-jp.com/localsolver/ 参照
2015/10/8

MSI株式会社 Copyright ⓒ 2015.

9

LocalSolver開発経緯
・ 仏ブイグ社の最適化部門による2000年からの実績（汎用化を試行2000-2005年）

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

MSI株式会社 Copyright ⓒ 2015.

1010

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

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

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

MSI株式会社 Copyright ⓒ 2015.

11

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

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

MSI株式会社 Copyright ⓒ 2015.

1212

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

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

13
13

2．LocalSolver5.5の新機能（１）:• LP and MPS 標準及び二次形式ファイルの直接入力.
• GAMS モデリング言語からの使用（
www.gams.com 参照）.
• Python 2.7、3.2、3.4 用のAPIを装備.

• AMPLからの利用

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

14

LocalSolver5.5の新機能(2):• LSP 言語プログラムから解情報の取得：
getSolutionStatus() 関数（built-in variables
and functions を参照）.

• Piecewise（区分線形） 関数の導入による非線形最適化問題の実用化• List意思決定変数の導入による大規模組み合わせ問題の強化(Set based modeling).

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

15

LP, MIP変換機能:•

localsolver foo.lp lsTimeLimit=10 lsSolutionFile=foo.sol•

localsolver foo.mps lsTimeLimit=10 lsSolutionFile=foo.sol

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

16

機能及び性能に関する改良ポイント:
•
•
•
•
•
•
•

2015/10/8

Improved preprocessing: try to reformulate your model to be suitable for
LocalSolver resolution.
Improved detection and preprocessing of global structures andconstraints: knapsack subproblems and chronological flow subproblems.
Improved numerical accuracy (without degrading performance) when
dealing with floating-point expressions, through scaling techniques.
improved constraint propagation techniques for the computation oflower bounds.
Improved constraint propagation techniques integrated in neighborhood
search.
Improved feasibility search process to find a first feasible solution
quicker.
Improved self-adaptive capabilities of the neighborhood search heuristic
to your problem.

MSI株式会社 Copyright ⓒ 2015.

17

３．Piecewise linear functions の概要

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

18

Piecewise linear（区分線形） 関数とは・ LocalSolver5.0から導入（MIPでのSOSセット等に対応）。

・ 区分線形関数は端点間を直線で結んだ関数として表現できる。
・ LocalSoverでは、区分線形関数を piecewise オペレータとして定義する。
・ piecewise (x,y,z)オペレータは、ｘ、ｙ、ｚ の３つのパラメータを持つ：

X：X軸の端点リストを定義する。
Y：Y軸の端点リストを定義する。
Z：区分線形関数内のXの値を定義する（対応するY軸の値が関数値としてもとまる）。
例題： piecewise({0,50,100},{0,10,100},75) 答え：

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

55.

19

Piecewise関数の例題１．
y <- piecewise({0,10,15,48.2},{1,2,-0.5,3.15}, x).
0 <= x <=48.2.

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

20

例題２．

y <- piecewise({0,10,10,30,30,48.2},{1,1,2,2,3.15,3.15}, x).

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

21

Piecewise関数を使った時間軸付TSPの例
•

都市数：

•

計画期間：

•

各都市の作業量
citywork ={10,23,5.5,10,10,21,17,16,10,23,5.5,13,10,19,18,16,9};•

各都市の作業終了期限
cityduedate = {0,0,1,2,0,2,2,2,1,1,0,1,0,2,1,1,1};•

各月の作業可能容量： monthCapa = {90,110,50};•

Piecewise関数の定義
xlist = {0,90,90,200,200,250};
ylist = {0,0,1,1,2,2};

2015/10/8

nbCities =１７； (0, 1, 2,・・・・,16)
nbMonths = 3;(0, 1, 2)

MSI株式会社 Copyright ⓒ 2015.

22

TIMETSP.ｌｓｐの例（その１）/********** tsp.lsp **********//* The input files follow the TSPLib "explicit" format.*/function input() {usage = "¥nUsage: localsolver tsp.lsp "+ "inFileName=inputFile [lsTimeLimit=timeLimit]¥n";if (inFileName == nil) error(usage);
inFile = openRead(inFileName);stop = false;
while (!stop) {str = readln(inFile);
if (startsWith(str,"DIMENSION:")) {dim = trim(split(str,":")[1]);nbCities = toInt(dim);println("Number of cities = "+nbCities);} else if (startsWith(str,"EDGE_WEIGHT_SECTION")) {stop = true;}}// distance from i to j is distance[i + nbCities*j]distanceWeight[0..nbCities*nbCities-1] <- readInt(inFile);
citywork ={10,23,5.5,10,10,21,17,16,10,23,5.5,13,10,19,18,16,9};
cityduedate = {0,0,1,2,0,2,2,2,1,1,0,1,0,2,1,1,1};
nbMonths = 3;monthCapa = {90,110,50};

xlist = {0,90,90,200,200,250};
ylist = {0,0,1,1,2,2};}

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

23

TIMETSP.ｌｓｐ の例（その２）/* This LocalSolver model is based on the assignment of a position to each city.
The length of the tour is computed as the sum of the distance between consecutive cities,
using the at operator.*/function model() {// x[i][j] equal to 1 if city j is ith visited city in the tour
x[0..nbCities-1][0..nbCities-1] <- bool();// one city per position ifor [i in 0..nbCities-1] constraint sum[j in 0..nbCities-1](x[i][j]) == 1;// one position per city jfor [j in 0..nbCities-1] constraint sum[i in 0..nbCities-1](x[i][j]) == 1;//city[i] is the city at position i in the tour
city[i in 0..nbCities-1] <- min(sum[j in 0..nbCities-1](j*x[i][j]),nbCities-1);
local maxCode = nbCities*nbCities-1;
distanceCode[i in 1..nbCities-1] <- min(maxCode,city[i-1] + nbCities * city[i]);distanceCode[0] <- min(maxCode,city[nbCities-1] + nbCities * city[0]);// the distance of the arc reaching the ith city
distance[i in 0..nbCities-1] <- distanceWeight[distanceCode[i]];2015/10/8

MSI株式会社 Copyright ⓒ 2015.

24

TIMETSP.ｌｓｐ の例（その３）// the work to be performed at the ith city
work[i in 0..nbCities-1] <- citywork[city[i]];// the due month of the ith city
duedate[i in 0..nbCities-1] <- cityduedate[city[i]];// the cumulated work for the ith city + previous cities
cumulatedWork[0] <- work[0];cumulatedWork[i in 1..nbCities-1] <- work[i]+cumulatedWork[i-1];// the completion month for the ith city (stepwise function)month[i in 0..nbCities-1] <- piecewise(xlist,ylist,cumulatedWork[i]);// detect if the ith city is visited too lateisLate[i in 0..nbCities-1] <- month[i] > duedate[i];// the total traveled distancetotalDistance <- sum[i in 0..nbCities-1](distance[i]);// the number of cities visited too latenbLate <- sum[i in 0..nbCities-1](isLate[i]);// a mix of the two criteria

minimize totalDistance + 3 * nbLate;}

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

25

TIMETSP.ｌｓｐ の例（その４）function param() {if (lsTimeLimit == nil) lsTimeLimit = 10;}
function output() {println("Distance = "+getValue(totalDistance)+", nbLate ="+getValue(nbLate));for[i in 0..nbCities-1] print(getValue(city[i])+ " ");println();for[i in 0..nbCities-1] print(getValue(cumulatedWork[i])+ ", ");println();}

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

26

TIMETSP.atspデータの例

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

27

TIMETSP.ｌｓｐ 実行結果（その１）
Microsoft Windows [Version 6.1.7601]
Copyright (c) 2009 Microsoft Corporation. All rights reserved.
C:¥Users¥Miyazaki-MSI>cd C:¥localsolver_5_0¥examples¥TIMETSPC:¥localsolver_5_0¥examples¥TIMETSP>localsolver TIMETSP.lsp
inFileName=TIMETSP.A TSP lsTimeLimit=1
LocalSolver 5.0 (Win64, build 20150119)
Copyright (C) 2015 Innovation 24, Aix-Marseille University, CNRS.
All rights reserved. See LocalSolver Terms and Conditions for details.
Load TIMETSP.lsp...
Run input...
Number of cities = 17
Run model...
Preprocess model 100% ...
Close model 100% ...
Preprocessing transformed 136 expressions.
Run param...
Run solver...
Initialize threads 100% ...
Push initial solutions 100% ...

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

28

TIMETSP.ｌｓｐ 実行結果（その2）Model:
expressions = 858, operands = 2207
decisions = 289 (bools = 289, ints = 0, floats = 0),
constraints = 34, objectives = 1, constants = 34
Param:
time limit = 1 sec, no iteration limit
seed = 0, nb threads = 2, annealing level = 1
Objectives:
Obj 0: minimize, bound = 0
Phases:Phase 0: time limit = 1 sec, no iteration limit, optimized objective = 0
Phase 0:[ 0 sec,
0 itr] : infeas : 68 violated expressions[ 1 sec, 30244 itr] : obj =42[ 1 sec, 30244 itr] : obj =4230244 iterations, 60489 moves performed in 1 seconds
Feasible solution: obj =42
Run output...
Distance = 39, nbLate = 1
0 11 2 13 12 1 10 9 8 16 7 4 3 15 14 5 6
10, 23, 28.5, 47.5, 57.5, 80.5, 86, 109, 119, 128, 144, 154, 164, 1
80, 198, 219, 236,C:¥localsolver_5_0¥examples¥TIMETSP>

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

29

TIMETSP.ｌｓｐ 実行結果（まとめ）2015/10/8

MSI株式会社 Copyright ⓒ 2015.

30

４．List意思決定変数セット（Set-based modeling)の概要

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

31

Set-based modeling(List意思決定変数セットとは）Structured decisional operator list(n)• listセットは {0, …, n-1} の値のサブセットである。
• 一つのセット内は異なる値を持つ。

List(n)に対するオペレータ：• count(u): number of values selected in the list
• get(u,i) or u[i]: value at index i in the list
• indexOf(u,v): index of value v in the list
• contains(u,v): “indexOf(u,v)!= -1” と同じ意味• disjoint(u1, u2, …, uk) : list を切り離す• partition(u1, u2, …, uk)：listを一つの物として見る
2015/10/8

MSI株式会社 Copyright ⓒ 2015.

32

List を使ったTSPの定式化
function model() {x <- list(N) ; // order n cities {0, ..., n-1} to visit
constraint count(x) == N; // exactly n cities to visit
minimize sum[i in 1..N-1]( Dist[ x[i-1] ][ x[i] ] )+ Dist[ x[N-1] ][ x[0] ] ; // minimize sum of traveled distances}

Could you imagine simpler model?
• Natural declarative model: straightforward to understand• Common set-oriented concepts: easy to learn• Still easier for people with (basic) programming skills• Compact: linear in the size of input  highly scalable (1 million nodes)

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

33

List を使ったTSPの性能
TSP: real-life 200-client instance
LocalSolver 5.0 vs 5.5 (with operator list)
1800000

1600000

1400000

1200000

1000000

LS 5.0800000600000LS 5.5400000200000Best known solution0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

34

List を使ったVRPの定式化
function model() {x[1..K] <- list(N) ; // for each truck, order the clients to visit
constraint partition( x[1..K] ); // each client is visited once
distances[k in 1..K] <- sum[i in 1..N-1]( dist( x[k][i-1], x[k][i]) )+ dist( x[k][N-1], x[k][0] ); // traveled distance for each truck
minimize sum[k in 1..K]( distances[k] ); // minimize total traveled distance}

To go further, to make it simpler••••
2015/10/8

Sets (unordered) versus lists (ordered)
Multi-sets/lists: multiple occurrence of the same values
Collections of objects instead of values
Ability to iterate and project over collections (lambda expressions)
MSI株式会社 Copyright ⓒ 2015.

35

Capacitated VRP benchmarks
CVRP - instances A
•
•
•
•
•

32 to 80 clients, 10 trucks max.
27 instances
5 minutes of running time
LS binary: almost infeasible
LS list: 1 % avg. opt. gap

CVRP - instances X100-500
•
•
•
•
•
2015/10/8

100 to 500 clients, 138 trucks max.
67 instances
5 minutes of running time
LS binary: almost infeasible
LS list: 9 % avg. opt. gap
MSI株式会社 Copyright ⓒ 2015.

36

CVRP TimeWindow benchmarks
CVRPTW - instances Solomon R100
•
•
•
•
•

101 to 112 clients, 19 trucks max.
13 instances
5 minutes of running time
LS binary: N/A
LS list: 3 % avg. opt. gap

CVRPTW - instances Solomon R200
•
•
•
•
•
2015/10/8

201 to 208 clients, 4 trucks max.
8 instances
5 minutes of running time
LS binary: N/A
LS list: 8 % avg. opt. gap
MSI株式会社 Copyright ⓒ 2015.

37

Listを使ったTIMETSPの例•

Listは意思決定変数を定義する新しい変数セット定義であり、制約論理プロ
グラミング（CSP)のノウハウの一つでもあった。list意思 変数セットとして定義された意思決定変数セットは、0‐n までの整数値を順番に持つ。

•

都市City群を list 変数セットとして定義する。
x <- list(nbCities);city[i in 0..nbCities-1] <- x[i];•Bool変数でTSPを定式化する場合、from-to を指定するｎ×ｎのbool変数を定義する必要があるがperputation変数では、定義される変数をセットとして考慮するため、大幅な意思決定変数の削減と制約条件の計算を省くことが可能となる。

•

TSPのように、Ｎ個の箱のなかに決められた変数を入れる場合に最適である。

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

38

Listを使ったTIMETSP_new.lspの例/********** tsp.lsp **********//* The input files follow the TSPLib "explicit" format.*/function input() {usage = "¥nUsage: localsolver tsp.lsp "+ "inFileName=inputFile [lsTimeLimit=timeLimit]¥n";if (inFileName == nil) error(usage);
inFile = openRead(inFileName);stop = false;
while (!stop) {str = readln(inFile);
if (startsWith(str,"DIMENSION:")) {dim = trim(split(str,":")[1]);nbCities = toInt(dim);println("Number of cities = "+nbCities);} else if (startsWith(str,"EDGE_WEIGHT_SECTION")) {stop = true;}}// distance from i to j is distance[i + nbCities*j]distanceWeight[0..nbCities*nbCities-1] <- readInt(inFile);
citywork ={10,23,5.5,10,10,21,17,16,10,23,5.5,13,10,19,18,16,9};
cityduedate = {0,0,1,2,0,2,2,2,1,1,0,1,0,2,1,1,1};
nbMonths = 3;monthCapa = {90,110,50};
xlist = {0,90,90,200,200,250};
ylist = {0,0,1,1,2,2};}

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

39

Listを使ったTIMETSP_new.lspの例/* This LocalSolver model is based on the assignment of a position to each city.
The length of the tour is computed as the sum of the distance between consecutive cities, using the atoperator.*/function model() {削除部分// x[i][j] equal to 1 if city j is ith visited city in the tour
x[0..nbCities-1][0..nbCities-1] <- bool();// one city per position ifor [i in 0..nbCities-1] constraint sum[j in 0..nbCities-1](x[i][j]) == 1;// one position per city jfor [j in 0..nbCities-1] constraint sum[i in 0..nbCities-1](x[i][j]) == 1;//city[i] is the city at position i in the tour
city[i in 0..nbCities-1] <- min(sum[j in 0..nbCities-1](j*x[i][j]),nbCities-1);
変更追加部分x <- ulist(nbCities);city[i in 0..nbCities-1] <- x[i];local maxCode = nbCities*nbCities-1;
distanceCode[i in 1..nbCities-1] <- min(maxCode,city[i-1] + nbCities * city[i]);distanceCode[0] <- min(maxCode,city[nbCities-1] + nbCities * city[0]);// the distance of the arc reaching the ith city
distance[i in 0..nbCities-1] <- distanceWeight[distanceCode[i]];2015/10/8

MSI株式会社 Copyright ⓒ 2015.

40以下同じ：TIMETSP_new.ｌｓｐの例（その３）// the work to be performed at the ith city
work[i in 0..nbCities-1] <- citywork[city[i]];// the due month of the ith city
duedate[i in 0..nbCities-1] <- cityduedate[city[i]];// the cumulated work for the ith city + previous cities
cumulatedWork[0] <- work[0];// the completion month for the ith city (stepwise function)month[i in 0..nbCities-1] <- piecewise(xlist,ylist,cumulatedWork[i]);// detect if the ith city is visited too lateisLate[i in 0..nbCities-1] <- month[i] > duedate[i];// the total traveled distancetotalDistance <- sum[i in 0..nbCities-1](distance[i]);// the number of cities visited too latenbLate <- sum[i in 0..nbCities-1](isLate[i]);// a mix of the two criteria
minimize totalDistance + 3 * nbLate;}

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

41

TIMETSP.atspデータの例(同じデータ）

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

42

TIMETSP_new.ｌｓｐ 実行結果（その１）
Microsoft Windows [Version 6.1.7601] Copyright (c)2009 Microsoft Corporation. All rights reserved.
C:¥Users¥Miyazaki-MSI>cd C:¥localsolver_5_1¥bin
C:¥localsolver_5_1¥bin>localsolver TIMETSP_new.lsp inFileName=TIMETSP.atsp
lsTimeLimit=1
LocalSolver 5.0 (Win64, build 20150213)
Copyright (C) 2015 Innovation 24, Aix-Marseille University, CNRS.
All rights reserved. See LocalSolver Terms and Conditions for details.

Load TIMETSP_new.lsp...
Run input...
Number of cities = 17
Run model...
Preprocess model 100% ...
Close model 100% ...
Run param...
Run solver...
Initialize threads 100% ...
Push initial solutions 100% ...

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

43

TIMETSP_new.ｌｓｐ 実行結果（その2）Model:
expressions = 213, operands = 729
decisions = 1 (bool = 0, int = 0, float = 0),
constraints = 0, objectives = 1, constants = 34
Preprocessing transformed 51 expressions
Param:
time limit = 1 sec, no iteration limit
seed = 0, nb threads = 2, annealing level = 1
Objectives:
Obj 0: minimize, bound = 0
Phases:Phase 0: time limit = 1 sec, no iteration limit, optimized objective = 0
Phase 0:[ 0 sec,
0 itr] : obj =186[ 1 sec, 45711 itr] : obj =42[ 1 sec, 45711 itr] : obj =4245711 iterations, 92909 moves performed in 1 seconds
Feasible solution: obj =42
Run output...
Distance = 39, nbLate = 1
11 0 13 2 12 10 1 9 7 8 16 4 3 14 15 5 6
13, 23, 42, 47.5, 57.5, 63, 86, 109, 125, 135, 144, 154, 164, 182,
198, 219, 236,C:¥localsolver_5_1¥bin>
2015/10/8

MSI株式会社 Copyright ⓒ 2015.

44

【スケジューリング・シンポジウム２０１５発表資料】

大規模組合せ最適化問題へのLocalSolverの適用事例

2015年9月27日
宮崎 知明（MSI株式会社）【OS1-４】

５．LSP言語の概要

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

46

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

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

MSI株式会社 Copyright ⓒ 2015.

47

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

機能

bool()

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

float（下限、上限）

意思決定変数（実数）constraint

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

Minimize

目的関数（最小）

定義順に最適化が適用

maximize

目的関数（最大）

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

内部変数の明示的宣言

モデルの見易さ//

注釈

2015/10/8

摘要

MSI株式会社 Copyright ⓒ 2015.

48

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言語でモデルを記述するだけ！！

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

49

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

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

50

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

MSI株式会社 Copyright ⓒ 2015.

51

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

記述

機能

入力制御

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

モデル定
義

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

出力制御

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

表示制御

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

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

パラメタ制
御2015/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 ⓒ 2015.

52

LSP言語の演算子
モデリングで利用可能なおもな演算子（目的関数、制約式を演算子で表現可能）

算術演算子

2015/10/8

論理演算子

関係演算子

複合演算子

sum

prod

not

==

if

min

max

and

!=

array + at

div

mod

or

<=

abs

sqrt

xor

>=

cos

log

<

ceil

round

>
MSI株式会社 Copyright ⓒ 2015.

53

LSP言語のModeling API（C#、Java、C++）C++

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

Java
C#

// 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;

createExpression

addOperand2015/10/8

MSI株式会社 Copyright ⓒ 2015.

54

開発言語比較
モデル名

ｌｓｐ

C++

ｌｓｐ比

Java

ｌｓｐ比

C#

ｌｓｐ比

備考

toy

17

49

2.9

46

2.7

48

2.8 ナップサック問題（トイモデル）

car_sequencing

77

211

2.7

211

2.7

246

3.2 車両投入順序問題

knasack

44

126

2.9

128

2.9

144

3.3 ナップサック問題

maxcut

44

138

3.1

137

3.1

149

3.4 裁断計画問題

multiobj_knapsack

93

172

1.8

182

2.0

191

2.1 ナップサック問題（非線形最適化）

pmedian

66

154

2.3

154

2.3

169

2.6 OR-LIB。２点間の輸送コスト最小

比較（平均）

1.0

socialgolfer

69

CSPLIB, problem 010

steel_mill_slab_design

99

CSPLIB, problem 038

google_machine

231

Google問題（Googleがスポンサ）

table_layout

243

表配置問題

nurse_rostering

505

看護師スケジューリング

2015/10/8

2.6

2.6

2.9

MSI株式会社 Copyright ⓒ 2015.

55

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

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

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

MSI株式会社 Copyright ⓒ 2015.

56

モデルの記述例（ナップザック問題）
積める重量が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

2015/10/8

価値

重量MSI株式会社 Copyright ⓒ 2015.

57

LSP言語モデル事例（Knapsack問題）
有名なナップザック問題です。
ある袋に８つのアイテムを積める：アイテムの合計価値を最大化させる。
但し、合計重量は102Kg以下とする。
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言語でストレートにモデルを記述するだけ！
！ ⓒ 2015.
2015/10/8
58
MSI株式会社 CopyrightLSP言語モデル事例（Knapsack問題実行結果）
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>※ちなみに答えは、x_2(30,15), x_4(30,60), x_5(20,90), x_6(20,100), x_7(2,15)の５個であり、重さの合計は102kg、価値の合計は280円となる。
2015/10/8

MSI株式会社 Copyright ⓒ 2015.

59

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

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

60

モデルの実行結果（１）モデルが実行され結果がログとして表示される。
:[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円が検出される。
2015/10/8

MSI株式会社 Copyright ⓒ 2015.

61

モデルの実行結果（２）出力制御部の記述により、実行可能解などの状態や結果の内訳などを表示することができる。
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であることが分かりる。

出力制御部の記述により、状態や結果の内訳などをファイルに出力（ファイル連携）
したり、アプリケーションプログラムに値を通知することもできる。
2015/10/8

MSI株式会社 Copyright ⓒ 2015.

62

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>

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

63

LSP言語事例（MultiObjective Knapsack問題）
function model() {// 0-1 decisions
x[0..7] <- bool();

算術演算子：min、max、and、or、sin、cos、 （非線形演算子）
if-then-else…
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;

予約語

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

62

実数問題の例（最小半径決定問題）（ｘ、ｙ）を中心とし、ｎ個の点をカバーする最小半径を求める問題 （Smallest circles)

実数型意思決定変数(float)

二次計算式

x <- float(minX, maxX);y <- float(minY, maxY);

r2 <- max[i in 1..n](pow(x-coordX[i],2) + pow(y-coordY[i],2));
minimize sqrt(r2);2015/10/8

MSI株式会社 Copyright ⓒ 2015.

65

６．日本の事例

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

66

6-1 SCMモデル:超大規模モデル
１．問題概要顧客要求に合わせて、予め決められた工場ー顧客間の配送便に間に合うように、いつどこ向けになにを生産するかを決める問題（複数工場の生産スケジュール）２．モデル概要

一種類の0-1整数の意思決定変数（Bool変数）で、すべての制約を表現した。また、複数の目的関数を設定し、現実的な解法を実現した。

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

67

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

実行結果（２） LocalSolver
LocalSolverでは、 ５～６分で全国規模を一つのモデルで解くことができた。

- Bool変数:

800万以上- 複数の目的関数を重要な順番で設定し、順番に最適化計算を実行。

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

68SCMモデルの実行結果
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)

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

69

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

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

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

70

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

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

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

71

6-3 裁断計画
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

2015/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 ⓒ 2015.

8本
18本
18本
8本
9本

72

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

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

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

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

MSI株式会社 Copyright ⓒ 2015.

73

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

A

B

AB

A

ABC

C

A

B

C

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

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

74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用ベンチマークデータ）では、従来型でもある程度実用的な時間で解を見つけることは可能である。

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

75

LocalSolver
Black-box function optimizationBlack-box optimization
Context– Unknown objective (oracle)– Costly to evaluate– Derivative-free– Continuous & integer decisions– Bounds on decisions

Many applications in engineering– Multidisciplinary/parametric optimization– Simulation optimization (noisy, nondeterministic) Design optimization of materials/systems: mechanics, electricity,
logistics, etc.
2015/10/8

MSI株式会社 Copyright ⓒ 2015.

77

Learning
Learn the objective function landscape– Objective landscape modeled by Radial Basis Functions– Several models are built with different techniques/parameters– Automatic selection of the most promising models for
optimization

2015/10/8

Objective Function

MSI株式会社 Copyright ⓒ 2015.

Objective Model

78

Optimization
Exploitation & diversification– Exploitation: optimize over the objective model– Diversification: explore new promising regions
 NLP subproblems solved through LocalSolver techniques:
local & direct search, gradient-based line search, etc.

Objective Function
2015/10/8

Objective Model
MSI株式会社 Copyright ⓒ 2015.

79

Benchmark結果
Instances– 25 instances from the recent paper by Costa and Nannicini.
RBFOpt: an open-source library for black-box optimization with costly function
evaluations. Optimization Online. (under review)– 20 runs per instance, 150 calls max. to the black-box per run– Numerical precision: 1e-6

Preliminary results– RBFOpt: 345 opt. solutions found, 82 calls avg. per run– LocalSolver: 310 opt. solutions found, 94 calls avg. per run– NOMAD (GERAD): 170 opt. solutions found2015/10/8

MSI株式会社 Copyright ⓒ 2015.

80

Benchmark
LocalSolver
Instance#sol
branincamel
ex_4_1_1
ex_4_1_2
ex_8_1_1
ex_8_1_4
gear
goldsteinpricehartman3
hartman6
least
nvs04
nvs06
nvs09
nvs16
perm0_8
perm_6rbrockschoen_10_1
schoen_10_2
schoen_6_1
schoen_6_2
shekel10
shekel5
shekel7

2015/10/8

RBFOptAvg. Eval

20
20
20
20
20
20
20
18
8
8
0
20
16
20
8
0
0
20
4
0
18
10
8
6
6
310

Error (%) #sol
23
0,0
26
0,0
11
0,0
51
0,0
10
0,0
44
0,0
34
0,0
122
0,1
130
1,2
121
11,0
150
1308,0
70
0,0
127
1,0
15
0,0
138
949,0
150
109,0
150 2424958,0
83
0,0
145
66,7
150
96,2
101
100,8
120
28,0
118
29,6
127
51,6
127
28,5

NOMAD
Avg. Eval
20
20
20
20
20
20
20
20
20
17
0
19
0
20
20
0
0
5
11
14
18
16
13
7
5
345

Error (%) #sol
31
0,0
34
0,0
14
0,0
9
0,0
7
0,0
25
0,0
7
0,0
53
0,0
45
0,0
101
5,1
150
204,7
64
194,4
150
13,3
14
0,0
49
0,0
150
147,2
150
44134,7
136
10,8
139
28,8
133
1,6
101
1,8
102
32,7
107
60,1
126
51,7
137
47,0

MSI株式会社 Copyright ⓒ 2015.

Error (%)
20
0,0
19
4,0
20
0,0
20
0,0
19
2,5
0
341,5
0
388,0
16
450,0
15
9,4
0
5,7
0
129,0
4
9997,0
9
8,7
16
1,2
9
885,0
0
412,0
0
311032,0
0
43,2
0
119,5
0
115,7
0
51,5
0
54,2
0
56,9
1
46,1
2
47,9
170

81

Roadmap（仏からのメッセージ）
John N. Hooker (2007) ：CMU教授“Good and Bad Futures for Constraint Programming (and Operations Research)”
Constraint Programming Letters 1, pp. 21-32“Since modeling is the master and computation the servant, no computational method should presume to haveits own solver.

This means there should be no CP solvers, no MIP solvers, and no SAT solvers. Allof these techniques should be available in a single system to solve the model at hand.
They should seamlessly combine to exploit problem structure. Exact methods should evolve gracefully into
inexact and heuristic methods as the problem scales up.”2015/10/8

MSI株式会社 Copyright ⓒ 2015.

82

LocalSolverとは（仏からのメッセージ）
Hybrid math optimization solver

For combinatorial, numerical,
or mixed-variable optimization
Suited for large-scale
non-convex optimization
Quality solutions in seconds
without tuning

LocalSolver = LS + CP/SAT + LP/MIP + NLP
2015/10/8

MSI株式会社 Copyright ⓒ 2015.

83

７．おわりに

３０年前には殆ど実現出来なかった大規模組合せ最適化問題に対して、実践的なアプローチが実現できる時代になったと考える。
また、大規模最適化問題の定式化技術が進歩し、簡単に大規模問題の作成が可能となっている。
「実学に役立つOR」として、人間と機械の調和を実現して日本の産業界の再生の一助となれ
ば幸いである。

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

84

参照文献
(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.

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

85

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

2015/10/8

MSI株式会社 Copyright ⓒ 2015.

86