システム/制御/情報，Vol. 50, No. 9, pp. 363–368, 2006

363||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||「堅く柔らかく…数理計画アプローチ再訪特集号」

解説

ここまで解ける整数計画
宮代 隆平* 松井 知己 †||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

1.

はじめに

的解法を用いる場合と比較して以下のメリットが考えられる．

近年の計算機パワーの増大により，様々な分野において以前には計算不可能であった大規模な問題が扱えるよ• 最適性の証明が得られる

うになっている．さらに数理計画の世界では，最適化ア

分枝限定法により，最適性の証明が（列挙の果てに）

ルゴリズムそのものがハードウェアの進歩に勝るとも劣行える．たとえば公平性を重視しなければいけない問題

らない速度で進化しており，最先端のアルゴリズムを実の場合，解が最適であることが非常に重要になる．

装した最適化ソルバーの性能は数年前に比べて飛躍的に• 下界／上界が出る

向上している．本稿では整数計画問題を取り上げ，ベン

実用的には，「これ以下／以上の目的関数値を持つ許容チマークを通して現在の最適化ソルバーの性能を紹介す

解は存在しない」という情報だけでも十分な場合がある．

る．また，整数計画モデルがうまく解けない場合のガイ

分枝限定法は線形緩和問題を利用しているので，計算がドを簡単に記す．
「整数計画を使おうと思うが，どのくら

終了しなくてもその時点での下界／上界の情報を得るこいの規模の問題まで解けるのかが知りたい」「以前に整とができる．

数計画問題としてモデル化したが，計算時間がかかりす• 問題が不能の場合

ぎた」という方に，本稿が参考になれば幸いである．

2.

発見的解法を用いていて許容解が見つからない場合，

整数計画モデル

まずはパラメータの調整・アルゴリズムの改良などを行

整数計画問題は，広い意味では「与えられた制約式おうのが普通だが，問題が不能だった場合には時間の浪費よび（一部に）整数条件がついた変数の下で，目的関数になってしまう．これに対して分枝限定法では，「問題の値を最適化する問題」であるが，通常は「与えられたが不能である」ということを（時間をかければ）確認で線形制約式および（一部に）整数条件がついた変数の下きる．

で，線形目的関数の値を最小化／最大化する問題」を考• プログラム開発が不要

える．例えば，全ての変数が 0 または 1 を取る 0-1 整数

整数計画問題それ自体はソルバーに解かせることにす

計画問題は以下の (1) 式で表される．

れば，自前でプログラムを開発する必要が無く，モデル

minimizec⊤ x

化に専念すればよいためトータルの時間が大幅に節約でsubject to

Ax ≥ b,きる．また，実際に解く問題が「最小化／最大化」では

x ∈ {0,1}n .

なく，「条件を全て満たす答えがあるか？」という形に(1)なっている場合も多いが，整数計画ソルバーをこの種のなお本稿では誌面の都合上，整数計画法そのものの詳細問題に対する探索プログラムとして用いることももちろ

な解説は行わない．整数計画法については [14,21,24], 線

ん可能である．

形計画法については [15] を参照のこと．

それでは，解きたい問題を整数計画問題としてモデ

さて，いま手元に解かなければいけない最適化問題がル化することにしよう．現在，ほぼ全ての整数計画ソルあるとする．もちろんこの問題が解析的に解ければうれ

バーは，緩和問題として線形計画問題を利用している．

しいが，通常扱う問題は NP-困難なことが多いはずだ．

したがって，整数計画モデルを立てる際には，線形制約

これに対しては，発見的解法を実装するか，整数計画問

式・線形目的関数でなくてはならない．こう書くとかな

題としてモデル化しソルバーに解かせるなどのアプロー

り限定されているようだが，一見異なるクラスの問題も，チがある．整数計画法を利用するアプローチには，発見

変数の追加・式の変形により整数計画モデルとして定式
化できる．

∗

東京農工大学 大学院共生科学技術研究院†
中央大学 理工学部情報工学科

例えば，工業製品の誤差評価などの場面などにおい⊤⊤て，複数の目的関数 c⊤1 x, c2 x, ..., ck x があるとき，こKey Words : integer programming, software, benchmark– 33 –

システム/制御/情報 第 50 巻 第 9 号

364(2006)

れらの最大値を最小化したい場合がある．このような分枝戦略，カットなどの各種アルゴリズムの進歩，およmin max 形の目的関数は，新しい変数 z および制約式⊤⊤c⊤1 x ≤ z, c2 x ≤ z, ..., ck x ≤ z を追加して，目的関数 z

びベースとなる単体法の高速化によってもたらされたもを最小化することにより，線形不等式系で表すことがでては [16,2–4] が詳しい．
）次節では，ベンチマーク問題をきる．同様にして，最小値の最大化も線形不等式系で表通して整数計画ソルバーが現時点でどのくらいの規模の現できる．また，絶対値（の和）の最小化を目的関数に入問題を扱えるのか紹介する．

のである．
（線形計画法・整数計画法の発展の歴史についれることができる．例えば |x1 | + |x2 | + ··· + |xn | を最小整数計画問題のベンチマーク

化したい場合は，変数 z1 ,z2 ,...,zn を導入し，−zi ≤ xi ≤3.

zi (i = 1,2,...,n) という制約のもとで，z1 + z2 + ··· + zn

ここでは整数計画問題のベンチマークとして，ベンを最小化すれば良い．残念ながら，絶対値の和の最大化

チマークセット MIPLIB 2003[1] を最新の整数計画ソは定式化が困難である．以上は，整数変数を含まない線ルバーで解いた結果を記す．今回の実験では，MIPLIB

形計画問題についても適用できる．

2003 に用意されている 60 問のうち，「商用ソフトで 1 時
間以内に解けるクラス」に分類されていた 28 問につい整数変数は，離散的な値を取る事象のモデル化に使て実験を行った．

用する他に，その離散性を利用して定式化のトリックに使うことができる．例えば，0-1 変数は「制約式のス計算には，Windows XP (CPU: Pentium 4, 2.8GHz,

イッチ」の役割として用いることができる．非負の連続数 y1 , y2 , ..., yn および十分に大きな定数 M を導入する

RAM: 1024MB) 上の整数計画ソルバー ILOG CPLEX
10.0[13] (2006 年 1 月リリース) を使用した．なお比較のために，ILOG CPLEX 9.0/8.1/7.0 (それぞれ 2003 年
12 月／ 2002 年 12 月／ 2000 年 10 月リリース) も使用した．CPLEX のパラメータ設定は，基本的にデフォルト

ことにより以下の (2) 式として定式化できる．

のまま計算させた1 ．

変数 x1 , x2 , ..., xn を，制約条件 Ax ≥ b の下で，制約式 xi ≤ di (i = 1,2,...,n) に違反する個数を最小化したい，という問題を考えよう．このような問題は，0-1 変

minimizesubject ton∑

第 1 表に，ベンチマーク問題の規模および計算結果を示す．各列は左からそれぞれ問題名，制約式の本数，変

yi

i=1

数の個数，そのうち整数変数の個数，行列 A に含まれる

x − d ≤ M y,

（単位：秒）を示している．数千変数／制約式の問題も実Ax ≥ b,

非零要素の数，CPLEX 10.0/9.0/8.1/7.0 での計算時間x ≥ 0,y ∈ {0,1}n .

用的な時間で解けており，また概して難しい問題に対し(2)ては大幅なスピードアップが見られ，最適化アルゴリズ
ムの進化が窺える．
（一部の問題では，新しいソルバーの

このように，大きな定数を用いる定式化の手法を big-M

方が遅くなっているが，これは分枝順序などの差異によ法と呼ぶ．big-M 法を用いると，さまざまな論理関係がるものである．
）現在もアルゴリズムの改良は続いてお定式化できるが，M を選択する際にあまりに大きな値

り，古いベンチマーク問題はどんどんベンチマークとしを用いると数値計算の面で不安定になるので，定数 Mての用を成さなくなっている．

は制約式の意味を変えない範囲でなるべく小さいものを

なお第 1 表に示した計算時間は，「最適解が求まり，な選択するのが良い．

おかつその解が最適であると証明できた」ところまでの

その他，非線形制約式なども人工的な変数を導入する

計算時間である．実用上では，「最適かどうかはともかくと線形制約式に書きなおせる場合があり，様々なクラスの問題を整数計画モデルとして表すことが可能である．
これら定式化の様々なテクニックについては [17,20] な

質の良い解を求めたい」というケースが多く，この場合はさらに大規模な問題まで扱える．第 2 表は，第 1 表の CPLEX 10.0 で 100 秒以上かかったベンチマーク問

どを参照してほしい．

題について，最適解が見つかった時点までの計算時間をさて，解くべき問題を整数計画問題としてモデル化し示したものである．最近のソルバーは，質の良い解を高たのはよいが，はたして現実的な時間内に答えを求めら

速に見つける能力が非常に高くなっており，最適解は計れるのだろうか．定式化の結果として数千変数，数万変

算の早い過程で見つかり，その最適性を証明するのに計数の問題になってしまった場合，10 年前までは実質的に算時間の大部分を要するという状況が増えてきているが，別のアプローチを考えざるを得なかった．しかし現在の第 2 表からもそれがわかる．

最適化ソルバーは，以前と比較にならないほど巨大な問また，各種ソルバーの設定パラメータ（カット生成，

題を解くことができ，toy problem だけでなく実務上の分枝戦略など）を調整することにより，問題がより高速最適化問題が次々に解決されている．たとえば分枝限定

1

法は，10 年前と比較するとハードウェアの進歩を除いたベンチマーク問題 manna81, opt1217 に対してのみ，

Gomory cut と mixed integer rounding cut を多数生

うえで 1000 倍以上高速になっているが，これは前処理，– 34 –

成する設定にした．

宮代・松井：ここまで解ける整数計画

第1表

365

ベンチマーク問題の規模と計算時間（計算時間の単位：秒）

問題名

制約式

変数

整数変数

非零要素

CPLEX 10.0

CPLEX 9.0

CPLEX 8.1

CPLEX 7.0

10teams
aflow30a
air04
air05
cap6000
disctomfiber
fixnet6
gesa2
gesa2-omanna81
mas74
mas76
misc07
mod011
modglobmzzv11
mzzv42znw04
opt1217
p2756
pk1
pp08a
pp08aCUTS
qiu
rout
set1ch
vpm2

230
479
823
426
2176
399
363
478
1392
1248
6480
13
12
212
4480
291
9499
10460
36
64
755
45
136
246
1192
291
492
234

2025
842
8904
7195
6000
10000
1298
878
1224
1224
3321
151
151
260
10958
422
10240
11717
87482
769
2756
86
240
240
840
556
712
378

1800
421
8904
7195
6000
10000
1254
378
408
720
3321
150
150
259
96
98
10240
11717
87482
768
2756
55
64
64
48
315
240
168

12150
2091
72965
52121
48243
30000
2944
1756
5064
3672
12960
1706
1640
8619
22254
968
134603151261
636666
1542
8937
915
480
839
3432
2431
1412
917

29.2
39.6
25.5
23.5
0.9
58.0
0.5
1.3
0.5
4.3
0.6
1380.5
154.4
17.4
92.7
0.2
495.6
97.5
40.9
0.4
0.5
120.9
1.2
3.3
64.4
127.8
0.7
1.2

7.8
81.5
27.3
29.1
0.5
777.7
0.3
0.4
0.5
3.9
0.6
1699.4
85.2
78.2
101.2
0.5
787.9
90.9
28.0
5.6
0.6
106.5
1.6
2.4
209.9
2800.6
0.8
0.8

4.9
191.2
44.0
31.8
2.0
1044.3
0.4
0.3
1.3
1.4
0.5
1855.1
110.3
97.9
983.3
0.5
10000<
10000<
23.3
10000<
0.5
203.0
1.3
4.5
120.9
3412.1
0.9
1.0

6.4
142.2
72.4
57.6
6.4
8989.9
0.6
0.3
0.9
1.2
0.5
1424.792.8
87.9
failure0.4
10000<
10000<
8.1
10000<
0.6
102.9
1.4
2.7
728.8
673.2
0.6
6.4

第2表

が小さくても難しい問題1 もある [6]．問題の難易度を決

最適解発見までの時間（単位：秒）

問題名

総計算時間

最適解の発見

mas74
mzzv11
mas76
rout
pk1

1380.5
495.6
154.4
127.8
120.9

9.9
434.1
0.6
90.9
12.5

めるのは，行列 A の形や変数の形式（0-1 変数か，一般の整数変数か，または連続変数も含むか），さらに「線形緩和問題が元の整数計画問題にどのくらい “近いか”」である．同じ最適化問題を表している整数計画モデルでも，上記のような定式化の良し悪しにより解けるスピー
ドは劇的に変化する．残念ながら（問題が本質的に難しい場合や）モデル化がよくない場合には，解ける問題のに解けることもある．どのパラメータの調整が有効かは，
問題構造に対する深い洞察が必要なことが多く，試行錯

サイズはまだそれほど大きくなく，数百変数くらいで行き詰まってしまうことも珍しくはない．次節では，定式化した問題がうまく解けない場合のガイダンスを示す．

誤になってしまう場合も多々あるが，求解速度が大きく市販されている最適化ソルバーは数多くの種類が変わる場合もあるので試してみる価値はある [2,5]．
では実用的には，ソルバーはどの程度の問題まで解あるが，数理計画の分野では商用ソフト CPLEX[13],けるのだろうか？今回扱ったベンチマーク問題では，変XPRESS-MP[8] などがよく用いられている．国産では
NUOPT[23] などのソフトウェアがある．商用以外のソ数の個数・制約式の本数ともに 1 万を超えているベンチマーク問題 mzzv42z も 100 秒未満で解けている．ただ1

し第 1 表からもわかるように，問題の難しさは単純に変

例えば，MIPLIB 2003[1] の timtab2 というベンチ
マーク問題は制約式が 294 本，変数が 675 個の問題であるが，未だに最適解がわかっていない．

数の個数や制約式の本数で決まるわけではなく，サイズ– 35 –

システム/制御/情報 第 50 巻 第 9 号

366(2006)

フトウェアも，GLPK[11,12], lp solve[19] ほか多数ある

第4表

が，整数計画法に関しては商用ソフトウェアの方がまだ圧倒的に高性能である．ソフトウェアの機能についてのサーベイは，[5,10,18] などが参考になる．なお，最近の整数計画ソルバーでは線形制約・線形目的関数以外の整数計画問題（例えば凸 2 次制約／凸 2 次目的関数）を扱えるものもあるが，当然ながらこれらはより難しい問題

ケース別ガイド

最適解発見 早い最適解発見 遅い

緩和問題のCase 1Case 2

性能が良い

多最適解の解消

許容領域の拡張

緩和問題のCase 3

Case 4

性能が悪い

制約の追加

許容領域の拡張

変数の一部丸め

あきらめる？

となり，大きなサイズの問題を実用的な時間で解くのはまだ困難である．しかし，最適化アルゴリズムの進化が早いため，ソルバーが扱える問題サイズがさらに拡大し変数の個数である．もし全ての変数が 0 または 1 になっていくことは間違いないだろう．

ていれば，もちろんこれは元の 0-1 整数計画の最適解となっている．さて，0-1 変数全体のうち，0 または 1 と4.

早分かりガイドなっている変数が，変数全体に対し何%くらいを占めているかを見てみよう．

整数計画問題を最適化ソルバーで解いてみたとき，思うような性能が得られなかったらどうするのか？例えば，(a-1) 0 または 1 となっている変数の個数が 10%以下だ．

本当に解きたい問題の前に小さなモデルでテストしたと

このようなときは，問題自体が非常に難しいことを覚ころ，商用の最適化ソルバーで数時間かかってしまった

悟したほうが良い．以下に記すいくつかの方法を少した場合などである．本節ではそんなときの典型的な手続き

めしてみて，顕著な改善が見られないならば，適当なとを，個人的な経験と勘に基づいて簡単に記してみる. 以

ころで見限って「(1) あきらめる」に戻った方が良い．モ

下の記述は，最適化ソルバーの急速な進歩からすると，

デルの改訂や問題の分割を行う際は，0 または 1 となっ数年後には見当違いの事となっている可能性もあるのでている変数の個数が増加するように行うのが得策だが，注意されたい.

具体的な方法は個々の問題に大きく依存する．

問題が思うようなスピードで解けないときの解決法は，大きく分けて以下の 2 つがある．

(a-2) 0 または 1 となっている変数の個数が 90%以上だ．
このような場合，通常は速く解けることが多いのだが，(1) あきらめる

なぜか時間がかかっているというのは，何か難しい構造

あきらめが肝心なときもある．ここで言う「あきらめが一部に隠れていることが多い．整数になっていない変る」とは，数からなる問題を想定して，それがどんな問題なのか改• 新たに仮定等を導入してモデル自体を改訂する• 元の問題をより小さな問題に分割する• 発見的解法を作ることにする• とりあえず計算機を走らせておいて，めて考える必要があるだろう．例えば，巡回セールスマン問題，最大カット問題，p-センター問題など，典型的な難しい問題（に良く似た構造）が隠れていないか確認
し，それぞれの解法において成功している制約式を導入

整数計画法に詳しい人を探しにいくする必要がある．ちなみに，線形緩和問題の最適解で 0などがある．

または 1 になっている変数の値は，元の整数計画問題の最適解で同じ値を持つとは限らないことに注意されたい．

(2) あきらめない
もちろん簡単にあきらめてはいけない．そんなときは(a-3) それ以外のときは，以下に進もう．

第 3 表の手順で状況の改善を図るのが良いだろう．ただ(b) 最適解発見までの時間を見る

し以下では，0-1 整数計画で非負関数の最小化を目的に最適解発見までの時間が，総計算時間の何%になって持つ問題を扱っているとする．
第3表

いるかを確認する．25%を超えていたら，遅い方と思った方が良い．

基本的なチェック項目(a) 線形計画緩和問題の最適解を見る(b) 最適解発見までの時間を見る(c) 緩和問題の性能を見る(c) 緩和問題の性能を見る
線形緩和問題の最適値が，元の整数計画問題の何%くらいになっているかを確認する．70%以下だったら，線形緩和問題の性能が悪いと思った方が良い．
上記の 2 つのデータから，4 通りの場合（第 4 表参照）

(a) 線形計画緩和問題の最適解を見るがあるが，これらの典型的な状況を挙げよう．

ほとんどの最適化ソルバーでは，線形緩和問題を内部で解いている．近年は線形計画問題は非常に高速に解け

Case 1: 最適解発見は早い，線形緩和問題の性能は良い．

るので，通常は問題ないはずだ．ここで注目するのは，

これなら計算時間がもっと短くてもよいのに？と思う

線形緩和問題の最適解において 0 または 1 となっているケースである．このような事態は，最適解が異常にたく– 36 –

宮代・松井：ここまで解ける整数計画

367

さんある時によく起こる．その理由と対策は以下のよう値）をとっている変数を，それぞれ 0 または 1 に丸めて，なものである．

問題のサイズを縮小して最適化ソルバーで解いてみるのも良い．あるいは単に切り上げるのではなく，ランダム(i) 目的関数が無い：

丸め法を繰り返し適用するのも良い．これは，緩和問題「許容解を求めれば良い問題だから」といって目的関数を作っていないと，総計算時間の増加を確実に招く．
あっても無くても良いなら，目的関数は必ず入れよう．
何でもいいなら，係数は整数乱数を使うのが良い．

での最適値を確率だと思って（いくつかの変数を）0 ま
たは 1 に丸め，（残った変数からなる）得られた問題を最適化ソルバーにかけるというものである．
（例えば変数 x1が，線形緩和問題の最適解で 0.8 という値になっていた(ii) 目的関数の係数がすべて 1 である：

ら，0.8 の確率で x1 の値を 1 に固定し，0.2 の確率で x1

よく誤解されるが，目的関数の係数がばらばらな値のの値を 0 に固定する．
）許容解が少ない場合は，このよう方が一般に速く解ける．何か意味をつけて目的関数の係な丸め法は，変数を固定してできる問題が不能となって数をいろんな値にし，最適解の個数を絞り込むのが良い．

しまうことが多いため残念ながらうまく働かない．

論文等の計算実験では，人工的な問題として目的関数のまた変数の間に対称性がある場合，線形緩和問題の性

係数を (整数) 乱数で生成している場合も多いが，これを能はかなり悪くなる．このような時は x1 ≤ x2 ≤ ··· ≤ xn

0 または 1 にすると突然総計算時間が極端に増加することは珍しくない．
「すべて 1」がどうしても必要なら，乱のように変数に無理やり区別をつけてやり，対称性を除去するべきである．どの変数の間に対称性があるかの判数を使って係数を摂動するという方法がある．摂動した断は一般には難しいため，数式を見るよりモデル化の時際は，目的関数の係数を適当にスケーリングして全て整点から無くすように注意するのが得策である．

数にしておいた方が良いこともある．

Case 4: 最適解発見は遅い，線形緩和問題の性能は悪い．
非常に状況が悪いため「(1) あきらめる」に戻ったほ(iii) 目的関数が min max 形である：
前述した min max 形の目的関数は，実は総計算時間

うが良いかもしれない．とりあえず，以下の事項を見直の増加を招くのでなるべくなら扱わないほうが良い．典してみよう．

型的な例が min max 形の目的関数を持つ p-センター• 許容解は本当に使えるか？

問題であろう．良く似た設定で，目的関数が単純な p-

実際に現実問題のモデル化を請け負って，最適解を求

メディアン問題の方がずっと容易に解けることが知らめると「こんな答えでは使えない」となることがしばし⊤⊤れている．複数の目的関数値 c⊤
1 x, c2 x, ..., ck x を均等

ばある．これは，モデル化の際の「制約条件の洗い出し」にしたいなら，最大値の最小化ではなく，絶対値の和が不十分なために起こる．時間をかけて最適解を求める⊤⊤|c⊤1 x| + |c2 x| + ··· + |ck x| の最小化を目的関数にする

前に，許容解を見て制約式が不足していないか確認したことを勧める．

方がよい．制約式を追加すると，計算時間が劇的に変化

Case 2: 最適解発見は遅い，線形緩和問題の性能は良い．
このような状況は，許容解が非常に少なく，問題が不することはしばしばある．

• 問題から得られる知見は全て使っているか？

能になりやすいとき起こることが多い．本質的にはモデモデル化の際に，「この制約式は，これまでに作った制ルを見直す必要があるが，以下のような方法がうまくい約式を満たしていれば自動的に満たしているはず」といく場合もある．まず制約式を見直し，必ず満たさねばな

うような場合でも，とりあえず追加しておくことを奨めらない制約 (hard constraints) と，できれば満たして欲る．これは，整数条件を含んだ世界で許容領域が同じでしい制約 (soft constraints) に分ける．その上で「できも，線形緩和した場合には許容領域が異なることがある

れば満たして欲しい制約」を緩和する．モデルを変更しからである．また，ソルバーによるカットの生成を促すて良いなら，制約が等式 a⊤ x = b ならその代わりに制約b − ε ≤ a⊤ x ≤ b + ε とするのも良いだろう（ただし ε は適当な小さな正数である）．新しい変数 z と罰金係数 θ を導入し，例えば制約が等式 a⊤ x = b ならば，その代わりに制約 b − z ≤ a⊤ x ≤ b + z を入れ，目的関数に新たな項+θz を加えるという方法もある．
（制約が不等式 a⊤ x ≥ b
ならば，その代わりに制約 a⊤ x + z ≥ b を入れ，目的関数に新たな項 +θz を加える．
）

意味もある．冗長な制約式はたいていの場合問題になら

Case 3: 最適解発見は早い，線形緩和問題の性能は悪い．

も強力になっているため（[7,9] など），あらかじめ知っないので，思いついた制約式は全て入れるくらいのつもりでもよい．
また，問題に対して持っている先験的な知識（暫定解，上界／下界値ほか）は無いだろうか？例えば，ある変数群を固定すると問題が著しく縮小されるような場合，それに含まれる変数から分枝する分枝順序を導入してみるとよい．最近では許容解から別の許容解を見つける手法

線形緩和の性能を上げるために，何か新しい不等式制ている許容解を与えてやると良いこともある．

約を見つけて加える必要がある．もし最適性を犠牲にして良いのなら，緩和問題の最適解で 0 または 1（に近い– 37 –

システム/制御/情報 第 50 巻 第 9 号

368

5.

おわりに

数理計画の分野では，整数計画法はもちろん重要な研究対象の一つであるが，それ以外の研究分野においても，整数計画を用いた最適化が加速度的に普及している．例
えば，四色定理に関連したグラフ理論の問題が，整数計画法を用いて解かれている [22]．また，工場の生産現場などでは従来から最適化が行われてきたが，顧客からの受注に合わせて即時に生産計画を再最適化するといった「オンライン最適化」も，既にたくさんの実施例が報告されている．これからはどのような分野においても，最適化問題に対する整数計画のモデル化は，必ず試してみるべき手段の一つになっていくのではないだろうか．
（2006 年 4 月 12 日受付）

参 考 文 献[1] T. Achterberg, T. Koch, A. Martin: MIPLIB 2003;
Operations Research Letters, Vol. 34, No. 4, pp. 361–
372 (2006) http://miplib.zip.de/[2] R. E. Bixby: MIP: Theory and practice — closing the gap; Conference and Research Papers, ILOG
(2000) http://www.ilog.com/products/optimization/tech/research/mip.pdf[3] R. E. Bixby: Solving real-world linear programs: adecade and more of progress; Operations Research,
Vol. 50, No. 1, pp. 3–15 (2002)[4] R. E. Bixby, M. Fenelon, Z. Gu, E. Rothberg, R.
Wunderling: Mixed-integer programming: a progress
report, The Sharpest Cut (M. Grötschel ed.), SIAM,
pp. 309–327 (2004)[5] A. Atamtürk, M. W. P. Savelsbergh: Integerprogramming software systems; Annals of Operations
Research, Vol. 140, No. 1, pp. 67–124 (2005)[6] G. Cornuéjols, M. Dewande: A class of hard small
0-1 programs, Integer Programming and Combinatorial Optimization: 6th International IPCO Conference, R. E. Bixby, E. A. Boyd, R. Z. RiosMercado (Eds.), Lecture Notes in Computer Science,Vol. 1412, Springer, pp. 284–293 (1998)[7] E. Danna, E. Rothberg, C. Le Pape: Exploring relaxation induced neighborhoods to improve MIP solutions; Mathematical Programming, Series A, Vol. 102,
No. 1, pp. 71–90 (2005)[8] Dash Optimization: Xpress-MP;
http://www.dashoptimization.com/[9] M. Fischetti, A. Lodi: Local branching; Mathematical Programming, Series B, Vol. 98, Nos. 1–3, pp. 23–
47 (2003)[10] R. Fourer: Linear programming — software survey;
OR/MS Today, Vol. 32, No. 3, pp. 46–55 (2005)
http://www.lionhrtpub.com/orms/orms-6-05/
frsurvey.html(2006)

http://www.lionhrtpub.com/orms/surveys/LP/
LP-survey.html[11] GLPK (GNU linear programming kit);
http://www.gnu.org/software/glpk/glpk.html[12] Glpk for windows;
http://gnuwin32.sourceforge.net/packages/glpk.htm[13] ILOG: CPLEX; http://www.ilog.co.jp/[14] 今野浩，鈴木久敏：整数計画法と組合せ最適化；日科技連 (1982)[15] 今野浩：線形計画法；日科技連 (1987)[16] 今野浩：役に立つ一次式 — 整数計画法「気まぐれな王女」の 50 年；日本評論社 (2005)[17] 久保幹雄，田村明久，松井知己（編集）：応用数理計画
ハンドブック；朝倉書店 (2002)[18] J. T. Linderoth, T. K. Ralphs: Noncommercial Software for Mixed-Integer Linear Programming, Integer
Programming: Theory and Practice (J. Karlof ed.),CRC Press, pp. 253–303 (2005)[19] Lp solve; http://groups.yahoo.com/group/lp solve/[20] 森雅夫，松井知己：オペレーションズ・リサーチ（経営システム工学ライブラリー 8）；朝倉書店 (2004)[21] G. Nemhauser, L. Wolsey: Integer and Combinatorial Optimization; Wiley-Interscience (1999)[22] G. Pataki, S. Schmieta, S. Ceria, M. Ferris, J. Linderoth: Seymour is solved!;
http://www-unix.mcs.anl.gov/metaneos/seymour/[23] 数理システム：NUOPT;
http://www.msi.co.jp/nuopt/[24] L. Wolsey: Integer Programming; Wiley-Interscience(1998)

著 者 略 歴みや しろ

宮 代

りゅう へい隆 平 (非会員)
2004 年 3 月東京大学大学院情報理工学系
研究科数理情報工学専攻博士課程修了．同
年 6 月東京農工大学大学院共生科学技術研究部助手となり現在に至る．組合せ最適化の研究に従事．博士（情報理工学）．オペ
レーションズ・リサーチ学会などの会員．

まつ

い

松 井

とも

み

知 己 (非会員)
1990 年 3 月東京工業大学大学院 総合理
工学研究科システム科学専攻博士後期課程修了. 同年 4 月東京理科大学理工学部経営工学科助手. 1992 年 4 月東京大学工学部
計数工学科講師. 1996 年 4 月東京大学大学
院工学系研究科計数工学専攻助教授. 2006

年 4 月中央大学理工学部情報工学科教授となり現在に至る.
組合せ最適化の研究に従事．博士（理学）．オペレーション
ズ・リサーチ学会などの会員．

– 38 –