バックナンバー ( 2016 Vol.1 ) 2016 年 1 月 14 日 発行
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム 最適化メールマガジン http://www.msi.co.jp/nuopt/ 2016 Vol.1 ( 2016 年 1 月 14 日 発行 ) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム 最適化メールマガジンでは，数理計画法パッケージ 数理システム Numerical Optimizer をはじめとして，最適化に関する様々 な情報やご案内を提供していきます． ++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++ ■ <トピック> 新年のご挨拶 ■ <トピック> Numerical Optimizer V18 新機能紹介(3) ～ 計算性能向上 ～ ■ <セミナー> Numerical Optimizer セミナーのご案内 ■ <トピック> 数理計画問題の豆知識（第 21 回） ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ****************************************************************** ■ <トピック> 新年のご挨拶 ****************************************************************** 新年おめでとうございます． 昨年を振り返ると，ビッグデータ，Internet of Things から人工知能まで， 数理科学をビジネスに適用する記事がメディアに出ない日はないという 1 年でした．NTT データ数理システムでも，数理最適化をはじめ統計解析・ 機械学習やテキスト分析，シミュレーションなど幅広いお引き合いを いただき，このトレンドはまだまだ衰えるものではないと実感しています． 社会・経済に関する時事を見ても，インダストリ 4.0，電力自由化，TPP に伴う農業高度化，オリンピック・パラリンピック等々，いわゆる 「デジタル・ビジネス・トランスフォーメーション」の対象領域の広がりと ともに，数理最適化がその根幹技術として登場する場面も益々増えてくる ものと思われます． Numerical Optimizer もこの期待に応えるべく，データ分析・活用の統合 プラットフォーム VAP（Visual Analytics Platform）の一翼として， 統計解析・機械学習，シミュレーションを有機的に結び付け，数理科学的な アプローチで社会を取り巻く課題を解決する真に役立つツールに高めて いきたいと考えています． 今年も引き続き，Numerical Optimizer ならびに NTT データ数理システム のご愛顧のほど，よろしくお願い申し上げます． （中川 慶一郎） ****************************************************************** ■ Numerical Optimizer V18 新機能紹介(3) ～ 計算性能向上 ～ ****************************************************************** Numerical Optimizer の開発チームでは，日々開発を行っております． ここでは主に Numerical Optimizer の計算性能面に関する向上について 述べたいと思います． ◆ 線形計画問題における向上 数千万変数から数億変数からなる「超大規模」線形計画問題に対応した 内点法を開発しました．本アルゴリズムは大規模レコメンデーションや 広告配送問題，ネットワーク問題など幅広い分野での活躍が期待されます． 中規模程度の問題においても，内点法の一次方程式を解く部分において SIMD 命令を用いるなどの改良により速度が向上しています． 線形計画問題に対するアルゴリズムとして，従来の単体法に加え，「双対 単体法」を導入しました．これは双対問題において実行可能となる基底解を 経て最適解を得る手法です．従来の単体法と比較すると，問題によっては 数倍の速度向上が見込めます． ◆ 整数計画問題における向上 分枝限定法の内部において，発見的解法として「RINS」と呼ばれるアルゴ リズムを組み込みました．これは線形緩和問題と暫定解の二つの解情報を 用いて，内部でコンパクトな混合整数計画問題を作成して解くことにより 実行可能解を得る手法です．本手法により，従来よりも早い段階で実行 可能解が求まるようになっています． V17 以前の WCSP タブーサーチでは，ハード制約の違反が解消不可能な ケースにおいてはソフト制約の違反量を適切に減らすことができません でした． V18 ではこちらを改良し，ユーザが適当な閾値を設定することによりその 閾値を超える反復回数ではハード制約違反量が残存した状態でもソフト 制約の違反量を適切に減らせるようにしました． 今後もユーザの皆様からの声にお応えするために性能向上に努めたいと 思います．速度をもっと速くしてほしい／解の精度を上げてほしい，という 問題があれば，いつでもお問い合わせください！ （藤井 浩一） ****************************************************************** ■ <セミナー> Numerical Optimizer セミナーのご案内 ****************************************************************** --- [ Numerical Optimizer 定例セミナー開催日程 ] ----------------- ・2 月 9 日（火）13:30 ～ 17:00 Numerical Optimizer スキルアップセミナー ・2 月 10 日（水）13:30 ～ 17:00 Numerical Optimizer ハンズオン実習 ------------------------------------------------------------------ --- [ 特別開催 ロジスティクスソリューション最適化セミナー ] ------ ・3 月 24 日（木）13:30 ～ 16:30 開催 ロジスティクス分野向けの特別セミナーを開催いたします． 配車・配送，バンニングについて当社のアルゴリズムを用いて開発した 事例を中心にご紹介いたします． 併せて道路交通シミュレーションの事例もご紹介いたします． 第 1 部．配送・配車最適化 NTT データ数理システムのアルゴリズムをご採用頂いた， NEC ソリューションイノベータ株式会社「ULTRAFIX」をご紹介致します． 講師：月山 賢治様（NEC ソリューションイノベータ株式会社） 第 2 部．最適バンニング NTT データ数理システムのアルゴリズムをご採用頂いた， 積み付け最適化計算システム「バンニングマスター」をご紹介致します． 講師：若狭 信治様（ネットロック株式会社） 第 3 部．数理システム事例紹介 以下の各事例をご紹介致します． 《最適化》食用油脂配送 配車計画システム システム受託開発事例 《シミュレーション》大都市の道路交通シミュレーションおよび ユーザー活用事例 http://www.msi.co.jp/nuopt/download/docs/logistics_seminar.pdf ------------------------------------------------------------------ 会場 : （株）NTT データ数理システム セミナールーム 東京都新宿区信濃町 35 信濃町煉瓦館 4 F アクセスマップ http://www.msi.co.jp/msi/location.html 各セミナーのお申し込みは下記からお願い致します． http://www.msi.co.jp/event/index_nuopt.html （飯島 剛） ****************************************************************** ■ <トピック> 数理計画問題の豆知識（第 21 回） ****************************************************************** 今回は積み付け問題に関して紹介させていただきたいと思います．ここで いう積み付け問題とはコンテナローディング問題，またはビンパッキング 問題として定式化される問題のことを表しています． 以下では，各品物及び容器は矩形（長方形）や直方体をしていると仮定 いたします． 積み付け問題を一言で言うと，「さまざまな制約条件のもと，箱（または コンテナ，またはパレット）に製品を積載する」方法を計算する問題です． ここでの制約条件は，例えば - はみ出さない（天井がない場合はあり得るが） - 過積載をしない - 浮かない - ある製品は横倒し禁止 - ある製品の上にはものを置かない（強度とか） などであり，製品全てを積載するために必要な箱を減らすことを目的と します．製品数が多い場合には，逆に利益を最大化できるように製品を 選択するという場合もあります．これはナップサック問題に相当します． 問題を特徴づけるのは - 上記のような目的関数の違い - 製品の種類が多い/少ない/ 1 種 - 箱の種類が多い/少ない/ 1 種 - 製品が多いかどうか - 箱の数に上限はあるか などです．これらの特徴により問題の種類が分かれており，現状すべての 種類の問題を効率的に（良い精度で）解くことのできるアルゴリズムは 知られていないのではないでしょうか．（知っていたらぜひともご教授 ください） 突然ですが，2 次元の場合の例題を 4 つ出します．パレットの種類， 製品の種類は単一で，特別な制約はなしです． ** ただしパレットからはみ出すのは禁止です ** （例題）全ての問題で製品 X のサイズを 1 × 2 とします． X をすべて 1 枚のパレットに乗せてみてください． 1. 2 × 3 のパレット, X を 3 個 2. 3 × 3 のパレット, X を 4 個 3. 4 × 5 のパレット, X を 9 個 4. 10 × 10 のパレット, X を 50 個 できましたか？では解答例です． 1. 2 ブロックのブロック積み ┌─┐ ├┬┤ │││ └┴┘ 2. ピンホイール積み ┌─┬┐ ├┬┤│ │├┴┤ └┴─┘ 3. 二つ穴のピンホイール積み ┌─┬┬┐ ├┬┤││ │├┴┼┤ ├┼┬┤│ ││├┴┤ └┴┴─┘ 4. れんが積み ┌─┬─┬─┬─┬─┐ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ └─┴─┴─┴─┴─┘ 呼び方は JIS Z0111 に従っています． 今回は目的関数がありませんでしたが，実際の問題では作業のしやすさ などが目的関数になってきます．上の例ではれんが積みが最も作業が楽で あり，積み方を考える上で第一候補になります．その意味で，個数は多い ものの 4 番が最も簡単な問題といえます． この問題は 2 次元でしたが，3 次元積み付けを考える際にも，パレットを 中心とした積載計画においては有用な考え方です． 積み付けの例を話してきましたが，意外なところでこれが使えるようです． クラウドにおけるリソースマネジメントの問題です．サーバー集約 （server consolidation）という言葉をグリーン IT の文脈で聞きますが， そこのリソース割り当て問題が各種ビンパッキング問題に帰着されます． また，ネットワーク割り当てや資源割り当てなどの個別の割り当てを考える こともあります． この問題のさらなる進展を心から望んで，最後に特別問題を出して文章を 締めたいと思います． （問）8 × 7 のパレットに X 25 個を乗せてください． ヒント: 穴が 6 個 （清水 超貴） ================================================================== ※ このメールは，展示会・セミナー等で名刺交換をされた方，過去に 数理システム Numerical Optimizer に関するお問い合わせを頂いたこ とのある方，および本メールマガジンの配信を希望された方にお送り しています． ※ バックナンバーはこちらから御覧頂けます． http://www.msi.co.jp/nuopt/mailmagazine/index.html ※ 本メールマガジンは等幅フォントでお読みになることを推奨します． ※ 今後このメールマガジンが不要な方は，誠にお手数ですが，「メール マガジン配信停止」という件名のメールを nuopt-ms@ml.msi.co.jp にお送りください．なお，反映作業の都合上，数日間は旧情報にてメー ルが届く場合がございます．なにとぞご容赦ください． 発行：株式会社 NTT データ数理システム << 数理システム Numerical Optimizer >> 担当 東京都新宿区信濃町 35 番地 信濃町煉瓦館 1 階 tel : 03-3358-6681 e-mail : nuopt-info@ml.msi.co.jp ==================================================================