整数計画法メモ

トップページへ戻る

本ページのURLが http://www.tuat.ac.jp/~miya/ipmemo.html から http://web.tuat.ac.jp/~miya/ipmemo.html へ変更になりました.
それに応じて,本ページからリンクされているダウンロード可能なファイルについても,URLが変更になっています.
(当面は旧URLにアクセスした場合でも,自動的に新URLにリダイレクトされます)


はじめに

 このページには,整数計画問題をソルバーで解く際に,知っていると役に立つかもしれない情報を雑多に記しています. 整数計画法は強力な最適化手法の一つなのですが,「実際に解きたい」時に日本語の情報があまり無い,と耳にしたのがこのページを作ったきっかけです.

おことわり

 このページに書いてある情報は無保証であり,筆者は一切の責任を持ちません. 自己責任でご利用ください. もちろん,なるべく正しいことを書くようにしますが,情報が古くなったり間違っていたりすることもあると思われます. お気づきの方は筆者までご連絡いただけると幸いです. 特に,リンク先(URL/その内容)やソルバー機能の変更,整数計画法や計算機の進歩による定石の変化などにご注意ください.

宮代 隆平(東京農工大学 工学部 情報工学科)

参考文献

 入門向け,およびこのページに関係するものからいくつかを紹介します. 文献 9 は,非商用ソルバーのダウンロードなども含め,ソルバーを初めて使う際のガイドを記しています. LP ファイルの簡単な解説も含んでいます. 文献 7 は,少し古くなってしまいましたが,整数計画法についてごく簡単にまとめてあります. 文献 15 は,整数計画法とはどんなものか,近年の情報がスライド形式でわかり易くまとめられています. 文献 1, 5 は,整数計画法における定式化のテクニックが日本語でまとまっています. 文献 5, 12 は,整数計画を使った定式化の例が多数記述されています. 文献 8 は,やや専門的になりますが,近年の分枝限定法の発展について述べています. 下記の「よくある質問」で,特定のソルバーを対象にした解説では,ソルバーに応じて文献 2, 3, 13 からの情報を元にしています. 文献 4, 6, 10, 11, 14, 16 に関しては,「よくある質問」の個々の項から参照しています.

  1. 藤江哲也: 整数計画法による定式化入門. オペレーションズ・リサーチ,57-4 (2012),pp. 190-197.
    PDF ファイル (藤江先生のご厚意により,文献ファイルの掲載許可を頂いています)
  2. Gurobi Optimization: Gurobi Optimizer Reference Manual Version 6.5. Gurobi Optimization, 2015.
  3. IBM ILOG: IBM ILOG CPLEX Optimization Studio V12.6.3 documentation. IBM ILOG, 2015.
  4. T. Koch, T. Achterberg, E. Andersen, O. Bastert, T. Berthold, R. E. Bixby, E. Danna, G. Gamrath, A. M. Gleixner, S. Heinz, A. Lodi, H. Mittelmann, T. Ralphs, D. Salvagnin, D. E. Steffy, K. Wolter: MIPLIB 2010. Mathematical Programming Computation, 3 (2011), pp. 103-163.
  5. 久保幹雄,J. P. ペドロソ,村松正和,A. レイス: 新しい数理最適化 〜Python 言語と Gurobi で解く〜. 近代科学社,2012.
  6. H. Mittelmann: Benchmarks for Optimization Software.
    http://plato.asu.edu/bench.html
  7. 宮代隆平,松井知己: ここまで解ける整数計画. システム/制御/情報,50-9 (2006), pp. 363-368.
    (英題:R. Miyashiro, T. Matsui: Recent Progress in Integer Programming. Systems, Control and Information, 50-9 (2006), pp. 363-368.)
    PDF ファイル
  8. 宮代隆平: ここまで解ける整数計画―近年の発展―. 第20回RAMPシンポジウム論文集 (2008),日本オペレーションズ・リサーチ学会,pp. 1-21.
  9. 宮代隆平: 整数計画ソルバー入門. オペレーションズ・リサーチ,57-4 (2012),pp. 183-189.
    PDF ファイル
  10. NEOS Server: NEOS Server for Optimization. University of Wisconsin-Madison, 2016.
    http://www.neos-server.org/neos/
  11. E. Rothberg: An Evolutionary Algorithm for Polishing Mixed Integer Programming Solutions. INFORMS Journal on Computing, 19 (2007), pp. 534-541.
  12. H. P. Williams: Model Building in Mathematical Programming (5th edition). Wiley, 2013.
    (第 3 版の訳書は『H. P. ウイリアムス著,小林英三訳: 数理計画モデルの作成法.産業図書,1995』です)
  13. Zuse Institute Berlin: SCIP (Version 3.2.1). ZUSE Institute Berlin, 2016.
    http://scip.zib.de/  http://scip.zib.de/doc/html/
  14. H. D. Sherali, J. C. Smith: An Improved Linearization Strategy for Zero-one Quadratic Programming Problems. Optimization Letters, 1 (2007), pp. 33-47.
  15. 藤江哲也: はじめよう整数計画法. チュートリアル講演,日本オペレーションズ・リサーチ学会 2014年春季研究発表会,2014.
    PDF ファイル (藤江先生のご厚意により,スライドの掲載許可を頂いています)
  16. E. Balas: Disjunctive Programming. 50 Years of Integer Programming 1958-2008, Chapter 10, pp. 283-340, Springer, 2010.

よくある質問

前書き

 整数計画ソルバーに関する,よくある質問とそれについての(とりあえずの)対処方法を書きました. ここに書かれている方法やテクニックの効果は,扱う問題の性質に大きく依存するため,万能の策は無いことにご注意ください. なお,あるソルバー上で特定の機能を紹介している場合,記載していないソルバーにその機能が無いことを意味するものではありません. 情報が特定のソルバーに偏っているのは,単に筆者のソルバー使用経験の差によるもので,他にも多数のソルバーがあります. 個々のソルバーに関する記載については [CPLEX] [Gurobi] [SCIP] というマークをつけました.[CPLEX] は IBM ILOG CPLEX 12.6.3(参考文献 3),[Gurobi] は Gurobi Optimizer 6.5(参考文献 2),[SCIP] は SCIP 3.2.1(参考文献 13)における情報です.

 下記の「よくある質問」では,基本的に「解きたい問題を LP ファイルとして作成し,それを各ソルバーのコマンドラインインターフェース(CLI)に入力して使う方法」を念頭においています([CPLEX]: Interactive Optimizer, [Gurobi]: Interactive Shell, [SCIP]: コマンドライン). CLI と LP ファイルの組合せはソルバーを使う最も単純な方法ですが,これだけでもかなりのことができます. 記載したパラメータ名などは各ソルバーの CLI に準拠しているので,API を介して使うなど他の方法の時には,記載したパラメータ名でマニュアルを検索してください.

目次

  1. ソルバーの入手,問題の記述,基本的なソルバーの操作
    1. ソルバーを入手したい
    2. 問題をソルバーに入力するためには
    3. ソルバーおよび LP ファイルは準備ができた.今すぐ解きたい
  2. 問題を解く際にエラーが出る
    1. 制約式が長すぎて,一行に入らない. または general, binary 宣言の後に一行に収まらない
    2. LP ファイルの読み込みでエラーが出る
    3. 制約式 5 x + y = 7 を表すのに,LP ファイルで a x + y = 7 および a = 5 (または a * x + y = 7 および a = 5) と書いたらエラーになった
    4. 分枝限定法の途中でメモリが足りなくなる
    5. 数値破綻を起こしてエラーになる
    6. 目的関数または制約式に 2 次の項を書いたがエラーになった
  3. 解いてみたが結果がおかしい
    1. 解に値が表示されない変数がある
    2. x < 7 という制約式を入れたのに,計算すると x が 7 の解が出る
    3. LP ファイルを作ったら,勝手に非負変数になっている.マイナスの値を取りうる変数(自由変数)を作りたい
    4. 解けるには解けたが,意図した問題として読み込まれていないようだ
    5. 自分で LP ファイルを生成したが,許容解があるはずの問題なのに不能 (infeasible) になる
    6. 別のソルバーで解くと最適解が違う
    7. 整数変数なのに,0.000001 または 0.999999 のような解が出る
  4. LP ファイルについて
    1. LP ファイルの詳細な文法が知りたい
    2. 目的関数が無い問題を扱いたい
    3. LP ファイルで,シグマ記号や配列に相当するものを用いたい
    4. 巨大な LP ファイルをどうやって生成すればよいか
    5. LP ファイルを自動的に整形したい
    6. MPS ファイルとは何か.MPS ファイルと LP ファイルを変換したい
    7. LP ファイルを MPS ファイルに変換したら,目的関数値がマイナス 1 倍になった
    8. LP ファイルで,2 次の目的関数を表したい
    9. LP ファイルで,2 次の制約式を表したい
    10. LP ファイルに書く変数や制約式の順番を変えたら計算時間が変わった!
  5. ソルバーの調整と計算速度について
    1. 最小化問題でなかなか下界が上がらない. 最大化問題でなかなか上界が下がらない
    2. 最適解にこだわらないので,なるべく高速に質の良い解がほしい
    3. 分枝限定法の計算時間を制限して,自動で停止するようにしたい
    4. 許容解を与えた状態で分枝限定法をスタートしたい
    5. ソルバーをヒューリスティクスな箱として使いたい
    6. 分枝順序を指定したい
    7. 並列分枝限定法でスレッド数を指定したい
    8. 並列分枝限定法において,スレッド数を増やしたら遅くなってしまった
    9. ソルバーのオプション A のみをオンにしたら計算が速くなり,オプション B のみをオンにしたら計算が速くなったので,オプション A と B を両方オンにしたところ計算が遅くなってしまった
    10. 計算を一度中断してから再開したら,中断しない場合と計算過程が異なった
  6. ソルバーをもっと便利に使いたい
    1. ソルバーが前処理をした LP ファイルを見たい
    2. どのように分枝限定法が進んでいるかを詳細に観察したい
    3. 整数変数の値が異なる最適解の個数を数えたい
    4. ログファイルの出力先を変更したい
    5. 複数の問題を自動的に解かせたい
    6. 複数の問題間で情報をやりとりしたい.他のプログラムと連携したい
    7. [CPLEX] 暫定解が得られたときの経過時間を自動的に記録したい
    8. [CPLEX] 計算を中断することなく,暫定解そのものを自動的に記録したい
  7. 定式化について
    1. 現場では使えないような答えが出てくる
    2. 線形式で書けないと思われる制約条件または目的関数がある
    3. 0-1 変数 x, y に対して,「z = x * y」に対応する 0-1 変数 z を使いたい
    4. 制約式を他の変数に応じてオン・オフしたい.「××ならば○○」というような制約式が書きたい
    5. 変数の個数が少ない問題なのに解けない.変数が少ない定式化に変えたら遅くなった
  8. その他の情報
    1. 整数計画問題のベンチマーク問題集が知りたい
    2. 商用ソルバーと非商用ソルバーは,計算時間がどの程度異なるのか
    3. どの商用ソルバーが速いのか
    4. 商用ソルバーを試してみたい

  1. ソルバーの入手,問題の記述,基本的なソルバーの操作

ここでは,非商用ソルバーの入手から,ソルバーの簡単な操作までを紹介します. 参考文献 9 にも,一通りの流れがまとめて書いてありますので参考にしてください.
  1. ソルバーを入手したい
     アカデミック環境に属している方の場合は,まずは非商用ソルバー SCIP を試してみましょう. 他にも各種のソルバーはありますが,とりあえずは SCIP からスタートするのがお手軽かと思われます. SCIP(参考文献 13)のダウンロードページ( http://scip.zib.de/ )から,手持ちの計算機環境にあった,なるべく新しいバージョンのファイルをダウンロードします(よくわからない場合は,Binaries と書いてある中から自分の OS にあったものを選ぶとよいでしょう).なおバイナリが動かない場合は,SCIP のバージョンを落とすと動作する場合があります. SCIP は,2016 年時点で,非商用では最も高速なソルバーの一つです.(ただし現時点で,アカデミックユーザー向けの無償ライセンスが存在する,SCIP より高速な商用ソルバーもいくつか存在します.)
     アカデミック環境ではない場合,SCIP は無償ではありません.代替手段として,NEOS サーバーにおける商用ソルバーの利用などがあります.参考文献 9 および 参考文献 10 を参照してください.
  2. 問題をソルバーに入力するためには
     いろいろな方法がありますが,最初は LP ファイルを利用するのが簡単だと思われます. LP ファイルとは,数理計画問題を表すファイル形式の一種で,拡張子が .lp のテキストファイルです. 数式をほぼそのままテキストにした形になっています. LP ファイルは,本ページで特に詳しく紹介してある CPLEX,Gurobi,SCIP のいずれのソルバーにおいても使用可能で,他にも対応しているソルバーがいくつか存在します. LP ファイルの例を以下に載せます. 簡単な文法については,参考文献 9 を参照してください.
    \ LP ファイルのサンプル
    \ コメントは \ の後ろが一行コメントになります
    
    minimize                      \ minimize は予約語.最大化の場合は maximize
    - 3 x + 4.5 y - 2 z(1) + f    \ 目的関数(複数行になってもよい)
    
    subject to                    \ subject to は予約語.ここから後ろに制約式
    c1: - g(1,1) + g(1,2) <= 5    \ 制約式には先頭に名前をつけられる(名前+コロン)
    c2: 3 g(1,1) - 7 g(1,2)       \ 順に c1, c2, ... と番号を振っておくとよい
        + z(2) >= -10
    c3: 2 f - g(1,1)              \ 制約式は複数行にまたがってもよい
        = 6                       \ ただし比較演算子と右辺定数項は同じ行に書く
    c4: + 1 x + 0.5 y = -4.6      \ 先頭の + や係数の 1 はあってもよい
    
    bounds                        \ bounds は予約語.ここから自由変数の宣言などを行う
    x free                        \ 一行に一つの変数,それに続けて free とすると,
    g(1,1) free                   \ その変数は自由変数になる
                                  \ free 宣言をしない変数は非負条件が課される
    
    general                       \ general は予約語.整数変数にする変数を書く
    g(1,1) g(1,2)                 \ free 宣言をしていなければ自動的に非負条件がつくことに注意
                                  \ この場合,g(1,2) は非負の整数変数
    
    binary                        \ binary は予約語.0-1 変数にする変数を書く
    z(1)                          \ この場合,z(1) と z(2) は 0-1 変数
    z(2)                          \ general, binary 宣言とも複数行に渡って構わない
    
    end                           \ end は予約語.ファイルの最後に書く
    
  3. ソルバーおよび LP ファイルは準備ができた.今すぐ解きたい
     LP ファイルの名前をここでは仮に test1.lp とします.以下のコマンドで,問題の読み込み,計算の実行,最適解の表示ができます.
目次へ戻る
  1. 問題を解く際にエラーが出る

ソルバーで問題を解く際にエラーが出る場合の対処方法です.
  1. 制約式が長すぎて,一行に入らない. または general, binary 宣言の後に一行に収まらない
     一行に収める必要はありません. LP ファイルの一行の文字数があまりに多すぎると,ソルバーによっては切り捨ててしまいますので適宜改行が必要です. 予約語や変数名の途中でなければ,一つの制約式の途中で改行して構いません(ただし,比較演算子と右辺項は同じ行に書きます). 一行に変数が 1 個しかないような縦長の LP ファイルでも,問題ありません(LP ファイルの整形 はソルバーで行えます).
  2. LP ファイルの読み込みでエラーが出る
     まずは,予約語(minimize 等)のスペルミスが無いか確認してください. 大部分の予約語は基本的に新しい行から始め,その後ろで改行します. 線形制約式を書くのに [ ] や / や * などを使っていないでしょうか(これらの記号は 2 次項を表すのに使います). 定数係数と変数の積は,スペースを使って表します. また,e や E は指数表記にも使われるため,変数名のつけ方に注意しましょう.
  3. 制約式 5 x + y = 7 を表すのに,LP ファイルで a x + y = 7 および a = 5 (または a * x + y = 7 および a = 5) と書いたらエラーになった
     a が変数とみなされて,制約式に変数の積が含まれてしまうためです. LP ファイルでは,定数係数は数字を直接書き,その後ろにスペースを空けて係る変数を置きます. ただし,定数を変数にしても制約式が線形になるままなら,定数を変数に置きかえて書いておくことは可能です. 例えば,制約式 5 x + y = 7 を LP ファイルで 5 x + y - b = 0 および b = 7 と書いても,変数の積にはなっていないので線形制約式とみなされます. 賢いソルバーならば,値が固定された変数は前処理で除去してしまうため,実際の効率も変わりありません.
  4. 分枝限定法の途中でメモリが足りなくなる
     問題のサイズがそれほど大きくないのにメモリ不足になる場合は,問題の性質もしくは定式化(あるいはその両方)があまり良くないことを示唆しています. 可能ならば良い定式化に変えるのが望ましいですが,とりあえずソルバーのオプションで対策をとることはできます. なお,分枝限定法で数 GB のメモリを食いつぶしているような場合には,計算を続けるとすぐにその倍のメモリを消費してしまうことも多く,メモリを多少増設してもあまり効果がないことがあります.
  5. 数値破綻を起こしてエラーになる
     非常に大きな係数を持つ制約式が混在する問題など,数値的に不安定になるケースがいくつかあります. 特に,制約式に 2 次項を含む問題は数値的に不安定になりがちです. このような場合,制約式を前もってスケーリングしておくと良い結果になることもあります.
  6. 目的関数または制約式に 2 次の項を書いたがエラーになった
     いくつかの例外を除いて,目的関数は最小化問題の場合には凸 2 次関数,最大化問題の場合には凹 2 次関数でなくてはなりません. さらに,制約式の場合は整数条件を除いた許容領域が凸であることが必要です. また 2 次項がある場合には,目的関数か制約式かで LP ファイルの書き方が若干変わります. 「LP ファイルで,2 次の目的関数を表したい」 「LP ファイルで,2 次の制約式を表したい」 の項も参照してください.
     ただし,0-1 変数の積に関しては,特別な前処理を施して任意の形の 2 次項が扱えるソルバーがあるようです. 『0-1 変数 x, y に対して,「z = x * y」に対応する 0-1 変数 z を使いたい』も参考にしてください.
目次へ戻る
  1. 解いてみたが結果がおかしい

問題は解けたが,どうも結果が変だというときにはこちらを参考にしてください.
  1. 解に値が表示されない変数がある
     大部分のソルバーで,値が 0 の変数は表示されません(大規模な最適化問題の解では,変数の値のうちほとんどが 0 であることが多いため).
  2. x < 7 という制約式を入れたのに,計算すると x が 7 の解が出る
     LP ファイルでは,等号無しの不等号は,等号付きの不等号と同じ意味になります.
  3. LP ファイルを作ったら,勝手に非負変数になっている.マイナスの値を取りうる変数(自由変数)を作りたい
     LP ファイルでは,定義した変数はデフォルトで非負条件が課されています. これを取り除くには,free 宣言を用います. 参考文献 9 を参照してください.
  4. 解けるには解けたが,意図した問題として読み込まれていないようだ
     意図した通りの問題になっていないと思われる場合は,ソルバーに読み込ませた LP ファイルを一度書き出させると,問題が正しいかどうか確かめられます.以下,LP ファイルの名前を仮に test1.lp とします.
  5. 自分で LP ファイルを生成したが,許容解があるはずの問題なのに不能 (infeasible) になる
     最近のソルバーには,互いに相反する最小の制約集合を出力する機能がついていることがあります. この機能は,最適化問題が不能(実行不能,infeasible)な時に策を検討するだけでなく, LP ファイル生成のバグを取るのにもとても便利です. ただし,問題サイズを小さくしないと計算時間がかかるため,なるべく規模の小さな問題からテストするのがよいでしょう.
  6. 別のソルバーで解くと最適解が違う
     最適解が複数存在する場合,解が異なることはありえます. 最適値そのものが違っている場合は,おそらく分枝限定法を終了させる判定条件の問題です.
  7. 整数変数なのに,0.000001 または 0.999999 のような解が出る
     まずは,得られた解を整数に丸めてみて,許容解がきちんと得られているかどうかを確認しましょう. 次に,big-M 法で巨大な定数を使っていないか確認してください. big-M 法で必要以上に大きな定数を使うことは,数値安定性および計算速度を損ねます.
目次へ戻る
  1. LP ファイルについて

LP ファイルについての,より細かい情報です.
  1. LP ファイルの詳細な文法が知りたい
     LP ファイルには,統一されたフォーマットが存在せず,ソルバーごとに独自の拡張がされています. 本ページおよび 参考文献 9 では,多くの環境で扱えると思われる,CPLEX で用いられている LP ファイル形式の一部分をもとに記述しています. ソルバーごとに定められている LP ファイルの詳細な文法は,以下を参照してください.
  2. 目的関数が無い問題を扱いたい
     minimize(あるいは maximize)の次の行に subject to として制約式を書き始めてください.
    ただし,目的関数が無い問題でも,適当な目的関数を設定してやることにより計算が高速になることがあります(遅くなることもあります). 例えば,変数の出現した順に重みの係数を 1, 2, ... として目的関数に入れてやる等です.
  3. LP ファイルで,シグマ記号や配列に相当するものを用いたい
     LP ファイルにそのような機能はないため,1000 個の変数の和は(適宜改行しながら)ベタに書くことになります. また x(1) と書いても,x(2) とは特に関係がありませんし,x2)))) というような変数も可能です. もちろん,人間が変数の意味を理解しやすいように,x(1), y(3,4), z_7_5_6 などと配列風に書くことは推奨されます. (ただし,[ ] は LP ファイルで 2 次式を表す際の記号のため,用いることができません.)
  4. 巨大な LP ファイルをどうやって生成すればよいか
     大きく分けて,以下の 3 つの方法があります: 「プログラミング言語で LP ファイルを生成する」 「数理計画モデリングツールを使う」 「ソルバーに準備されている API などで,(LP ファイルを介さず)ダイレクトに問題生成および求解を行う」. それぞれの利点と欠点は,参考文献 9 の 5 章を参照してください.
  5. LP ファイルを自動的に整形したい
     LP ファイルを一度ソルバーに読み込ませて,それから書き出すときれいに整形してくれます. 以下,整形したい LP ファイルの名前を test1.lp とします.
  6. MPS ファイルとは何か.MPS ファイルと LP ファイルを変換したい
     MPS ファイルとは,数理計画問題を表すファイル形式の一種です. テキストファイルなのですが,人間の目ではあまり読みやすくはありません. ベンチマーク問題などは MPS 形式でアップロードされていることも多いです.
  7. LP ファイルを MPS ファイルに変換したら,目的関数値がマイナス 1 倍になった
     いくつかのソルバーでは,最大化問題の LP ファイルを MPS ファイルに変換すると,係数をマイナス 1 倍した最小化問題に置き換えるようです.
  8. LP ファイルで,2 次の目的関数を表したい
     最小化問題の場合に凸 2 次目的関数,最大化問題の場合に凹 2 次目的関数が直接扱えるソルバーがあります.
     目的関数において,線形項を先に書き,それに続いて 2 次項を + [ 2 x^2 - 4 x * y + 9 y^2 ] /2 のように書きます. 変数の 2 乗は ^2 を,クロス項には * を使います. また,係数は 2 倍して書き,2 次項の全体を [ ] /2 でくくります([ ] とそれより内側はスペースで区切る).
  9. LP ファイルで,2 次の制約式を表したい
     凸 2 次制約,2 次錐制約が直接扱えるソルバーがあります.
    制約式における 2 次項は [ x^2 - 2 x * y + 7 y^2 ] <= 58 のように書きます([ ] とそれより内側はスペースで区切る). 変数の 2 乗は ^2 を,クロス項には * を使います. 目的関数における 2 次項との違いは,係数を 2 倍して /2 する必要がないということです.
  10. LP ファイルに書く変数や制約式の順番を変えたら計算時間が変わった!
     ソルバーは分枝限定法の中で分枝順序を様々な情報から決定していますが, 最終的に優先度が等しい場合には何らかの順序をつける必要があるため,分枝順序および計算時間が変数や制約式を記述した順番に依存することがあります. このあたりの情報は,参考文献 4 に詳しいです.
目次へ戻る
  1. ソルバーの調整と計算速度について

計算速度に関係する部分での,ソルバーの調整についてです.
  1. 最小化問題でなかなか下界が上がらない. 最大化問題でなかなか上界が下がらない
     定式化が良くない可能性もありますが,とりあえずソルバーのパラメータを調整してみる価値はあると思われます.
  2. 最適解にこだわらないので,なるべく高速に質の良い解がほしい
     ソルバーのパラメータを調整するのが手っ取り早いと思われます.
  3. 分枝限定法の計算時間を制限して,自動で停止するようにしたい
     以下のコマンドで,分枝限定法を 10000 秒で終了させられます. 数字を変えることにより,秒数を自由に設定できます.
  4. 許容解を与えた状態で分枝限定法をスタートしたい
     (質の良い)許容解を与えることにより,分枝限定法の高速化をねらいます. 特に,許容解が見つかりにくい問題では計算時間の短縮が期待できます.
  5. ソルバーをヒューリスティクスな箱として使いたい
     上記の「最適解にこだわらないので,なるべく高速に質の良い解がほしい」 「分枝限定法の計算時間を制限して,自動で停止するようにしたい」 「許容解を与えた状態で分枝限定法をスタートしたい」を組み合わせて使うと良いと思われます.
  6. 分枝順序を指定したい
     最近のソルバーはかなり賢くなっているので,デフォルトの分枝順序はかなり高速です. 手作業による分枝順序の調整に多くの時間を掛けることはあまりおすすめしません. ただし,特定の変数を固定すると問題が著しく小さくなるなど,問題構造を詳しく知っている場合には分枝順序の手動指定が有効な場合もあります.
  7. 並列分枝限定法でスレッド数を指定したい
     並列分枝限定法が実装されているソルバーでは,マルチコア CPU の利点を生かすことができます. あるいは,他のタスクの邪魔をしないように,スレッド数を減らすことも可能です.
  8. 並列分枝限定法において,スレッド数を増やしたら遅くなってしまった
     スレッド数を増やしても遅くなる場合はあります.参考文献 4 の図 4 が詳しいです. ですが,例えば 1 スレッドと 16 スレッドくらいだと,それなりに違いが出てくるようです. 「スレッド数を指定したい」の項も参照してください.
  9. ソルバーのオプション A のみをオンにしたら計算が速くなり,オプション B のみをオンにしたら計算が速くなったので,オプション A と B を両方オンにしたところ計算が遅くなってしまった
     そういうことはしばしばあります.
  10. 計算を一度中断してから再開したら,中断しない場合と計算過程が異なった
     ソルバーによっては,そういうことがあります.
目次へ戻る
  1. ソルバーをもっと便利に使いたい

ソルバーの便利な機能の紹介をします.
  1. ソルバーが前処理をした LP ファイルを見たい
     いくつかのソルバーでは,ソルバーが前処理した後の LP ファイルを見ることができます.
  2. どのように分枝限定法が進んでいるかを詳細に観察したい
     分枝限定法の可視化を行う際などは,ノード間の関係が必要になります.
  3. 整数変数の値が異なる最適解の個数を数えたい
     原理的には可能です.ですが,最適解の個数は,問題によっては非常に多くなりえます. 特に,変数間に対称性がある場合には,容易に非現実的な数になります(事実上列挙しきれない). したがって,小さな問題から試すのが得策です.
  4. ログファイルの出力先を変更したい
     複数の問題を解く場合には,ログファイルを分けておくと便利です.
  5. 複数の問題を自動的に解かせたい
     いくつかの方法がありますが,とりあえず OS のコマンドライン(Windows の場合はコマンドプロンプト)を用いて制御する方法を紹介します.
  6. 複数の問題間で情報をやりとりしたい.他のプログラムと連携したい
     LP ファイルをコマンドライン・インターフェースで解く方法は,最も単純な方法です. 列生成法など,複数の問題の間で情報をやりとりする必要がある場合には,ソルバーの API などを用いるのが得策です. 各ソルバーのマニュアルおよびサンプルファイルを参照してください.
  7. [CPLEX] 暫定解が得られたときの経過時間を自動的に記録したい
     CPLEX 12.5 から簡単になっています. Interactive Optimizer では,set mip display 3(あるいは set mip display 4)として分枝限定法を実行してください.
  8. [CPLEX] 計算を中断することなく,暫定解そのものを自動的に記録したい
     Interactive Optimizer では,set output intsolfileprefix test として分枝限定法を実行してください(ここで test は出力されるファイル名なので違う名前でも構いません). 見つかった暫定解の順序で test-00001.sol, test-00002.sol, ... と,解の情報を保存したファイルが出力されます. これらのファイルは xml ファイルで,テキストとして中味を見れば解がわかるようになっています.
目次へ戻る
  1. 定式化について

定式化に関して,よくある質問を記載します.
  1. 現場では使えないような答えが出てくる
     出てきた解が記述した制約条件を全て満たしているならば,ソルバーや整数計画法自体の問題というよりは,現実の制約条件が全て制約式として表現されていないことによるものです. 人間が暗黙のうちに仮定しているが,明示的に書いていない制約式はないかどうかチェックしてください.
  2. 線形式で書けないと思われる制約条件または目的関数がある
     絶対値や max 演算子など,一見して線形式で表せなさそうな場合でも,補助変数などを導入して定式化できることがあります. 参考文献 1 に,日本語でよくまとまった情報があります.
  3. 0-1 変数 x, y に対して,「z = x * y」に対応する 0-1 変数 z を使いたい
     z >= x + y - 1, z <= x, z <= y の 3 本の不等式および x, y, z に関する 0-1 制約により表現できます(他の書き方もあります.参考文献 14 などを参照してください). この種の定式化のテクニックは,参考文献 1 にまとめられています.
     一方で,0-1 変数の場合には,x * y という表現を直接受けつけることのできるソルバーもあるようです. しかし,緩和問題が緩くなるような変形を用いて x * y を扱えるようにしていることが多いため,ソルバーが受けつけているとしても,上記の不等式 3 本による表現を試してみる価値はあります.
  4. 制約式を他の変数に応じてオン・オフしたい.「××ならば○○」というような制約式が書きたい
     big-M 法と呼ばれる方法を使います. 例えば,0-1 変数 z に対して,非負の連続変数 x を,z = 0 の時に「x = 0」という制約式を入れ,z = 1 の時にその制約式を無効にしたいとします. 非負の連続変数 x の上界が正の(大きな)定数 M だと何らかの理由でわかっている場合,x <= M * z とすることで,上記を達成することができます. なお,定式化の際に,M の値は許される範囲でなるべく小さくした方が計算が高速になります. 詳しくは 参考文献 1 をお読みください. ただし,big-M 法を 1 つの問題の中で多用することは,計算速度を落としますので,big-M 法を使わないで定式化できる場合は,そちらをおすすめします.
     また,Special Ordered Set type 1 (SOS type 1) 制約が使えるソルバーの場合,x <= M * z と書くかわりに,SOS type 1 制約で x と z' をメンバーに入れることで,同様の制約となります:ここで z' は z + z' = 1 となる 0-1 変数です.  なお,「A または B」というような制約式を書きたい場合には,big-M 法ではなく disjunctive constraint(離接制約)を用いて定式化する方法もあります. 離接制約を扱うような問題は, disjunctive programming と呼ばれています. 詳しくは 参考文献 16 をお読みください.
  5. 変数の個数が少ない問題なのに解けない.変数が少ない定式化に変えたら遅くなった
     変数が少ない(あるいは制約式が少ない)問題あるいは定式化が,必ずしも計算時間が短いわけではありません. どのような定式化が良い定式化(≒高速に解ける定式化)になるかはケースバイケースですが,一般的には「線形緩和問題の最適値と整数計画問題の最適値のギャップが小さい」定式化が良い定式化になることが多いです. ただしベストを尽くしても,あまりにも変数が多い問題や整数計画法に向いていない問題は解くのが難しいのも事実です.
    例:小さいのに難しい問題の LP ファイルMIPLIB 2003markshare1
目次へ戻る
  1. その他の情報

その他,役に立つリンク先などの情報をまとめておきます.
  1. 整数計画問題のベンチマーク問題集が知りたい
     いくつかありますが,有名なのは MIPLIB ( http://miplib.zib.de/ )です. 現時点では MIPLIB 2010 ( http://miplib.zib.de/miplib2010.php )が最新バージョンです. 少し前までは MIPLIB 2003 ( http://miplib.zib.de/miplib2003/index.php )がよく用いられていました.
  2. 商用ソルバーと非商用ソルバーは,計算時間がどの程度異なるのか
     現時点では,最高速の商用ソルバーと最高速の非商用ソルバーとを比較すると,前者の方がかなり高速です. SCIP のホームページ ( http://scip.zib.de/ )によると,1 時間以内で解ける簡単な問題で,5 倍以上の速度差があるようです. さらに,難しい問題ほど,ソルバーの性能差が顕著に現れます(数分と数時間,あるいは数時間と数日というようなケースも稀ではありません).
     また,商用ソルバーはバージョンアップ時に大幅に性能が向上していることが多いため,なるべく最新バージョンの使用をおすすめします.
  3. どの商用ソルバーが速いのか
     問題によってソルバー A の方が速かったり,ソルバー B の方が速かったりということがあります. なので,どのソルバーが速いのかというのは統計的に見るしかないことにご注意ください. ソルバー別のベンチマーク結果については,Hans Mittelmann のベンチマークサイト( http://plato.asu.edu/bench.html )が有名です.
  4. 商用ソルバーを試してみたい
     いくつかの商用ソルバーのベンダーでは,各種トライアルライセンスを準備しています. さらにアカデミックユーザーの場合は,無償または格安ライセンスが提供されていることも多いです.
     また,NEOS サーバー( http://www.neos-server.org/neos/ )を用いるとアカデミックユーザーかどうかにかかわらず,無償で商用ソルバーを使うことができます (LP ファイルを準備すれば CPLEX を,MPS ファイルに変換すれば Gurobi Optimizer も使えます). ただし,問題の規模や計算時間に制限があります. 詳しくは,参考文献 9 を参照してください.
目次へ戻る
このページのトップへ戻る  トップページへ戻る