Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                

整数計画法メモ

トップページへ戻る

本ページのURLが https://www.tuat.ac.jp/~miya/ipmemo.html から https://web.tuat.ac.jp/~miya/ipmemo.html へ変更になりました． それに応じて，本ページからリンクされているダウンロード可能なファイルについても，URLが変更になっています．

はじめに

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

おことわり

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

更新履歴

　このページは2013年4月に公開し，その後も改訂を行ってきましたが，2020年12月から更新履歴をつけるようにしました． なお，誤字脱字やその他の微細な訂正は更新履歴に記しません．

2025年2月 2024年9月 2024年8月 2024年5月 2024年3月 2024年1月 2023年8月 2023年1月 2022年8月 2022年5月 2022年2月 2021年11月 2021年9月 2021年8月 2021年3月 2020年12月
宮代 隆平（東京農工大学 工学部 知能情報システム工学科）

参考文献

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

  1. 藤江哲也： 整数計画法による定式化入門． オペレーションズ・リサーチ，57-4 (2012)，pp. 190-197.
    PDF ファイル （藤江先生のご厚意により，文献ファイルの掲載許可を頂いています）
  2. Gurobi Optimization: Gurobi Optimizer Reference Manual Version 10.0. Gurobi Optimization, 2022.
  3. IBM ILOG: IBM ILOG CPLEX Optimization Studio 22.1.0 documentation. IBM ILOG, 2022.
  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.
    doi:10.1007/s12532-011-0025-9
  5. 久保幹雄，J. P. ペドロソ，村松正和，A. レイス： 新しい数理最適化 〜Python 言語と Gurobi で解く〜． 近代科学社，2012． ISBN 978-4-7649-0433-0
  6. H. Mittelmann: Benchmarks for Optimization Software.
    https://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.）
    doi:10.11509/isciesci.50.9_363　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, 2025.
    https://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.
    doi:10.1287/ijoc.1060.0189
  12. H. P. Williams: Model Building in Mathematical Programming (5th edition). Wiley, 2013. ISBN 978-1-118-44333-0
    （第 3 版の訳書は『H. P. ウイリアムス著，小林英三訳： 数理計画モデルの作成法．産業図書，1995，ISBN 978-4-782-84601-8』です）
  13. Zuse Institute Berlin: SCIP (Version 9.2.1). Zuse Institute Berlin, 2025.
    https://www.scipopt.org/　 https://www.scipopt.org/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.
    doi:10.1007/s11590-006-0019-0
  15. 藤江哲也： はじめよう整数計画法． チュートリアル講演，日本オペレーションズ・リサーチ学会 2014年春季研究発表会，2014．
    PDF ファイル （藤江先生のご厚意により，スライドの掲載許可を頂いています）
  16. E. Balas: Disjunctive Programming. 50 Years of Integer Programming 1958-2008, Chapter 10, pp. 283-340, Springer, 2010.
    doi:10.1007/978-3-540-68279-0_10
  17. 高野祐一： ZIMPL言語とSCIPによる数理最適化． 専修ネットワーク＆インフォメーション， 24 (2016)，pp. 9-14.
    doi:10.34360/00005129
  18. 宮代隆平： 整数最適化アプローチへの入門． チュートリアル講演，電子情報通信学会 2019年総合大会，2019．
    PDF ファイル
  19. A. Gleixner, G. Hendel, G. Gamrath, T. Achterberg, M. Bastubbe, T. Berthold, P. Christophel, K. Jarck, T. Koch, J. Linderoth, M. Lübbecke, H. D. Mittelmann, D. Ozyurt, T. K. Ralphs, D. Salvagnin, Y. Shinano: MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library. Mathematical Programming Computation, 13 (2021), pp. 443-490.
    doi:10.1007/s12532-020-00194-3
  20. O. Günlük, J. Linderoth: Perspective Reformulations of Mixed Integer Nonlinear Programs with Indicator Variables. Mathematical Programming, Series B, 124 (2010), pp. 183-205.
    doi:10.1007/s10107-010-0360-z
  21. E. Balas: Disjunctive Programming. Springer, 2018. ISBN 978-3-030-00147-6
    doi:10.1007/978-3-030-00148-3
  22. MOSEK: MOSEK Modeling Cookbook 3.3.0.
    https://docs.mosek.com/modeling-cookbook/index.html
  23. 田中大毅： 列挙の方法によるmarket split問題の解法． 日本オペレーションズ・リサーチ学会 2024年春季研究発表会 アブストラクト集，pp. 230-231．

よくある質問

前書き

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

　下記の「よくある質問」では，基本的に「解きたい問題を LP ファイルとして作成し，それを各ソルバーのコマンドラインインターフェース（CLI）に入力して使う方法」を念頭においています（[CPLEX]: Interactive Optimizer, [Gurobi]: Interactive Shell, [SCIP]: コマンドライン）． LP ファイルと CLI の組合せはソルバーを使う最も単純な方法ですが，これだけでもかなりのことができます． ただし，他のプログラムと組み合わせた動的な作業や，列生成法などに代表される分枝限定法の制御を行う場合は，各ソルバーの API を使うことをおすすめします． このあたりについては，「巨大な LP ファイルをどうやって生成すればよいか」も参照してください．

　なお，本ページに記載したパラメータ名などは各ソルバーの CLI に準拠しているので，API を介して使うなど他の方法の時には記載したパラメータ名でマニュアルを検索してください． また，ソルバーのバージョンアップによってパラメータ名などがしばしば変更になりますので，ご注意ください．

目次

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

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

　ここでは，非商用ソルバーの入手から，ソルバーの簡単な操作までを紹介します． 参考文献 9 にも，一通りの流れがまとめて書いてありますので参考にしてください．

  1. ソルバーを入手したい

    　まずは，非商用ソルバー SCIP を試してみましょう． 他にも各種のソルバーはありますが，とりあえずは SCIP からスタートするのがお手軽かと思われます． SCIP は 2023 年末の時点で，非商用では最も高速なソルバーの一つです（商用ソルバーでは SCIP より高速なものも存在します）． さらに，2022年 12 月に公開された SCIP 8.0.3 以降からは Apache 2.0 ライセンス が適用されています． これにより，営利用途においてもライセンスの範囲内で無償利用が可能になっています．
    　SCIP（ 参考文献 13 ）のダウンロードページ（ https://www.scipopt.org/ ）から，手持ちの計算機環境にあったファイルをダウンロードします． なお，Apache 2.0 ライセンスが適用されているのは SCIP 8.0.3 以降ですのでご注意ください．
    　アカデミック環境に所属している方は，NEOS サーバーにおける商用ソルバーの利用も可能です． 「商用ソルバーを試してみたい」を参照してください．

  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 とします． 以下のコマンドで，問題の読み込み，計算の実行，最適解の表示ができます．
    • [CPLEX]　Interactive Optimizer を起動し，「read test1.lp」「optimize」「display solution variable - 」（最後の variable の後ろはスペースを空けてハイフン）とすると画面に解が表示されます． また，cplex.log というファイルに画面出力が保存されています． 「quit」で終了します．
    • [Gurobi]　Interactive Shell を起動し，「m = read("test1.lp")」「m.optimize()」「m.printAttr('x')」とすると画面に解が表示されます（m はモデル名なので違う名前でも構いません）． 「m.write("test1.sol")」とすると test1.sol というファイルに解が出力されます． また，gurobi.log というファイルに画面出力が保存されています． 「quit()」で終了します．
    • [SCIP]　コマンドラインで SCIP を起動し，「read test1.lp」「optimize」「display solution」とすると画面に解が表示されます． また，「write solution test1.sol」とすると test1.sol というファイルに解が出力されます． 「quit」で終了します．

  4. 計算を途中で停止したい

    　難しい整数最適化問題を最後まで解ききれないときに，計算を手動で停止する方法です． あらかじめ計算時間を制限する場合は，「計算時間を制限して，分枝限定法を自動的に停止するようにしたい」を参照してください．
    • [CPLEX][SCIP]　Interactive Optimizer/コマンドラインでは，Ctrl-C で分枝限定法の計算を停止できます． サイズの大きな問題では停止するまでに時間がかかるので，Ctrl-C を連打しないように注意してください． 「optimize」で中断した部分から計算を再開できます．
    • [Gurobi]　Interactive Shell では，Ctrl-C で分枝限定法の計算を停止できます． サイズの大きな問題では停止するまでに時間がかかるので，Ctrl-C を連打しないように注意してください． 「m.optimize()」で中断した部分から計算を再開できます（ここで m は現在扱っているモデル名）．

  5. 問題の読み込み時に注意すること

    　LP ファイルを読み込む際の注意です．
    • [CPLEX]　Interactive Optimizer では，LP ファイル（あるいは MPS ファイルなどの問題ファイル）を read で読み込むと，その前に読み込んでいた問題の情報は消えてしまいます（同一の LP ファイルの再読み込みでも）． 解いた問題の分析は別の問題を読み込む前に行いましょう． 「display problem stats」で現在読み込んでいる問題の情報を表示できます．
    • [Gurobi]　同時に複数のモデルを扱うことができます（ただし，モデル名は異なるものにする必要があります）． 現在扱っているモデルの一覧と，変更されたパラメータについては「models()」で表示できます． なお，扱っているモデルを破棄したい場合は「m.dispose()」あるいは「del m」とします（ここで m は破棄したいモデルの名前）．
    • [SCIP]　コマンドラインでは，LP ファイル（あるいは MPS ファイル）などの問題ファイルを read で読み込むと，それ以前に読み込んでいた問題の情報は消えてしまいます（同一の LP ファイルの再読み込みでも）． 解いた問題の分析は別の問題を読み込む前に行いましょう． 「display statistics」で現在読み込んでいる問題の情報を表示できます．

  6. ソルバーへのコマンド入力について

    　コマンド入力の省略方法についてです．
    • [CPLEX]　Interactive Optimizer では，コマンド入力はソルバーが一意に判断できる範囲で短くできます． 例えば，トップレベルのコマンドには d から始まるものは display しかないので，「display」と入力するのと「d」と入力するのは同じになります． これを用いると，例えば「set mip display 4」というコマンド入力は「s mi d 4」というように簡略化できます（本ページではコマンド名は省略せずに記述します）． 一方で，トップレベルのコマンドで p から始まるものは複数あるので，p だけでは入力が完了しません．
    • [SCIP]　コマンドラインでは，コマンド入力はソルバーが一意に判断できる範囲で短くできます． 例えば，トップレベルのコマンドには d から始まるものは display しかないので，「display」と入力するのと「d」と入力するのは同じになります． これを用いると，例えば「display statistics」というコマンド入力は「d st」というように簡略化できます（本ページではコマンド名は省略せずに記述します）． 一方で，トップレベルのコマンドで c から始まるものは複数あるので，c だけでは入力が完了しません．

  7. ソルバーのヘルプコマンドを表示したい

    　各ソルバーの詳細はマニュアルに記載されていますが，ソルバー上でも簡易ヘルプを参照できます．
    • [CPLEX]　Interactive Optimizer では，「help」でトップレベルのコマンド一覧が表示され，「help コマンド名」でそのコマンドのヘルプが表示されます．
    • [Gurobi]　Interactive Shell では，「help()」でヘルプコマンドのヘルプが表示されます． 「paramHelp("パラメータ名")」でパラメータのヘルプが表示されます．
    • [SCIP]　コマンドラインでは，「help」でトップレベルのコマンド一覧が表示されます．
目次へ戻る

  1. 問題を解く際にエラーが出る

　ソルバーで問題を解く際にエラーが出る場合の対処方法です．

  1. 制約式が長すぎて一行に入らない． または general, binary 宣言の後に一行に収まらない

    　一行に収める必要はありません． LP ファイルの一行の文字数があまりに多すぎると，ソルバーによっては切り捨ててしまいますので適宜改行が必要です． 予約語や変数名の途中でなければ，一つの制約式の途中で改行して構いません（ただし，比較演算子と右辺項は同じ行に書きます）． 一行に変数が 1 個しかないような縦長の LP ファイルでも問題ありません（LP ファイルの整形 はソルバーで行えます）．

  2. LP ファイルの読み込みでエラーが出る

    　まずは，予約語（minimize 等）のスペルミスが無いか確認してください． 大部分の予約語は基本的に新しい行から始め，その後ろで改行します． 線形制約式を書くのに [ ] や / や * などを使っていないでしょうか（これらの記号は二次項を表すのに使います）． 定数係数と変数の積は，スペースを使って表します． また，e や E は 1e4 y などの指数表記にも使われるため，変数名のつけ方に注意しましょう．
    • [CPLEX]　今のところ CPLEX の LP ファイルでは，xx yy という変数（xx と yy の間にスペース）を書くと xxyy という一つの変数として認識されます． しかし他のソルバーとの互換性のためにも，文字列の間にスペースを含む変数は避けた方が無難です．
    • [Gurobi]　今のところ Gurobi の LP ファイルでは，x + y と x+y は違う意味を持ちます． 前者は変数 x と y の和で，後者は x+y という一つの変数に認識されます． また，二次項を表す x * y も，x*y ではなく * の前後にスペースが必要です． 変数や演算子の間のスペースは基本的に省略できません．

  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 のメモリを食いつぶしているような場合には，計算を続けるとすぐにその倍のメモリを消費してしまうことも多く，メモリを多少増設してもあまり効果がないことがあります．
    • [CPLEX]　Interactive Optimizer では，「set workmem 8192」とすると，分枝限定法で使用するメモリを 8192 MB に設定することができます． 数字は MB を単位として自由に設定できます． また，「set emphasis memory yes」と設定することで，メモリを節約することに重点を置いた分枝限定法になります． 「set mip strategy file 2」と設定することで，ノード情報が大きくなった場合はハードディスクに書き込むようにできます． さらに「set mip strategy file 3」とすると，圧縮してハードディスクに保存します．
    • [Gurobi]　Interactive Shell では，「setParam("NodefileStart", 0.5)」と設定することで，ノード情報が 0.5 GB を超えるとハードディスクに書き込むようにできます． 数字は GB を単位として自由に設定できます．

  5. 数値破綻を起こしてエラーになる

    　非常に大きな係数を持つ制約式が混在する問題など，数値的に不安定になるケースがいくつかあります． 特に，制約式に二次項を含む問題は数値的に不安定になりがちです． このような場合，制約式を前もってスケーリングしておくと良い結果になることもあります．
    • [CPLEX]　Interactive Optimizer では，「set emphasis numerical yes」で数値安定性に重点を置いた分枝限定法になります．
    • [Gurobi]　Interactive Shell では，「setParam("NumericFocus", 1)」で数値安定性に重点を置いた分枝限定法になります． さらに数値を 2 あるいは 3 とすることでより数値安定性に重点をおきます（デフォルト値は 0）．
    • [SCIP]　コマンドラインでは，「set emphasis numerics」で数値安定性に重点を置いた分枝限定法になります．
    　また，目的関数が凸二次関数（最大化問題の場合は凹二次関数）のはずなのに，数値誤差の影響で「凸でない」というエラーが出る場合があります． この場合，目的関数の係数を全て整数にスケーリングする，対角項の係数を微小に増加させる，新しい変数と制約式を導入して係数行列を疎にするなどの対策を試してみてください．

  6. 目的関数または制約式に二次項を書いたがエラーになった

    　いくつかの例外を除いて，目的関数は線形関数または凸二次関数（最大化問題の場合には凹二次関数）でなくてはなりません． さらに，制約式の場合は整数条件を除いた許容領域が凸であることが必要です． また二次項がある場合には，目的関数か制約式かで LP ファイルの書き方が若干変わります． 「LP ファイルで，二次の目的関数を表したい」「LP ファイルで，二次の制約式を表したい」 の項も参照してください． なお，0-1 変数の積に関しては，特別な前処理を施して任意の形の二次項が扱えるソルバーがあるようです． 「0-1 変数 x, y に対して，「z = x * y」に対応する 0-1 変数 z を使いたい」も参考にしてください．
    • [CPLEX]　CPLEX 12.6 から，制約式が線形であるような二次最適化問題もしくは整数二次最適化問題については，『最小化問題の場合には凸二次目的関数，最大化問題の場合は凹二次目的関数』以外の目的関数が扱えるようになりました． 普通に解いてみて，"Q in objective is not positive semi-definite." というエラーメッセージが表示された場合，『 』内の条件を満たしていません． 「set optimalitytarget 3」として問題を解き直してください（このオプションは，以前は solutiontarget という名前でした）． ただし，『 』内の条件を満たしている問題と比べるとかなり計算に時間がかかるので注意が必要です．
    • [Gurobi]　Gurobi 9.0 から，『最小化問題の場合には凸二次目的関数，最大化問題の場合は凹二次目的関数』以外の二次の目的関数が扱えるようになりました． また，『制約式に含まれる変数を連続変数とみなした時，許容領域が凸になる二次不等式』以外の二次制約式が扱えるようになりました（例えば，z = x * y というような双線形等式制約が扱えます）． 普通に解いてみて，エラーメッセージが表示された場合，『 』内の条件を満たしていません． 「setParam("NonConvex", 2)」として問題を解き直してください． ただし，『 』内の条件を満たしている問題と比べるとかなり計算に時間がかかるので注意が必要です．
    　また，目的関数が凸二次関数（最大化問題の場合は凹二次関数）のはずなのに，数値誤差の影響で「凸でない」というエラーが出る場合があります． この場合，目的関数の係数を全て整数にスケーリングする，対角項の係数を微小に増加させる，新しい変数と制約式を導入して係数行列を疎にするなどの対策を試してみてください．

  7. [CPLEX]　ILOG CPLEX Optimization Studio が実行できない

    　CPLEX に付属している CPLEX Optimization Studio を使用していて，問題を OPL 言語で正しく記述したにもかかわらず，実行すると「選択を起動できません．また，最近起動されていません」と表示されて進まない，あるいは実行できても「不明なエラー」が出て止まってしまう場合には，デフォルトで「構成1」になっている実行構成の名前を半角英数字に変更してください．
    　または，CPLEX Optimization Studio のインターフェースを全て英語にしてしまう方法があります． Windows の場合は，ショートカットのプロパティのリンク先を "C:\...\oplide.exe" -nl en_US のように直すことで英語版が起動します（-nl en_US は " " の外側に書く）． コマンドラインからの起動の場合は，引数に -nl en_US をつけて起動してください．
目次へ戻る

  1. 解いてみたが結果がおかしい

　問題は解けたが，どうも結果が変だというときにはこちらを参考にしてください．

  1. 解に値が表示されない変数がある

    　大部分のソルバーで，値が 0 の変数は表示されません（大規模な最適化問題の解では，変数の値のうちほとんどが 0 であることが多いため）．

  2. x < 7 という制約式を入れたのに，計算すると x が 7 の解が出る

    　LP ファイルでは，等号無しの不等号は，等号付きの不等号と同じ意味になります．

  3. LP ファイルを作ったら，勝手に非負変数になっている．マイナスの値を取りうる変数（自由変数）を作りたい

    　LP ファイルでは，定義した変数はデフォルトで非負条件が課されています． これを取り除くには，free 宣言を用います． 「問題をソルバーに入力するためには」または 参考文献 9 を参照してください．

  4. 解けるには解けたが，意図した問題として読み込まれていないようだ

    　意図した通りの問題になっていないと思われる場合は，ソルバーに読み込ませた LP ファイルを一度書き出させると，問題が正しいかどうか確かめられます． 以下，LP ファイルの名前を仮に test1.lp とします．
    • [CPLEX]　Interactive Optimizer では，「read test1.lp」「write test2.lp」とすると，test2.lp にソルバーが認識している問題が書き出されます． また，今のところ CPLEX の LP ファイルでは，xx yy という変数（xx と yy の間にスペース）を書くと，xxyy という一つの変数として認識するので注意が必要です． 多くのソルバーではエラーとして処理されますが，互換性のためにも文字列の間にスペースを含む変数は避けた方が無難です．
    • [Gurobi]　Interactive Shell では，「m = read("test1.lp")」「m.write("test2.lp")」とすると test2.lp にソルバーが認識している問題が書き出されます（m はモデル名なので違う名前でも構いません）． また，今のところ Gurobi の LP ファイルでは，x + y と x+y は違う意味を持ちます． 前者は変数 x と y の和で，後者は x+y という一つの変数に認識されます． 変数や演算子の間のスペースは基本的に省略できません．
    • [SCIP]　コマンドラインでは，「read test1.lp」「write problem test2.lp」とすると，test2.lp にソルバーが認識している問題が書き出されます．

  5. 自分で LP ファイルを生成したが，許容解があるはずの問題なのに不能 (infeasible) になる

    　最近のソルバーには，互いに相反する最小の制約集合を出力する機能がついていることがあります． この機能は，最適化問題が不能（実行不能，infeasible）な時に策を検討するだけでなく，LP ファイル生成のバグを取るのにもとても便利です． ただし，問題サイズを小さくしないと計算時間がかかるため，なるべく規模の小さな問題からテストするのがよいでしょう．
    • [CPLEX]　Interactive Optimizer では，問題を解き不能だと出てから「tools conflict」と実行します（このコマンドは，以前はトップレベルの conflict というコマンドでした）． コマンドの処理が終了したら，「display conflict all」で互いに矛盾する制約式などが出力されます．
    • [Gurobi]　Interactive Shell では，問題を解き不能だと出てから，computeIIS メソッドを使います． computeIIS メソッドの処理が終了したら，拡張子が .ilp のファイルを出力することで互いに矛盾する制約式などが出力されます． 例：「m = read("test1.lp")」「m.optimize()」「m.computeIIS()」「m.write("test1.ilp")」

  6. 別のソルバーで解くと最適解が違う

    　最適解が複数存在する場合，解が異なることはありえます． 最適値そのものが違っている場合は，おそらく分枝限定法を終了させる判定条件の問題です．
    • [CPLEX]　Interactive Optimizer では，デフォルトの終了条件が最適性ギャップ 0.0001 (= 0.01%) になっているため，最適値の絶対値が大きな問題では最適解でない解で終了してしまうことがあります． これを避けるには，「set mip tolerances mipgap 0」「set mip tolerances absmipgap 0」と設定します．
    • [Gurobi]　デフォルトの終了条件が最適性ギャップ 0.0001 (= 0.01%) になっているため，最適値の絶対値が大きな問題では最適解でない解で終了してしまうことがあります． これを避けるには，Interactive Shell では「setParam("MIPGap", 0)」「setParam("MIPGapAbs", 0)」と設定します．
    　なお，混合整数二次錐最適化問題 (MISOCO) など，制約式に二次項を含む整数最適化問題は数値誤差に弱く，ソルバーが間違った解を最適解として返してくることがあります． これには決定的な対策はないのですが，可能ならば複数のソルバーなどでチェックするとエラーを減らすことができます．

  7. 整数変数なのに，0.000001 または 0.999999 のような解が出る

    　まずは，得られた解を整数に丸めてみて，許容解がきちんと得られているかどうかを確認しましょう． 次に，big-M 法で巨大な定数を使っていないか確認してください． Big-M 法で必要以上に大きな定数を使うことは，数値安定性および計算速度を損ねます． なお，計算には誤差が含まれますので得られた結果を処理する際には注意が必要です． 例えば，0-1 変数としていても 0.000001 のような値が得られることがあるため，「int 型の 0 と比較する」というような処理は誤った結果を招くことがあります．
    • [CPLEX]　Interactive Optimizer では，「set emphasis numerical yes」で数値安定性に重点を置いた分枝限定法になります． あるいは，「set mip tolerances integrality 0」と設定してみてください．
    • [Gurobi]　Interactive Shell では，「setParam("NumericFocus", 1)」で数値安定性に重点を置いた分枝限定法になります． さらに数値を 2 あるいは 3 とすることでより数値安定性に重点をおきます（デフォルト値は 0）． あるいは，「setParam("IntegralityFocus", 1)」かつ/または「setParam("IntFeasTol", 1e-9)」と設定してみてください．
    • [SCIP]　コマンドラインでは，「set emphasis numerics」で数値安定性に重点を置いた分枝限定法になります．

  8. 分枝限定法を進めたら，最適性ギャップが増えた

    　通常，分枝限定法における相対的な最適性ギャップ（上界と下界の割合）は単調に減少しますが，上界と下界の正負が異なる段階では，上下界が改善されたときに一時的に最適性ギャップの値が増加したように見えることがあります． これは，ソルバーによる最適性ギャップの計算方法に起因するものです． このような段階においては，相対的な最適性ギャップの値は分枝限定法の進行状況の目安としてあまり参考になりません． 絶対的な最適性ギャップ（上界と下界の差）を観察してください．
    　また，最適値が 0 であるような問題の場合，相対的な最適性ギャップは分枝限定法の進行状況の目安としてほとんど役に立ちません． この場合にも，絶対的な最適性ギャップを参考にしてください．

  9. [CPLEX]　ILOG CPLEX Optimization Studio で LP ファイルを生成したが，添字がずれる

    　CPLEX に付属している CPLEX Optimization Studio において OPL 言語で問題を記述し，実行すると LP ファイルを生成するように設定しているとき，配列変数の添字を 1 から始めるようにしていても，LP ファイルでは 0 から始まるようになっている場合があります（そうならない時もあります）． LP ファイルにも問題自体は正しく記述されているのですが，この現象が起きると添字がずれているので人間が解を解釈する際に間違ってしまう可能性があります． この問題が発生した場合は，OPL 言語上で配列変数の添字を 0 から始めるようにし，添字 0 に対応する変数には定数を与えてしまえば添字がずれることはとりあえずなくなります．
目次へ戻る

  1. LP ファイルについて

　LP ファイルについての，より細かい情報です．

  1. LP ファイルの詳細な文法が知りたい

    　LP ファイルには，統一されたフォーマットが存在せず，ソルバーごとに独自の拡張がされています． 本ページおよび 参考文献 9 では，多くの環境で扱えると思われる，CPLEX で用いられている LP ファイル形式の一部分をもとに記述しています． ソルバーごとに定められている LP ファイルの詳細な文法は，以下を参照してください．
    • [CPLEX]　"LP file format" でマニュアルを検索してください． 注意点として，CPLEX の LP ファイルでは，xx yy という変数（xx と yy の間にスペース）を書くと xxyy という一つの変数として認識されます． しかし他のソルバーとの互換性のためにも，文字列の間にスペースを含む変数は避けた方が無難です．
    • [Gurobi]　"LP file format" でマニュアルを検索してください． 注意点として，Gurobi の LP ファイルでは，x + y と x+y は違う意味を持ちます． 前者は変数 x と y の和で，後者は x+y という一つの変数に認識されます． また，二次項を表す x * y も，x*y ではなく * の前後にスペースが必要です． 変数や演算子の間のスペースは基本的に省略できません．

  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 ファイルで二次式を表す際の記号のため用いることができません．）

  4. 巨大な LP ファイルをどうやって生成すればよいか

    　大きく分けて以下の 3 つの方法があります： 「プログラミング言語で LP ファイルを生成する」 「数理最適化モデリングツールを使う」 「ソルバーに準備されている API などで，（LP ファイルを介さず）ダイレクトに問題生成および求解を行う」． それぞれの利点と欠点は以下の通りです．
    　「プログラミング言語で LP ファイルを生成する」： 使い慣れているプログラミング言語でテキストを出力させればよいので，一番お手軽です． 本ページでも，LP ファイル＋各ソルバーの CLI を用いた方法を想定して紹介しています． また，問題を LP ファイルを介して扱うため，あるソルバーから他のソルバーに乗り換えることも容易なのもメリットです． ただしあくまでも LP ファイルベースのため，他の方法と比較するとソルバーの複雑な制御が難しいというデメリットもありますが，問題を独立に解くだけならばこの方法でもほとんど不便はないと思われます．
    　「数理最適化モデリングツールを使う」： メリットは，数式で表現されたモデルからプログラムが作りやすいことです． 例えば，あるモデリング言語では「x1 から x100 までの和が 3 以下」を表現するのに sum(i in 1..100)(x[i]) <= 3 と書くことができるなど，数式からプログラムへ直感的に書き換えが可能となっています． 他にも，よく使うタイプの制約式に対応する予約語が準備されているなど，数学的定式化が完成してからの変換作業が非常に高速に行えることが利点です． ただし，数理最適化モデリングツールを購入し，そこで使用されているモデリング言語を習得する手間がかかります． 汎用のプログラミング言語を覚えるよりは容易ですが，ある程度の時間的・金銭的な初期投資が必要になります． ソルバーによっては，数理最適化モデリングツールが同梱されているものもあります．
    　「ソルバーに準備されている API などで，（LP ファイルを介さず）ダイレクトに問題生成および求解を行う」： 問題ファイルの生成にとどまらず，分枝順序の操作など分枝限定法の高度な制御が可能になるのが一番のメリットとなります． 列生成法など，複数の問題間で情報をやりとりする必要がある場合には，この方法を利用するのが現実的でしょう． ただし API の書式などはソルバーごとに異なるため，別ソルバーへの流用は難しいのも確かです．
    • [CPLEX]　数理最適化モデリングツール CPLEX Optimization Studio が同梱されています（ 参考文献 3 ）． また，C, C++, Java, .NET, Python の API が準備されています．
    • [Gurobi]　Interactive Shell 自体が Python インタープリタになっており，この上からソルバーをプログラムで高度に制御できます． 参考文献 5 にわかりやすい解説およびサンプルプログラムが載っています． また，C, C++, Java, .NET, Python, R の API が準備されています．
    • [SCIP]　数理最適化モデリング言語 ZIMPL が最初から同梱されています． ZIMPL 言語の簡単な文法については，参考文献 17 を参照してください． コマンドラインでは，「read test1.zpl」「write problem test2.lp」とすると，test2.lp に LP ファイルを出力できます（ここで test1.zpl は ZIMPL 言語で作成した問題ファイル）． なお，SCIP はソースコードが全て公開されており，単なるソルバーとしてだけではなく，分枝限定法のフレームワークとして提供されています．

  5. LP ファイルを自動的に整形したい

    　LP ファイルを一度ソルバーに読み込ませて，それから書き出すときれいに整形してくれます． 以下，整形したい LP ファイルの名前を test1.lp とします．
    • [CPLEX]　Interactive Optimizer では，「read test1.lp」「write test2.lp」とすると，test2.lp に整形された LP ファイルが出力されます．
    • [Gurobi]　Interactive Shell では，「m = read("test1.lp")」「m.write("test2.lp")」とすると test2.lp に整形された LP ファイルが出力されます（m はモデル名なので違う名前でも構いません）．
    • [SCIP]　コマンドラインでは，「read test1.lp」「write problem test2.lp」とすると，test2.lp に整形された LP ファイルが出力されます．

  6. MPS ファイルとは何か．MPS ファイルと LP ファイルを変換したい

    　MPS ファイルとは，数理最適化問題を表すファイル形式の一種です． テキストファイルなのですが，人間の目ではあまり読みやすくはありません． ベンチマーク問題などは MPS 形式でアップロードされていることも多いです．
    • [CPLEX]　Interactive Optimizer では，「read test1.mps」「write test2.lp」とすると，MPS ファイルから LP ファイルに変換できます． 「read test3.lp」「write test4.mps」で逆の変換ができます．
    • [Gurobi]　Interactive Shell では，「m = read("test1.mps")」「m.write("test2.lp")」とすると MPS ファイルから LP ファイルに変換できます． 「m = read("test3.lp")」「m.write("test4.mps")」で逆の変換ができます（m はモデル名なので違う名前でも構いません）．
    • [SCIP]　コマンドラインでは，「read test1.mps」「write problem test2.lp」とすると MPS ファイルから LP ファイルに変換できます． 「read test3.lp」「write problem test4.mps」で逆の変換ができます．

  7. LP ファイルを MPS ファイルに変換したら，目的関数値がマイナス 1 倍になった

    　いくつかのソルバーでは，最大化問題の LP ファイルを MPS ファイルに変換すると，係数をマイナス 1 倍した最小化問題に置き換えるようです．

  8. LP ファイルで二次の目的関数を表したい

    　最小化問題の場合に凸二次目的関数，最大化問題の場合に凹二次目的関数が直接扱えるソルバーがあります．
    　目的関数において，線形項を先に書き，それに続いて二次項を + [ 2 x^2 - 4 x * y + 9 y^2 ] /2 のように書きます． 変数の 2 乗は ^2 を，クロス項には * を使います． また，係数は 2 倍して書き，二次項の全体を [ ] /2 でくくります（[ ] とそれより内側はスペースで区切る）．
    • [CPLEX]　CPLEX 12.6 から，制約式が線形であるような二次最適化問題もしくは二次整数最適化問題については，『最小化問題の場合には凸二次目的関数，最大化問題の場合は凹二次目的関数』以外の目的関数が扱えるようになりました． 普通に解いてみて，"Q in objective is not positive semi-definite." というエラーメッセージが表示された場合，『 』内の条件を満たしていません． Interactive Optimizer では，「set optimalitytarget 3」として問題を解き直してください（このオプションは，以前は solutiontarget という名前でした）． ただし，『 』内の条件を満たしている問題と比べるとかなり計算に時間がかかるので注意が必要です．
    • [Gurobi]　Gurobi 9.0 から，『最小化問題の場合には凸二次目的関数，最大化問題の場合は凹二次目的関数』以外の二次の目的関数が扱えるようになりました． 普通に解いてみて，エラーメッセージが表示された場合，『 』内の条件を満たしていません． 「setParam("NonConvex", 2)」として問題を解き直してください． ただし，『 』内の条件を満たしている問題と比べるとかなり計算に時間がかかるので注意が必要です．

  9. LP ファイルで二次の制約式を表したい

    　凸二次制約，二次錐制約が直接扱えるソルバーがあります．
    　制約式における二次項は [ x^2 - 2 x * y + 7 y^2 ] <= 58 や [ x(1)^2 + 3 x(2)^2 - y * z ] <= 0 のように書きます（[ ] とそれより内側はスペースで区切る）． 変数の 2 乗は ^2 を，クロス項には * を使います． 目的関数における二次項との違いは，係数を 2 倍して /2 する必要がないということです．
    • [Gurobi]　Gurobi 9.0 から，『制約式に含まれる変数を連続変数とみなした時，許容領域が凸になる二次不等式』以外の二次制約式が扱えるようになりました（例えば，z = x * y というような双線形等式制約が扱えます）． 普通に解いてみて，エラーメッセージが表示された場合，『 』内の条件を満たしていません． Interactive Shell では，「setParam("NonConvex", 2)」として問題を解き直してください． ただし，『 』内の条件を満たしている問題と比べるとかなり計算に時間がかかるので注意が必要です．

  10. LP ファイルで目的関数に定数項を含めたい

    　LP ファイルには統一されたフォーマットが存在せず，ソルバーごとに独自の拡張がされています． 目的関数に定数項を含めた LP ファイルを直接扱えるソルバーもあるのですが，エラーとなるソルバーもあり，現状では目的関数に定数項を含めた LP ファイルを書くことはあまりおすすめできません． 目的関数値を定数項を含めた値として表示させたい場合は，例えば目的関数に定数項に対応する変数を加え，制約式でその変数の値を固定してしまえば同等のことができます．

  11. LP ファイルに書く変数や制約式の順番を変えたら計算時間が変わった

    　ソルバーは分枝限定法の中で分枝順序を様々な情報から決定していますが， 最終的に優先度が等しい場合には何らかの順序をつける必要があるため，分枝順序および計算時間が変数や制約式を記述した順番に依存することがあります． このあたりの情報は 参考文献 4 に詳しいです．

  12. Lazy Constraints を使いたい

    　ソルバーによっては Lazy Constraints が使えます． Lazy Constraints と定義された制約式は，最初は問題から取り除かれており，許容解が見つかるたびに問題に追加するべきかどうかチェックされます． 制約式の本数が膨大になってしまうが，実際にはそのうちのごく一部しか意味がないような問題で効果を発揮します．
    　以下では，LP ファイルで Lazy Constraints を扱う方法を説明します． そもそも制約式全体を LP ファイルに書ききるのが難しい場合や，動的に Lazy Constraints を追加したいような場合は，各ソルバーの API を利用するのが便利です． 詳細はマニュアルを参照してください．
    • [CPLEX]　LP ファイルでは，通常の制約式の後かつ bounds セクションの前に Lazy Constraints という予約語を書き，Lazy Constraints にしたい制約式を列挙します．
    • [Gurobi]　LP ファイルでは，通常の制約式の後かつ bounds セクションの前に Lazy Constraints 2 という予約語を書き，Lazy Constraints にしたい制約式を列挙します． 数字は 1, 2, 3 のいずれかを書くことができます（数字を指定しない場合は 1 とみなされます）． この数字は元問題への Lazy Constraints の追加の方法を制御しているのですが，通常の場合は 2 で問題無いと思われます． 詳細はマニュアルの linear constraint attribute の lazy の項を参照してください．
目次へ戻る

  1. ソルバーの調整と計算速度について

　計算速度に関係する部分での，ソルバーの調整についてです．

  1. 最小化問題でなかなか下界が上がらない．最大化問題でなかなか上界が下がらない

    　定式化が良くない可能性もありますが，とりあえずソルバーのパラメータを調整してみる価値はあると思われます．
    • [CPLEX]　Interactive Optimizer では，「set emphasis mip 2」で，最小化問題の場合には下界を上げる，最大化問題の場合には上界を下げることに重点を置いた分枝限定法になります． 「set emphasis mip 3」で，そのさらに強力なバージョンになります．
    • [Gurobi]　Interactive Shell では，「setParam("MIPFocus", 2)」で，最小化問題の場合には下界を上げる，最大化問題の場合には上界を下げることに重点を置いた分枝限定法になります． 「setParam("MIPFocus", 3)」で，そのさらに強力なバージョンになります．
    • [SCIP]　コマンドラインでは，「set emphasis optimality」で，最小化問題の場合には下界を上げる，最大化問題の場合には上界を下げることに重点を置いた分枝限定法になります．

  2. 最適解にこだわらないので，なるべく高速に質の良い解がほしい

    　ソルバーのパラメータを調整するのが手っ取り早いと思われます．
    • [CPLEX]　Interactive Optimizer では，「set emphasis mip 1」で，許容解を探すことに重点を置いた分枝限定法になります． 「set emphasis mip 4」で，そのさらに強力なバージョンになります． 「set emphasis mip 5」で，「set emphasis mip 4」よりさらに許容解の発見に注力した分枝限定法になります．
    • [Gurobi]　Interactive Shell では，「setParam("MIPFocus", 1)」で，許容解を探すことに重点を置いた分枝限定法になります．
    • [SCIP]　コマンドラインでは，「set emphasis feasibility」で，許容解を探すことに重点を置いた分枝限定法になります．

  3. 計算時間を制限して，分枝限定法を自動的に停止するようにしたい

    　以下のコマンドで，分枝限定法を 10000 秒で終了させられます． 数字を変えることにより秒数を自由に設定できます．
    • [CPLEX]　Interactive Optimizer では「set timelimit 10000」とします．
    • [Gurobi]　Interactive Shell では「setParam("TimeLimit", 10000)」とします．
    • [SCIP]　コマンドラインでは「set limits time 10000」とします．

  4. 定めた閾値と同じかより良い目的関数値の許容解が出たら，分枝限定法を自動的に停止するようにしたい

    　用途によっては，ユーザーが定めた閾値と同じかより良い目的関数値（最小化問題では閾値以下，最大化問題では閾値以上）を持つ許容解が得られれば十分な場合があります． 以下のコマンドで，定めた閾値と同じかより良い目的関数値の許容解が出たら，分枝限定法を自動的に停止するようにできます． 以下では閾値を 200 として説明しますが，数字を変えることにより閾値は自由に設定できます．
    • [CPLEX]　Interactive Optimizer では，最小化問題の場合は「set mip limits lowerobjstop 200」とすると，目的関数値が 200 以下の許容解が得られたら自動で停止します． 最大化問題では「set mip limits upperobjstop 200」とすると，目的関数値が 200 以上の許容解が得られたら自動で停止します．
    • [Gurobi]　Interactive Shell では「setParam("BestObjStop", 200)」とすると，最小化問題では目的関数値が 200 以下の許容解が得られたら，最大化問題では目的関数値が 200 以上の許容解が得られたら，自動で停止します．
    • [SCIP]　コマンドラインでは「set limits primal 200」とします．なお，SCIP 9.0.1 以前では「set limits objectivestop 200」とします．

  5. 許容解を与えた状態で分枝限定法をスタートしたい

    　（質の良い）許容解を与えることにより，分枝限定法の高速化をねらいます． 特に，許容解が見つかりにくい問題では計算時間の短縮が期待できます．
    • [CPLEX]　許容解を記述した MST ファイル（test1.mst とします）を作成し，「read test1.lp」「read test1.mst」「optimize」とすることで，許容解を読み込んだ状態で分枝限定法がスタートします． （CPLEX で許容解を得られた状態で MST ファイルを write すると，XML 形式の MST ファイルが出力され，またマニュアルでも XML 形式の MST ファイルが解説されていますが，簡単に使うには古いバージョンの MST ファイルが便利なので，このページでは下記の方法を紹介します．） CPLEX の（古いバージョンの） MST ファイルとは， 
      NAME
     x  1
     y  0
     z  7
ENDATA
      のように，一行に一つずつ整数変数を記述し，その後ろにスペースを空けて許容解での対応する値を記述した，拡張子が .mst のテキストファイルです． 一行目には NAME と書き，最終行には ENDATA と書きます． 整数変数は，各行で 5 文字目以降に書く必要があります． その後ろにスペースを空けて許容解での対応する値を記述します． （Gurobi の MST ファイルと文法が少し異なるので注意）
      　注意：CPLEX 12.6.1 より，上記の古い MST ファイルが使用できなくなりました． XML 形式の MST ファイルを自前で作成してもよいのですが，とりあえずの対処方法として，LP ファイル自体に制約式を追加して既知の許容解を出力させ，「write test1.mst」とすれば XML 形式の MST ファイルを出力することができます．
    • [Gurobi]　許容解を記述した MST ファイル（test1.mst とします）を作成し，「m = read("test1.lp")」「m.read("test1.mst")」「m.optimize()」とすることで，許容解を読み込んだ状態で分枝限定法がスタートします（m はモデル名なので違う名前でも構いません）． Gurobi の MST ファイルとは， 
      x  1
y  0
z  7
      のように，一行に一つずつ整数変数を記述し，その後ろにスペースを空けて許容解での対応する値を記述した，拡張子が .mst のテキストファイルです． 詳細は MST format でマニュアルを検索してください．（CPLEX の MST ファイルと文法が少し異なるので注意）
    • [SCIP]　許容解を記述した MST ファイル（test1.mst とします）を作成し，「read test1.lp」「read test1.mst」「optimize」とすることで，許容解を読み込んだ状態で分枝限定法がスタートします． SCIP の MST ファイルとは， 
      x  1
y  0
z  7
      のように，一行に一つずつ整数変数を記述し，その後ろにスペースを空けて許容解での対応する値を記述した，拡張子が .mst のテキストファイルです（問題を解いて許容解が得られた時に「write solution test1.mst」とすると，もう少し詳細な情報が書かれた MST ファイルが出力されますが，許容解を与えるだけなら上記の書き方で問題ありません）．

  6. ソルバーをヒューリスティクスとして使いたい

    　上記の「最適解にこだわらないので，なるべく高速に質の良い解がほしい」「計算時間を制限して，分枝限定法を自動的に停止するようにしたい」「定めた閾値と同じかより良い目的関数値の許容解が出たら，分枝限定法を自動的に停止するようにしたい」「許容解を与えた状態で分枝限定法をスタートしたい」を組み合わせて使うと良いと思われます．
    • [CPLEX]　分枝限定法の他に，solution polishing というアルゴリズムも実装されています（ただし，デフォルト設定では solution polishing のモードには入りません）． 問題によっては，強力に働くヒューリスティクスです（アルゴリズムの詳細は 参考文献 11 に記載されています）． Solution polishing についてはいろいろな設定が可能ですが，Interactive Optimizer では例えば「set mip polishafter solutions 1」と設定することで，許容解を 1 つ見つけた後は分枝限定法から solution polishing ヒューリスティクスへ移行するようにできます． （許容解を 1 つ見つけたにも関わらず "Starting solution polishing." と表示されない，あるいは計算が止まってしまう場合は，「set mip polishafter solutions 1」の 1 を 2, 3, ... と徐々に増やして，最初から解き直してみてください．） あるいは，「set timelimit 1000」「set mip limits polishtime 200」と設定することで，通常の分枝限定法を 1000 秒で終了し，その後に 200 秒 polishing を行うようにできます（数字を変えることにより秒数を自由に設定できます）． ただし，分枝限定法の段階で許容解が見つかっていることが必要です．
    • [Gurobi]　分枝限定法の他に，NoRel heuristic というアルゴリズムも実装されています（ただし，デフォルト設定では NoRel heuristic のモードには入りません）． Norel heuristic は分枝限定法に入る前に実行される，問題によっては強力に働くヒューリスティクスです． NoRel heuristic についてはいくつかの設定が可能ですが，Interactive Shell では例えば「setParam("NoRelHeurTime", 200)」と設定することで，NoRel heuristic を 200 秒実行した後に通常の分枝限定法へ移行するようにできます（数字を変えることにより秒数を自由に設定できます）． なお，「計算時間を制限して，分枝限定法を自動的に停止するようにしたい」で計算時間を制限している場合，この計算時間には NoRel heuristic の時間が含まれます． 例えば，「setParam("TimeLimit", 1000)」「setParam("NoRelHeurTime", 200)」とした場合には，分枝限定法の前に NoRel heuristic が 200 秒実行され，その後に通常の分枝限定法が 800 秒実行されることになります．

  7. 分枝順序を手動で指定したい

    　最近のソルバーはかなり賢くなっているので，デフォルトの分枝順序はかなり高速です． 手作業による分枝順序の調整に多くの時間を掛けることはあまりおすすめしません． ただし，特定の変数を固定すると問題が著しく小さくなるなど，問題構造を詳しく知っている場合には分枝順序の手動指定が有効な場合もあります．
    • [CPLEX]　ORD ファイルと呼ばれるファイルを作ると，Interactive Optimizer でも分枝順序が指定できます． 「ORD file format」でマニュアルを検索してください． （Gurobi の ORD ファイルと文法が異なるので注意．特に CPLEX の ORD ファイルは，一つの行の何文字目から何を書くかが指定されています．）
    • [Gurobi]　ORD ファイルと呼ばれるファイルを作ると，Interactive Shell でも分枝順序が指定できます． 「ORD format」でマニュアルを検索してください． （CPLEX の ORD ファイルと文法が異なるので注意）

  8. 並列分枝限定法でスレッド数を指定したい

    　並列分枝限定法が実装されているソルバーでは，マルチコア CPU の利点を生かすことができます． あるいは，他のタスクの邪魔をしないようにスレッド数を減らすことも可能です．
    • [CPLEX]　Interactive Optimizer では，「set threads k」で k スレッドで分枝限定法が実行できます． デフォルトでは，計算機にある論理コアをフルに使用します． なお，マルチスレッドで実行した際に clone0.log, clone1.log, ... のようなファイルが出力されますが，これが不要だという場合は「set output clonelog -1」としてください．
    • [Gurobi]　Interactive Shell では，「setParam("Threads", k)」で k スレッドで分枝限定法が実行できます． デフォルトでは計算機にある論理コアをフルに使用しますが，スレッド数が 32 を超えるような場合は 32 が上限となります． スレッド数を 32 より多くしたい場合は，手動で数字を指定する必要があります．

  9. 並列分枝限定法において，スレッド数を増やしたら遅くなってしまった

    　スレッド数を増やしても遅くなる場合はあります． 参考文献 4 の図 4 が詳しいです． ですが，例えば 1 スレッドと 16 スレッドくらいだとそれなりに違いが出てくるようです． 「並列分枝限定法でスレッド数を指定したい」の項も参照してください．

  10. ソルバーのオプション A のみをオンにしたら計算が速くなり，オプション B のみをオンにしたら計算が速くなったので，オプション A と B を両方オンにしたところ計算が遅くなってしまった

    　そういうことはしばしばあります．

  11. 計算を一度中断してから再開したら，中断しない場合と計算過程が異なった

    　ソルバーによっては，そういうことがあります．

  12. 計算時間を制限したら，制限しない場合と計算過程が異なった

    　ソルバーによっては，計算時間の上限を指定すると，その上限に近づいても最適性ギャップが大きいとき（計算が最後まで終了しなそうなとき）に許容解の発見を優先するモードに切り替わるものがあるようです．

  13. 線形最適化問題を複数回解いてみたら，最適解が異なった

    　ソルバーによっては，マルチスレッドで線形最適化問題を解くと，複数のアルゴリズム（単体法や内点法）を用いて計算し一番速く終了したものを出力します． このため，稀なケースですが，アルゴリズム間の計算時間の差異が微小なときは試行ごとに異なる最適解が出る可能性があるようです．
    • [CPLEX]　Interactive Optimizer では，「set parallel 1」で線形最適化問題に対して毎回同じ解を出すようにすることができます．
    • [Gurobi]　Interactive Shell では，「setParam("Method", 4)」で線形最適化問題に対して毎回同じ解を出すようにすることができます．
目次へ戻る

  1. ソルバーをもっと便利に使いたい

　ソルバーの便利な機能の紹介をします．

  1. ソルバーが前処理をした LP ファイルを見たい

    　いくつかのソルバーでは，ソルバーが前処理した後の LP ファイルを見ることができます．
    • [CPLEX]　Interactive Optimizer では，問題を読み込んで前処理が終了した後（分枝が始まったとき），Ctrl-C で分枝限定法を中断し，「write test1.pre」で前処理後のファイルが出力されます． それから，「read test1.pre」「write test2.lp」とすれば，test2.lp が前処理後の LP ファイルとなっています．
    • [Gurobi]　Interactive Shell では，「m = read("test1.lp")」「m2 = m.presolve()」「m2.write("test2.lp")」とすれば test2.lp が test1.lp の前処理後の LP ファイルとなっています（ここで m と m2 はモデル名なので違う名前でも構いません）．
    • [SCIP]　コマンドラインでは，「read test1.lp」「presolve」「write transproblem test2.lp」とすれば，test2.lp が前処理後の LP ファイルとなっています．

  2. どのように分枝限定法が進んでいるかを詳細に観察したい

    　分枝限定法の可視化を行う際などは，ノード間の関係が必要になります．
    • [CPLEX]　Interactive Optimizer では，「set mip strategy search 1」「set mip interval 1」とすると，（画面表示ではなく）ログファイルにノードの親子関係が表示されます． ただし，現在デフォルトで採用されている探索方法ではないため，多くの場合に計算時間が余分にかかります． また 1 ノードごとにログを表示するため，ログファイルが膨大になるので注意が必要です．

  3. 整数変数の値が異なる最適解の個数を数えたい

    　原理的には可能です． ですが，最適解の個数は問題によっては非常に多くなりえます． 特に，変数間に対称性がある場合には容易に非現実的な数になります（事実上列挙しきれない）． したがって，小さな問題から試すのが得策です．
    • [CPLEX]　Interactive Optimizer では，以下のパラメータをセットした後に populate としてください： 「set mip pool absgap 0」「set mip pool intensity 4」「set mip limits populate 2100000000」．
    • [Gurobi]　Interactive Shell では，「setParam("PoolSearchMode", 2)」「setParam("PoolSolutions", 2000000000)」「setParam("PoolGap", 0)」として問題を解いてください．
    • [SCIP]　まず問題を解いて，最適値を確認します． その次に，「目的関数 = 最適値」という制約式を LP ファイルに追加し，count というコマンドを使います． 詳しくは，https://www.scipopt.org/doc/html/COUNTER.php を参照してください．

  4. ログファイルの出力先を変更したい

    　複数の問題を解く場合には，ログファイルを分けておくと便利です．
    • [CPLEX]　Interactive Optimizer では，「set logfile test1.log」で test1.log というファイルにログが残ります（デフォルトは cplex.log）． なお，「set default」で全てのオプションをデフォルトに戻せますが，ログファイルの出力先変更のみは set default の影響を受けないので注意してください． ログファイルの出力先をデフォルトに戻すには，明示的に「set logfile cplex.log」としてやる必要があります．
    • [Gurobi]　Interactive Shell では，「m.setParam("LogFile", "test1.log")」（ここで m は現在扱っているモデル名）で test1.log というファイルにログが残ります（デフォルトは gurobi.log）． ただし，Gurobi 9.0 から，API 経由で Gurobi を使用する場合はデフォルトではログファイルが出力されないようになりました． パラメータ LogFile に明示的に出力先を指定してやる必要があります（Interactive Shell やコマンドラインの gurobi_cl ではデフォルトで gurobi.log に出力されます）．

  5. 複数の問題を自動的に解かせたい

    　いくつかの方法がありますが，とりあえず OS のコマンドライン（Windows の場合はコマンドプロンプト）を用いて制御する方法を紹介します．
    • [CPLEX]　CPLEX の Interactive Optimizer に与えるコマンドを 1 行に一つずつ書いたテキストファイルを test.txt とします． OS のコマンドラインで「cplex < test.txt （あるいは cplex -f test.txt）」とすると，CPLEX が test.txt に書かれた内容を順次実行します． これを OS コマンドの自動実行スクリプト（Windows の場合にはバッチファイル等）と組み合わせれば，複数の問題の自動処理ができます． （単一の test.txt の中に複数の問題の処理を書いても良いのですが，問題間で連携する必要がなければ，CPLEX のリフレッシュの意味も含めてテキストファイルを問題別に用意したほうが良いと思われます．）
      CPLEX 用の test.txt の例： 
      set logfile test1.log
set threads 1
set mip display 4
set workmem 8192
set mip tolerances mipgap 0
set mip tolerances absmipgap 0
set timelimit 10000
read test1.lp
optimize
display solution variable -
quit
    • [Gurobi]　OS のコマンドラインで「gurobi_cl TimeLimit=10000 LogFile=test1.log ResultFile=test1.sol MIPGap=0 MIPGapAbs=0 Threads=1 test1.lp」というように，「gurobi_cl　オプションに与える引数群　問題名」とすると問題を解くことができます． これを OS コマンドの自動実行スクリプト（Windows の場合にはバッチファイル等）と組み合わせれば，複数の問題の自動処理ができます．
    • [SCIP]　SCIP の実行ファイル名が scip.exe という名前だとし，また SCIP のコマンドラインに与えるコマンドを 1 行に一つずつ書いたテキストファイルを test.txt とします． 「scip.exe -l test1.log -b test.txt」とすると，test1.log に test.txt を実行した内容が記録されます． これを OS コマンドの自動実行スクリプト（Windows の場合にはバッチファイル等）と組み合わせれば，複数の問題の自動処理ができます．
      SCIP 用の test.txt の例： 
      set limits time 10000
read test1.lp
optimize
display solution
quit

  6. 複数の問題間で情報をやりとりしたい．他のプログラムと連携したい

    　LP ファイルをコマンドライン・インターフェースで解く方法は，最も単純な方法です． 列生成法など，複数の問題の間で情報をやりとりする必要がある場合には，ソルバーの API などを用いるのが得策です． 各ソルバーのマニュアルおよびサンプルファイルを参照してください．
    • [CPLEX]　Interactive Optimizer では，xecute というコマンドを用いると，xecute に続けて与えた引数を OS に渡します（例えば「xecute dir *.lp」など）． このコマンドを用いると，ある程度は他のプログラムの処理も Interactive Optimizer 上から行えます（ですが，高度な処理はやはり API を用いた方が楽に行うことができます）．
    • [Gurobi]　Interactive Shell 自体が Python インタープリタになっており，この上からソルバーをプログラムで高度に制御できます． 参考文献 5 にわかりやすい解説およびサンプルプログラムが載っています． また，「system("コマンド名")」で OS のコマンドを使用できます．
    • [SCIP]　SCIP はソースコードが全て公開されており，単なるソルバーとしてだけではなく，分枝限定法のフレームワークとして提供されています．

  7. 計算を中断することなく，暫定解そのものを自動的に記録したい

    　用途によっては，最適解以外の解も見たいことがあります．
    • [CPLEX]　Interactive Optimizer では，「set output intsolfileprefix test」として分枝限定法を実行してください（ここで test は出力されるファイル名なので違う名前でも構いません）． 見つかった暫定解の順序で test-00001.sol, test-00002.sol, ... のように解の情報を保存したファイルが出力されます． これらのファイルは xml ファイルで，テキストとして中身を見れば解がわかるようになっています．
    • [Gurobi]　Interactive Shell では，「m.setParam("SolFiles", "./test")」（ここで m は現在扱っているモデル名）とすることで，見つかった暫定解の順序で test_0.sol, test_1.sol, ... のように解の情報を保存した sol ファイルが現在のディレクトリに出力されます． "./test" の部分を変更することで出力されるディレクトリおよび sol ファイルの名前を変更できます．

  8. 変更したパラメータ設定を表示・保存・復元したい

    　ソルバーの変更したパラメータ設定を表示・保存する方法です．
    • [CPLEX]　Interactive Optimizer では，「display settings changed」でデフォルト値から変更されているパラメータの一覧を表示できます． 別の LP ファイルを読み込んでもパラメータの設定は変化しません． 現在のパラメータ設定は「write ファイル名.prm」とすることでファイルに出力ができ，「read ファイル名.prm」で復元できます． 「set default」で全てのパラメータをデフォルト値に戻せますが，ログファイルの出力先だけは「set default」でデフォルトに戻らないので注意してください（ログファイルの出力先を変更したい も参照してください．デフォルトの出力先は cplex.log です）．
    • [Gurobi]　Interactive Shell では，現在扱っているモデル名とそのモデルで変更されたパラメータの一覧を「models()」で表示できます． 現在のパラメータ設定は「writeParams("ファイル名.prm")」とすることでファイルに出力ができ，「readParams("ファイル名.prm")」で復元できます． 「resetParams()」で全てのパラメータをデフォルト値に戻せます． 「setParam("パラメータ名", "default")」でそのパラメータをデフォルト値に戻せます．
      　また，上記の setParam, writeParams, readParams, resetParams などは，現在扱っているモデル名を m とするとき「m.setParam("パラメータ名", 新しい値)」等とすることで，そのモデルのみにおけるパラメータを操作できます． 本ページでは主にパラメータの一括変更を例にあげて説明していますが，必要に応じて使い分けてください．
    • [SCIP]　コマンドラインでは，「display parameters」でデフォルト値から変更されているパラメータの一覧を表示できます． 別の LP ファイルを読み込んでもパラメータの設定は変化しません． 現在の全パラメータ設定は「set save ファイル名」とすることでファイルに出力でき，「set load ファイル名」とすることで復元できます． 現在のデフォルト値から異なるパラメータ設定は「set diffsave ファイル名」とすることでファイルに出力でき，「set load ファイル名」とすることで復元できます． 「set default」で全てのパラメータをデフォルト値に戻せます．

  9. 問題の統計情報が見たい

    　読み込んだ問題について，変数の個数や制約式の本数を表示できます．
    • [CPLEX]　Interactive Optimizer では，「display problem stats」で現在読み込んでいる問題の情報を表示できます．
    • [Gurobi]　Interactive Shell では，「m.printStats()」で現在読み込んでいる問題の情報を表示できます（ここで m は現在扱っているモデル名）．
    • [SCIP]　コマンドラインでは，「display statistics」で現在読み込んでいる問題の情報を表示できます．

  10. 与えた整数最適化問題の連続緩和問題を得たい

    　読み込んだ整数最適化問題について，その連続緩和問題（整数制約を取り除いた問題）を出力させることができます．
    • [CPLEX]　Interactive Optimizer では，まず「read test1.lp」として整数最適化問題を読みこませます． 次に，読みこませた整数最適化問題の種類に応じて，「change problem lp」「change problem qp」「change problem qcp」のいずれかのコマンドを用います． 「change problem lp」では目的関数の 2 次項，および 2 次の制約式と整数制約が問題から取り除かれます． 「change problem qp」では 2 次の制約式と整数制約が問題から取り除かれます（目的関数の 2 次項は保持されます）． 「change problem qcp」では整数制約が問題から取り除かれます（目的関数の 2 次項と 2 次の制約式は保持されます）． change コマンドを用いた後，「write test2.lp」とすれば連続緩和問題を LP ファイルとして出力できます． なお，indicator などの特殊な制約は取り除かれます．
    • [Gurobi]　Interactive Shell では，「m = read("test1.lp")」としてから「mr = m.relax()」とすると mr が連続緩和問題に対応するモデルになっています（ここで m は現在扱っているモデル名，mr は連続緩和問題に対応するモデル名）． 「mr.write("test2.lp")」で test1.lp の連続緩和問題を LP ファイルとして出力できます． なお，indicator などの特殊な制約は取り除かれます．

  11. 与えた線形最適化問題の双対問題を得たい

    　読み込んだ線形最適化問題について，その双対問題を出力させることができます．
    • [CPLEX]　Interactive Optimizer では，「read test1.lp」として問題を読みこませた後，「write problem test1.dua」としてください． test1.dua という，test1.lp の双対問題を記録した MPS ファイルが出力されます． これを LP ファイルに変換したければ，「read test1.dua」とした後，「write problem test2.lp」とすれば LP ファイルとして出力されます．
    • [Gurobi]　Interactive Shell では，「m = read("test1.lp")」としてから「m.write("test1.dua")」とすると test1.dua という test1.lp の双対問題を記録した MPS ファイルが，「m.write("test1.dlp")」とすると test1.lp の双対問題を記録した LP ファイルが出力されます（ここで m は現在扱っているモデル名）．

  12. [CPLEX]　暫定解が得られたときの経過時間を自動的に記録したい

    　CPLEX 12.5 から簡単になっています． Interactive Optimizer では，「set mip display 3」（あるいは「set mip display 4」）として分枝限定法を実行してください．

  13. [CPLEX]　Benders 分解を行いたい

    　混合整数最適化問題を解く際に，Benders 分解法を用いることができます． 一部の問題では効果が期待できます． Interactive Optimizer では，「set benders strategy 3」として問題を解くと，全ての整数変数はマスター問題へ，全ての連続変数はサブ問題へと分割されて Benders 分解法が実行されます． また，ユーザー自身で問題の分割を指定することもできます． 詳しくはマニュアルを参照してください．
目次へ戻る

  1. 定式化について

　定式化に関して，よくある質問を記載します．

  1. 実際の現場では使えないような答えが出てくる

    　出てきた解が記述した制約条件を全て満たしているならば，ソルバーや整数最適化自体の問題というよりは，現実の制約条件が全て制約式として表現されていないことによるものです． 人間が暗黙のうちに仮定しているが，明示的に書いていない制約式はないかどうかチェックしてください．

  2. 線形式で書けないと思われる制約条件または目的関数がある

    　絶対値や max 演算子など，一見して線形式で表せなさそうな場合でも，補助変数などを導入して定式化できることがあります． 参考文献 1 に，日本語でよくまとまった情報があります．
    • [Gurobi]　Gurobi 7.0 から，LP ファイルや API で MAX, MIN, ABS, AND, OR の演算子が使えます． それぞれのキーワードでマニュアルを検索してください．

  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 変数です．
    　さらに，二次錐制約が使えるソルバーでは非負の連続変数 y に対し x^2 <= y * z という二次錐制約式で x <= M * z と同様の制約を表すことができます． これは perspective 再定式化 (perspective reformulation) と呼ばれるテクニックの一種です． Perspective 再定式化の詳細は，例えば 参考文献 20 をお読みください．
    • [CPLEX][Gurobi][SCIP]　Indicator と呼ばれる LP ファイルの書式を使うと，制約式の切り替えができます． x を 0-1 変数とするとき，LP ファイルに「x = 0  ->  線形制約式」と書くと x が 0 のときのみ右側の線形制約式が有効になります． 「x = 1  ->  線形制約式」とすると x が 1 のときのみ有効です．
      「x = 0  ->  9 z + 5 y <= 6」
      「x = 1  ->  7 z + w = 0」
      のように両立させることも可能です． ただし，-> の左側に書く変数は 0-1 変数でなくてはならず，-> の右側は線形制約式でなければならないという制限があります． 詳しくは indicator variable でマニュアルを検索してください．
    　なお，「A または B」というような制約式を書きたい場合には，disjunctive constraint（離接制約）を用いて定式化する方法もあります． 離接制約を扱うような問題は disjunctive programming と呼ばれています． 詳しくは 参考文献 16，参考文献 21 を参照してください．

  5. 変数の個数が少ない問題なのに解けない．変数の個数が少ない定式化に変えたら遅くなった

    　変数が少ない（あるいは制約式が少ない）問題あるいは定式化が，必ずしも計算時間が短いわけではありません． どのような定式化が良い定式化（≒高速に解ける定式化）になるかはケースバイケースですが，一般的には「線形緩和問題の最適値と整数最適化問題の最適値の乖離が小さい」定式化が良い定式化になることが多いです． ただしベストを尽くしても，あまりにも変数が多い問題や整数最適化に向いていない問題は解くのが難しいのも事実です．
    例：小さいのに難しい問題の LP ファイル （MIPLIB 2017 の pb-market-split8-70-4）． 0-1 変数 71 個，制約式 17 本の小さな問題ですが（本質的には 0-1 変数 70 個，等式ナップサック制約 8 本の許容性判定問題），2023 年 11 月まで許容解が一つも見つかっておらず，また不能であることも証明されていませんでした． 現在は許容解（かつ最適解）が発見されています（ 参考文献 23 ）．

  6. 線形や二次でない目的関数を扱いたい

    　多項式関数を直接扱えないソルバーでも，凸二次制約を扱える場合は以下のようなトリックで次数を上げることができます． 制約式で x^2 <= y かつ y^2 <= z とし，z を最小化すれば x の 4 乗を最小化していることと等価です（LP ファイルの形式では - y + [ x^2 ] <= 0 かつ - z + [ y^2 ] <= 0）． また，二次錐制約を扱えるソルバーでは，非負変数 x, s, t に対し x^2 <= s * t かつ s^2 <= x とし，t を最小化すれば x の 1.5 乗を最小化していることと等価です（LP ファイルの形式では [ x^2 - s * t ] <= 0 かつ - x + [ s^2 ] <= 0）． この種のテクニックは，参考文献 22 にまとめられています．
目次へ戻る

  1. その他の情報

　その他，役に立つリンク先などの情報をまとめておきます．

  1. 整数最適化問題のベンチマーク問題集が知りたい

    　いくつかありますが，有名なのは MIPLIB (Mixed Integer Programming LIBrary) です． 現時点では MIPLIB 2017 ( 参考文献 19, https://miplib.zib.de/ ) が最新バージョンです． 少し前までは MIPLIB 2010 ( 参考文献 4, https://miplib2010.zib.de/ ) がよく用いられていました．

  2. 商用ソルバーと非商用ソルバーは計算時間がどの程度異なるのか

    　現時点では，最高速の商用ソルバーと最高速の非商用ソルバーとを比較すると，前者の方がかなり高速です． Hans Mittelmann のベンチマークサイト（ https://plato.asu.edu/bench.html ）によると，2 時間以内で解ける簡単な問題で，10 倍近い速度差があるようです． さらに，難しい問題ほどソルバーの性能差が顕著に現れます（数分と数時間，あるいは数時間と数日というようなケースも稀ではありません）．

  3. どの商用ソルバーが速いのか

    　問題によってソルバー A の方が速かったり，ソルバー B の方が速かったりということがあります． なので，どのソルバーが速いのかというのは統計的に見るしかないことにご注意ください． ソルバー別のベンチマーク結果については，Hans Mittelmann のベンチマークサイト（ https://plato.asu.edu/bench.html ）が有名です． なお，現在は一部の商用ソルバーについて，ベンチマーク結果の掲載を停止しているようです（古い結果は残っています）．

  4. 商用ソルバーを試してみたい

    　いくつかの商用ソルバーのベンダーでは，各種トライアルライセンスを準備しています． さらにアカデミックユーザーの場合は，無償または格安ライセンスが提供されていることもあります． なお，商用ソルバーはバージョンアップ時に大幅に性能が向上していることが多いため，なるべく最新バージョンの使用をおすすめします．
    　また，NEOS サーバー（ https://www.neos-server.org/neos/ ）を用いると，アカデミックユーザーの場合は利用規約の範囲内で CPLEX や Gurobi などの商用ソルバーを使うことができます． ただし，問題の規模や計算時間に制限があります． 詳しくは，NEOS サーバーのユーザーズガイド（ https://neos-guide.org/users-guide ）や FAQ（ https://neos-guide.org/content/FAQ ），および NEOS サーバーの利用規約（ https://neos-server.org/neos/termofuse.html ）を参照してください．
目次へ戻る
このページのトップへ戻る　　トップページへ戻る
宮代 隆平（東京農工大学 工学部 知能情報システム工学科），公開：2013年4月，最終更新：2025年2月