整数計画法メモ

トップページへ戻る

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

はじめに

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

おことわり

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

更新履歴

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

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, 2024.
    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.1.1). Zuse Institute Berlin, 2024.
    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.1.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 とします． 以下のコマンドで，問題の読み込み，計算の実行，最適解の表示ができます．

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

    　難しい整数最適化問題を最後まで解ききれないときに，計算を手動で停止する方法です． あらかじめ計算時間を制限する場合は，「計算時間を制限して，分枝限定法を自動的に停止するようにしたい」を参照してください．

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

    　LP ファイルを読み込む際の注意です．

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

    　コマンド入力の省略方法についてです．

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

    　各ソルバーの詳細はマニュアルに記載されていますが，ソルバー上でも簡易ヘルプを参照できます．
目次へ戻る

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

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

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

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

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

    　まずは，予約語（minimize 等）のスペルミスが無いか確認してください． 大部分の予約語は基本的に新しい行から始め，その後ろで改行します． 線形制約式を書くのに [ ] や / や * などを使っていないでしょうか（これらの記号は二次項を表すのに使います）． 定数係数と変数の積は，スペースを使って表します． また，e や E は 1e4 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 のメモリを食いつぶしているような場合には，計算を続けるとすぐにその倍のメモリを消費してしまうことも多く，メモリを多少増設してもあまり効果がないことがあります．

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

    　非常に大きな係数を持つ制約式が混在する問題など，数値的に不安定になるケースがいくつかあります． 特に，制約式に二次項を含む問題は数値的に不安定になりがちです． このような場合，制約式を前もってスケーリングしておくと良い結果になることもあります． 　また，目的関数が凸二次関数（最大化問題の場合は凹二次関数）のはずなのに，数値誤差の影響で「凸でない」というエラーが出る場合があります． この場合，目的関数の係数を全て整数にスケーリングする，対角項の係数を微小に増加させる，新しい変数と制約式を導入して係数行列を疎にするなどの対策を試してみてください．

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

    　いくつかの例外を除いて，目的関数は線形関数または凸二次関数（最大化問題の場合には凹二次関数）でなくてはなりません． さらに，制約式の場合は整数条件を除いた許容領域が凸であることが必要です． また二次項がある場合には，目的関数か制約式かで LP ファイルの書き方が若干変わります． 「LP ファイルで，二次の目的関数を表したい」「LP ファイルで，二次の制約式を表したい」 の項も参照してください． なお，0-1 変数の積に関しては，特別な前処理を施して任意の形の二次項が扱えるソルバーがあるようです． 「0-1 変数 x, y に対して，「z = x * y」に対応する 0-1 変数 z を使いたい」も参考にしてください． 　また，目的関数が凸二次関数（最大化問題の場合は凹二次関数）のはずなのに，数値誤差の影響で「凸でない」というエラーが出る場合があります． この場合，目的関数の係数を全て整数にスケーリングする，対角項の係数を微小に増加させる，新しい変数と制約式を導入して係数行列を疎にするなどの対策を試してみてください．

  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 とします．

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

    　最近のソルバーには，互いに相反する最小の制約集合を出力する機能がついていることがあります． この機能は，最適化問題が不能（実行不能，infeasible）な時に策を検討するだけでなく，LP ファイル生成のバグを取るのにもとても便利です． ただし，問題サイズを小さくしないと計算時間がかかるため，なるべく規模の小さな問題からテストするのがよいでしょう．

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

    　最適解が複数存在する場合，解が異なることはありえます． 最適値そのものが違っている場合は，おそらく分枝限定法を終了させる判定条件の問題です． 　なお，混合整数二次錐最適化問題 (MISOCO) など，制約式に二次項を含む整数最適化問題は数値誤差に弱く，ソルバーが間違った解を最適解として返してくることがあります． これには決定的な対策はないのですが，可能ならば複数のソルバーなどでチェックするとエラーを減らすことができます．

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

    　まずは，得られた解を整数に丸めてみて，許容解がきちんと得られているかどうかを確認しましょう． 次に，big-M 法で巨大な定数を使っていないか確認してください． Big-M 法で必要以上に大きな定数を使うことは，数値安定性および計算速度を損ねます． なお，計算には誤差が含まれますので得られた結果を処理する際には注意が必要です． 例えば，0-1 変数としていても 0.000001 のような値が得られることがあるため，「int 型の 0 と比較する」というような処理は誤った結果を招くことがあります．

  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 ファイルの詳細な文法は，以下を参照してください．

  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 の書式などはソルバーごとに異なるため，別ソルバーへの流用は難しいのも確かです．

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

    　LP ファイルを一度ソルバーに読み込ませて，それから書き出すときれいに整形してくれます． 以下，整形したい LP ファイルの名前を test1.lp とします．

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

    　MPS ファイルとは，数理最適化問題を表すファイル形式の一種です． テキストファイルなのですが，人間の目ではあまり読みやすくはありません． ベンチマーク問題などは MPS 形式でアップロードされていることも多いです．

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

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

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

    　最小化問題の場合に凸二次目的関数，最大化問題の場合に凹二次目的関数が直接扱えるソルバーがあります．
    　目的関数において，線形項を先に書き，それに続いて二次項を + [ 2 x^2 - 4 x * y + 9 y^2 ] /2 のように書きます． 変数の 2 乗は ^2 を，クロス項には * を使います． また，係数は 2 倍して書き，二次項の全体を [ ] /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 する必要がないということです．

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

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

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

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

  12. Lazy Constraints を使いたい

    　ソルバーによっては Lazy Constraints が使えます． Lazy Constraints と定義された制約式は，最初は問題から取り除かれており，許容解が見つかるたびに問題に追加するべきかどうかチェックされます． 制約式の本数が膨大になってしまうが，実際にはそのうちのごく一部しか意味がないような問題で効果を発揮します．
    　以下では，LP ファイルで Lazy Constraints を扱う方法を説明します． そもそも制約式全体を LP ファイルに書ききるのが難しい場合や，動的に Lazy Constraints を追加したいような場合は，各ソルバーの API を利用するのが便利です． 詳細はマニュアルを参照してください．
目次へ戻る

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

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

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

    　定式化が良くない可能性もありますが，とりあえずソルバーのパラメータを調整してみる価値はあると思われます．

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

    　ソルバーのパラメータを調整するのが手っ取り早いと思われます．

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

    　以下のコマンドで，分枝限定法を 10000 秒で終了させられます． 数字を変えることにより秒数を自由に設定できます．

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

    　用途によっては，ユーザーが定めた閾値と同じかより良い目的関数値（最小化問題では閾値以下，最大化問題では閾値以上）を持つ許容解が得られれば十分な場合があります． 以下のコマンドで，定めた閾値と同じかより良い目的関数値の許容解が出たら，分枝限定法を自動的に停止するようにできます． 以下では閾値を 200 として説明しますが，数字を変えることにより閾値は自由に設定できます．

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

    　（質の良い）許容解を与えることにより，分枝限定法の高速化をねらいます． 特に，許容解が見つかりにくい問題では計算時間の短縮が期待できます．

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

    　上記の「最適解にこだわらないので，なるべく高速に質の良い解がほしい」「計算時間を制限して，分枝限定法を自動的に停止するようにしたい」「定めた閾値と同じかより良い目的関数値の許容解が出たら，分枝限定法を自動的に停止するようにしたい」「許容解を与えた状態で分枝限定法をスタートしたい」を組み合わせて使うと良いと思われます．

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

    　最近のソルバーはかなり賢くなっているので，デフォルトの分枝順序はかなり高速です． 手作業による分枝順序の調整に多くの時間を掛けることはあまりおすすめしません． ただし，特定の変数を固定すると問題が著しく小さくなるなど，問題構造を詳しく知っている場合には分枝順序の手動指定が有効な場合もあります．

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

    　並列分枝限定法が実装されているソルバーでは，マルチコア CPU の利点を生かすことができます． あるいは，他のタスクの邪魔をしないようにスレッド数を減らすことも可能です．

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

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

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

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

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

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

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

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

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

    　ソルバーによっては，マルチスレッドで線形最適化問題を解くと，複数のアルゴリズム（単体法や内点法）を用いて計算し一番速く終了したものを出力します． このため，稀なケースですが，アルゴリズム間の計算時間の差異が微小なときは試行ごとに異なる最適解が出る可能性があるようです．
目次へ戻る

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

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

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

    　いくつかのソルバーでは，ソルバーが前処理した後の LP ファイルを見ることができます．

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

    　分枝限定法の可視化を行う際などは，ノード間の関係が必要になります．

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

    　原理的には可能です． ですが，最適解の個数は問題によっては非常に多くなりえます． 特に，変数間に対称性がある場合には容易に非現実的な数になります（事実上列挙しきれない）． したがって，小さな問題から試すのが得策です．

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

    　複数の問題を解く場合には，ログファイルを分けておくと便利です．

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

    　いくつかの方法がありますが，とりあえず OS のコマンドライン（Windows の場合はコマンドプロンプト）を用いて制御する方法を紹介します．

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

    　LP ファイルをコマンドライン・インターフェースで解く方法は，最も単純な方法です． 列生成法など，複数の問題の間で情報をやりとりする必要がある場合には，ソルバーの API などを用いるのが得策です． 各ソルバーのマニュアルおよびサンプルファイルを参照してください．

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

    　用途によっては，最適解以外の解も見たいことがあります．

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

    　ソルバーの変更したパラメータ設定を表示・保存する方法です．

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

    　読み込んだ問題について，変数の個数や制約式の本数を表示できます．

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

    　読み込んだ整数最適化問題について，その連続緩和問題（整数制約を取り除いた問題）を出力させることができます．

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

    　読み込んだ線形最適化問題について，その双対問題を出力させることができます．

  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 に，日本語でよくまとまった情報があります．

  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 をお読みください． 　なお，「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月，最終更新：2024年9月