FICO

TM

Xpress Optimization Suite

Xpress-Tuner
User guide 日本語版

最終更新

www.ﬁco.com

2009年5月26日

Make every decision count TM

User guide 日本語版

Published by Fair Isaac,
Copyright Fair Isaac Corporation 2009. All rights reserved.
All trademarks referenced in this manual that are not the property of Fair Isaac are acknowledged.
All companies, products, names and data contained within this book are completely ﬁctitious and are used solely toillustrate the use of Xpress-MP. Any similarity between these names or data and reality is purely coincidental.

How to Contact The Xpress TeamUSA, Canada and all Americas
Information, Sales and Licesing
Information and Sales: info@dashoptimization.com
Licensing: license-usa@dashoptimization.com
Product Support: support-usa@dashoptimization.com
Tel: +1 (201) 567 9445
Fax: +1 (201) 567 9443
Dash Optimization Inc.
560 Sylvan Avenue
Englewood Cliﬀs
NJ 07632
USAJapan
Xpress Optimization Japan
Information and Sales: info@jp.dashoptimization.com
Licensing: license@jp.dashoptimization.com
Product Support: support@jp.dashoptimization.com
Tel: +81 43 297 8836
Fax: +81 43 297 8827
WBG Marive-East 21F FASuC B2124
2-6 Nakase Mihama-ku261-7121 Chiba
JapanWorldwide
Email: XpressSalesUS@ﬁco.com

WORLDWIDE
Email: XpressSalesUK@ﬁco.com
Tel: +44 1926 315862
Fax: +44 1926 315854
FICO, Xpress team
Leam House, 64 Trinity Street
Leamington Spa
Warwickshire CV32 5YN
UK

Product Support
Email: Support@ﬁco.com(Please include ʼ Xpressʼ in the subject line)
Telephone:
NORTH AMERICA
Tel (toll free): +1 (877) 4FI-SUPP
Fax: +1 (402) 496-2224
EUROPE, MIDDLE EAST, AFRICA
Tel: +44 (0) 870-420-3777
UK (toll free): 0800-0152-153
South Africa (toll free): 0800-996-153
Fax: +44 (0) 870-420-3778

Japanese Copyright 2011- MSI Co., Ltd. All Right Reserved

c 2009 Fair Isaac Corporation. All rights reserved.

page 1

User guide 日本語版

ASIA-PACIFIC, LATIN AMERICA, CARIBBEAN
Tel: +1 (415) 446-6185
Brazil (toll free): 0800-891-6146
For the latest news and Xpress software and documentation updates, please visit the Xpress website at
http://www.ﬁco.com/xpress or subscribe to our mailing list.

Japanese Copyright 2011- MSI Co., Ltd. All Right Reserved

c 2009 Fair Isaac Corporation. All rights reserved.

page 2

User guide 日本語版

FICO Xpress Optimization SuiteTM

Xpress-Tuner
User guide 日本語版
Release 1.1
2009. 5. 26

目次11

Xpress-Tuner の目的 .......................................................................................................32

問題を、どのようにチューニングするか .........................................................................x3

チューニングのプロセス ...................................................................................................x4

詳細結果 .........................................................................................................................x5

一組の問題をチューニングする ......................................................................................x6

チューニング方法 ............................................................................................................x7

用語 ..................................................................................................................................x

Xpress-Tuner の目的
Xpress-MP は、cutting planes、heuristics、branch and bound search などの多くのアルゴリズ
ム、テクニックを適用して MIP 問題を解きます。Xpress-MP の内部のアルゴリズムは、ユーザが、コントロール・パラメータを通じて、カスタマイズできます。Xpress-MP のコントロール・パラメー
タは、下記の 1 つ、もしくは、複数をコントロールできるように設計されています。
• 一つを選択する (e.g. breadth-ﬁrst versus depth-ﬁrst search)• 一組を選択する (e.g. pick and choose presolve techniques)• 数の大きさ (e.g. number of rounds of knapsack cuts)• 頻度 (e.g. apply heuristics every N nodes)
Xpress-Tuner を使うと、Xpress-Optimizer が、デフォルト値を使うよりも、特定の MIP 問題 ( または、一組の問題 ) を速く解くことができるような「一組の望ましいコントロール・パラメータ」を見つけることが出来ます。

Japanese Copyright 2011- MSI Co., Ltd. All Right Reserved

c 2009 Fair Isaac Corporation. All rights reserved.

page 3

User guide 日本語版

Xpress-Tuner により、Xpress-Optimizer ライブラリ、Xpress-Mosel、Xpress-BCL を使い、容易に実行できる簡潔な最もよい戦略がわかるので、経験の浅いユーザでも、Xpress-MP を、容易に、有効に使えるようになります。同時に、Xpress-MP コントロール・パラメータに詳しい経験の豊富なユーザには、異なるソリューション・アプローチに関して、問題がどのようなパフォーマンスをするのかを詳細に分析するための豊富な情報を提供します。

2

問題を、どのようにチューニングするか

Xpress-Tuner を起動させると、下記のようなウインドウが開きます。

ここで、重要なユーザ・インターフェースには、下記のようなものがあります。
1. 問題ファイル名：これは、.MPS、.LP ファイル、圧縮された .MPS.GZ、.LP.GZ ファイル、または、( マトリクス集合を含んでいる ) .SET ファイルのいずれかです。問題ファイル名は、調整したいファイル ( または、ファイルのセット ) を表します。
ノート：Xpress-Tuner は、¥tuner¥ という作業ディレクトリを、問題ファイル名が位置しているのと同じディレクトリに生成します。Xpress-Tuner のすべてのランは、この新たに作成されたディレクトリに保存されます。
2. 最適化の方向：minimize or maximize
3. 目標とする「問題の optimality gap」：通常は 0%、しかし、0%-100% の間のどのような数字でもよい（例えば､0.1%）
4. 問題を解くのに割ける希望ランタイム：この希望ランタイムは、業務で使うときの要件に基づく現実的な期待時間を使うべきです。例えば、Xpress-MP が最適解を見つけるには 5 分かかっ
Japanese Copyright 2011- MSI Co., Ltd. All Right Reserved

c 2009 Fair Isaac Corporation. All rights reserved.

page 4

User guide 日本語版ており、その 5 分のうちの多くを多くの時間を branching に使っているとするなら、60 秒というアグレッシブな目標時間を入力すべきです。
ノート：時間は、つねに、「秒単位」です。
5. Reduce time to gap は、おそらく、最も望ましいゴールでしょう。しかし、その他のゴールも利用可能です。
6. チューニングのための合計時間：よくチューニングされた戦略を得るには、「寛容な時間」を与える必要があります。最良の結果を得るには、最低、200 ランを許すべきでしょう。(e.g.
60s × 200 runs = 12,000 s)
7. 状況に応じて、コントロール・パラメータの一部に、baseline parameter として値を入れ、設定を強制します。これらは、自動化チューナーにより得られる潜在的な値に優先します。
8. チューニングメソッドを選択する：Adaptive ﬂexible 1 は、最も網羅的なチューニングメソッドであり、したがって、通常、良い最初の選択です。
9. 必要に応じてチューニングメソッドをカストマイズする：それぞれのチューニングメソッドごとのインストラクションが利用可能です。
10. Start をクリックするとチューニングが始まる。

Japanese Copyright 2011- MSI Co., Ltd. All Right Reserved

c 2009 Fair Isaac Corporation. All rights reserved.

page 5

User guide 日本語版

3 チューニングのプロセス
Xpress-Tuner が動いている間、下記のようなディスプレーが表示されます。

このディスプレーで重要なポイントは、下記です。
1. チューニング目標のサマリー。ターゲットとする ( 望ましい ) ギャップ、および、1 ランごとに許すランタイムを含む。
2. progress update section は、チューニングセッションが開始されてからどのくらいの時間が経過しているか、および、(Tuner を始動するとき課したタイムリミットに基づき ) どのくらいの時間が残っているかを示します。また、この部分で、Tuner が、Xpress-Optimizer デフォルトを改善したかどうかも示します。「View Detailed Strategy Rankings」ボタンをクリックすると、より詳細を示す window が開かれます (Xpress-Tuner ユーザガイドの section 4 に説明があります )。Include runs from previous sessions というチェックボックスは、同じ問題の前のチューニングセッションのランを、詳細 window に表示するかどうかをコントロールします。
3. activity log は、前に完成した戦略ランのいくつかの、非常に簡単なサマリーを示します。
4. この section は、active control parameter strategy、および、output from the active
optimization run を示します。Stop ボタンを押すことで、Tuner セッションを中断できます ( このとき、すべての Tuner 結果はディスクに保存されるので、セッションを停止することは安全です。Tuner の次回の作業は、前の結果を読むことで、中止されたところから再開されます )。
5. 下の 6 番目の項目と同じように、Xpress-Tuner の最も重要な display section です。
Baseneversus Best so far 比較は、現在の最も良い調整された戦略は、baseline run との対比で、どのようなものであるかを示します。多くの場合、チューニングによる結果の方が優れてJapanese Copyright 2011- MSI Co., Ltd. All Right Reserved

c 2009 Fair Isaac Corporation. All rights reserved.

page 6

User guide 日本語版

います。
すべての戦略ランの後に、現在までに得られた最良の戦略を示すために、このセクションはアップデートされます。
6. 最もよい戦略の設定 : 最もよい戦略を構成するコントロール・パラメータのリスト。
このリストは、現在の最もよい戦略でアップデートされ、Tuner がどのように作業を遂行しているかについて、フィードバックします。
戦略を、相互に比較するには、View Detailed Strategy Rankings. をクリックします。

4

詳細結果
View Detailed Strategy Rankings をクリックすると、下のような window が出てきます。
E このリストの各行はランを示し、各ランは、Tuner が試みたユニークな戦略を示します。
このリストの一覧は下記の通りです。

MachineTuner がランしているコンピュータ名

Xpress Version

Xpress-Optimizer のバージョン .

Whenランが開始されたときの、日付けと時間 (+milliseconds)

Alg

最初の LP 緩和に使われたアルゴリズム

File

チューニングされているマトリックス（もしくは、一組のファイル）

MAXTIME（ユーザによって課される）global search のための時間制限

MIPRELSTOP（ユーザによって課される）相対的ギャップ・ストッピング･クライテリア

Japanese Copyright 2011- MSI Co., Ltd. All Right Reserved

c 2009 Fair Isaac Corporation. All rights reserved.

page 7

User guide 日本語版

Control parameters

コントロール・パラメータで可変。値なしは「デフォルト」を意味する。

Rank

ユーザによって指定されるゴールに基づくランク(e.g., best gap, best solution, etc.)

Run time

初期のＬＰ緩和のための時間を含む、実際の経過時間

Gap optimality

gap を意味する。MIPRELSTOP の定義を見る。

Objective

ランの最良の integer solution

Bound

ランの最良の boundRoot Gap

root node の後の optimality gap

Root Objective

root node の後の最良の integer solution

Root Boundroot node の後の最良の boundSolutions

見つかった実行可能ソリューションの数

Nodes

探査された branch and bound nodes の数

緑色の部分は、カラムでの相対的なランクを示します。薄い緑色の部分、より小さい値を、濃い緑色の部分は、より大きい値を示します。
ノート：コラム間の比較は無意味です。
Gap コラムなどのように、場合によっては、薄い緑色のほうが良く、低い ( より良い ) ランクのと関連します。最小化問題の Bound コラムなどの場合では、( 濃い緑色でハイライトされる ) より大きい値のほうがより良い値です。
テーブルの結果は、コラムヘッダーをクリックすることでソートできます。ソーティングは安定しています。これは、いくつかの評価基準を、順次、適用できることを意味します (e.g. sort bygap, then by objective, then by number of nodes)。
テーブルの結果は、クリップボードにコピーして ( クリップボードへのコピー )、次いで、Excelなどにペイストできます。
結果のリストで右クリックすることで、現在、選択しているところで、いろいろな操作オプションが利用可能です。例えば､現在のコラムの値が、現在、マウスカーソルの置かれているところの値と等しいすべてのランを選択するのなどです。1 つ、もしくは、それ以上のランが選択されているとき、「View / Compare Selected...」というボタンをクリックすると、下図のように、二つ以上のランを並べて分析できます。
Japanese Copyright 2011- MSI Co., Ltd. All Right Reserved

c 2009 Fair Isaac Corporation. All rights reserved.

page 8

User guide 日本語版

Japanese Copyright 2011- MSI Co., Ltd. All Right Reserved

c 2009 Fair Isaac Corporation. All rights reserved.

page 9

User guide 日本語版

5

一組の問題をチューニングする
Tuner を使用して得られるコントロール・パラメータの設定が、確実に、対象とする問題カテゴリ全体のコントロール・パラメータとして、十分、頑健であるようにするために、数学的モデルに、いろいろな入力を選択し、同じモデルのいくつかのマトリクス・インスタンスを生成するのはよい考えです。同じモデルの異なるマトリクス・インスタンスをグルーピングして一組とし、次いで、この一組のマトリクス・インスタンス向けに、Xpress-Tuner に良くチューニングされた戦略を見つさせると、同じモデルの新しいインスタンスでうまくいく設定が得られます。
この場合、Strategy Rankings window は、下記のようになります。

個々のマトリクスのランが、セットのランと並んで記載されており、お互いに比較されてランクされていることに注意してください。上のスクリーン・ショットは、air04.mps と air05.mps を、air.set と呼ばれるセットにグループすることで得られたものです。Rank1 を示す air04.mps のランの一つは、Rank2 を示す air04.mps のランよりも良いことが判ります。こうして、戦略ランキング詳細ウィンドウにより、ユーザは、セットだけではなく、セットのコンポーネントも比較できます。この比較から、さらに深い洞察が得られるでしょう。

Japanese Copyright 2011- MSI Co., Ltd. All Right Reserved

c 2009 Fair Isaac Corporation. All rights reserved.

page 10

User guide 日本語版

6 チューニング方法
下の図に見られるように、デフォルトで、何種類かのチューニング方法が利用可能です。

注 1：全てのチューニング法はカスタマイズ可能。
注 2：どのチューニング法もクローン化いた後、カスタマイズ可能。
チューニング方法：
Adaptive ﬂexible comprehensive4

殆どの目的に対して、もっともよい選択。網羅的なチューニング方式で多くの戦略を内包している。
これらはユーザーがカスタマイズできる。

Adaptive ﬂexible 2 Adaptive ﬂexible 1 と同一のチューニング方式であるが、当初、内包している戦略の数が少ない。Comprehensive method
ほど、一般的ではないですが、この方式は Tuner がadaptive phase に高速に達することが可能です。この方式はチューニング時間をセーブするため、質は低下します。
Adaptive ﬂexible root focus

このチューニング方式は、MP search の node に影響を与え、コントロール・パーラメントでフォーカスします。

Japanese Copyright 2011- MSI Co., Ltd. All Right Reserved

c 2009 Fair Isaac Corporation. All rights reserved.

page 11

User guide 日本語版

Adaptive ﬂexible tree focus

この方式は MIP search の Brancing phase に影響を与え、コントロール・パラメータでフォーカスします。

Adaptive pure comprehensive

この方式は、最初は Adaptive Flexible comprehensiveと同一の戦略数を内包しています。導出された戦略候補を選択するため非常にエリート主義な進化的スキームを使う。

Adaptive pure quick

Ａdaptive pure comprehensive と同一方式ですが、root node でフォーカスすることに重点を置く。

Adaptive pure tree focus

Adaptive pure comprehensive と同一方式ですが、分枝限定探査に重点を置く。

Combinations

このチューニング方式は、少数のコントロール。パラメータのすべての組合せをテストする。

Mixer

ディスクから、以前に行われたすべてのコンパティブルなランを読み込み、そして、適応型の進化的アルゴリズムを適用して、より良い戦略を導出する。例えば、cutting strategy にフォーカスしている Tuner session、strong branching にフォーカスしている Tuner session を別々にランして、次いで、三番目のランとして、それらを Mixer チューニング方法でランする。

Single run 1

単一の戦略を試すショートカット。

Single run 2

別の、単一の戦略を試すショートカット。

Japanese Copyright 2011- MSI Co., Ltd. All Right Reserved

c 2009 Fair Isaac Corporation. All rights reserved.

page 12User guide 日本語版

7

用語
以下に、このユーザガイドで使われている用語を、Xpress-Tuner のコンテクストで説明します。
Control parameter setting

コントロール・パラメータは、Xpress-Optimizer をカスタマイズするのに使 うことができる名前を付けられた設定です。
例えば、CUTSTRATEGY=0 は、ある問題にカットを適用する設定を無効にするよう Optimizer に命令するコントロール・パラメータです。

Problem

解くマトリックス・ファイル

Run

ランとは、所与の問題を、所与の戦略で行う
Xpress-Optimizer の実行を意味する。

Sessionセッションは、あるチューニング方式の完全な実行を意味する。Start ボ タンをクリックして、チューニングセッションを開始すると、Xpress-Tuner は、選択されたチューニング方式に従って、異なる戦略を試みる。そして、与えられたタイムリミットを使い果たすか、または、Stop ボタンを押すことで、ユーザによって止められるまで execution を継続する。

Set(Xpress-Tuner の「Create a set of matrices...」ボタンを使用して一つのセ ットにグループ化された問題の集まり。
Xpress-Tuner は、セットの中のすべての問題を自動的に実行して、セット全体を対象とした結果を計算する。
ノート：セットにおける、すべての問題のすべてのランの平均ギャップは、セットランを比較するのに使用される唯一の評価基準です。

Strategy

あるランで一緒に適用される一つ以上のコントロール・パラメータ設定。例えば、「CUTSTRATEGY=0、HEURSTRATEGY=3」は戦略です。

Japanese Copyright 2011- MSI Co., Ltd. All Right Reserved

c 2009 Fair Isaac Corporation. All rights reserved.

page 13

User guide 日本語版

Tuning method

ランを実行するための、それぞれのいくつかの適応型の、または、非適 応型のテクニック。これらのランのゴールは、ある問題、もしくは、セット化された一組の問題を解くための、望ましい戦略を見つけること。

Japanese Copyright 2011- MSI Co., Ltd. All Right Reserved

c 2009 Fair Isaac Corporation. All rights reserved.

page 14