整数計画問題に対する分枝カット法とかソトの理論
藤江 哲也…仙川‖…l‖‖‖‖‖‖‖‖＝＝‖‖‖＝‖‖‖＝‖‖‖‖＝‖‖‖‖‖‖＝‖‖＝‖‖‖‖‖‖＝‖＝＝‖‖＝＝‖‖‖＝＝‖‖‖‖‖‖‖‖＝‖＝‖‖＝‖‖‖‖‖‖＝＝＝‖＝‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖＝‖‖＝＝＝‖＝‖＝‖‖‖＝‖‖‖＝‖‖＝＝‖‖‖‖＝＝‖‖＝＝＝‖＝＝＝‖‖‖＝‖州

ルゴリズムとしての様々な工夫（技法）がまとめられ

1．はじめにている（その一部は次節で取り上げる）．これは【生分枝カット法は，分枝限定法に切除平面法を組み込成される子問題数】の減少に関する貢献とみることがんだ解法である（これら解法の概略は次節で取り扱できる（親問題の情報を利用して子問題の線形計画緩う）．近年，この分枝カット法の進歩によって，かな

和問題を解く，といった【子問題を解く時間】に関す

り規模の大きい整数計画問題が解けるようになっている技法もある）．1982年に刊行された文献［16］では，る．中には，小規模でありながら解くことが非常に難

その当時までに提案された技法についてまとめられてしい問題も存在する（例えば文献［8］）が，一般にはいる．そしてその多くが，現在においても【生成され数千〜数万変数の問題が扱えるようになった．まず，る子問題数】の減少に重要な役割を演じており，特にこのように進展してきた理由を考えることにする．

近年の計算機環境や線形計画ソルバの進歩によって実分枝限定法・分枝カット法の計算時間を，かなり大用レベルでの重要性が認識されるようになった．線形計画ソルバの進歩は，文献［16，第6章］や文献［15］で雑把に【生成される子問題数】×【子問題を解く時間】

取り上げられている切除平面法，特にカット生成が実とする（厳密な議論については文献［12］を参照された

用的になった要因にもなり，現在のような分枝カットい）．近年，規模の大きい整数計画問題が解けるよう法の進展につながったと言える．

になった背景に，ハードウェアの進歩を含む計算機環

別の見方をすると，整数計画ソルバのベースとなる境の劇的な変化があったことはもちろんである．この技術は新しいものばかりではなく，文献［15］や文献

変化は【子問題を解く時間】の減少に貢献し，よって［16］に既に現れているものも多いわけである．筆者の規模の大きい問題が解けるようになったものと理解で私見では，このことはあまり認識されていないようできる．また，特にここ数年来の線形計画ソルバの進歩

ある．整数計画問題は一般にNP困難であり，【生成も無視することはできない．整数計画問題に対する分される子問題数】減少の技法について理論的な評価を枝限定法や分枝カット法の計算は，その大部分を線形行うことは難しく，実験的な評価が重要となる．しか計画問題を解くことに費やされ，線形計画問題が高速し，技法が提案された当時と現在とでは計算機環境がに解けるようになれば，その分だけ【子問題を解く時

大きく異なるため，これら技法の（特に，当時は有効間】の減少に貢献する．線形計画ソルバの進歩についでないとされた技法の）再評価があってもよいはずでては，例えば文献［6］に述べられている．文献［6］によある．実際，現在成功をおさめているソルバは，これると，かつては数時間〜数日を要したが現在では数分

らの技法を積極的に取り入れている［1，7］．その一方あれば解けてしまう問題も少なくないようである．こで，文献［15，16］の刊行後，これら技法の改良・発展のような進歩が，大規模な整数計画問題を解くことにが続いている．そして，今後さらに【生成される子問つながっているのも明らかであろう（実用的な線形計

題数】減少の技法が重要になると思われる．本稿では，

画問題の解法について，日本語で書かれた本として文分枝カット法の入門として，その概略を説明し，その献［30］がある）．

中の重要な技法について紹介する．続いて，カットの一方，例えば文献［16，第4章］は，分枝限定法のア
ふじえ てつや神戸商科大学商経学部〒651−2197神戸市西区学園西町8−2−1
2003年12月号

理論を取り上げ，現在ソルバで使用されているカット（の一部）を紹介する．最後に，整数計画を扱った文献および整数計画ソルバを紹介する．最近の整数計画
ソルバは利便性においても向上している（文献［1］や© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（59）935

4節に挙げるURLを参照のこと）ため，今後，整数

トを追加することにより（LP）の強化を試みる．カ

計画問題の適用例・応用例がさらに増えることを期待

ットの追加は，各子問題についても行われる．このとしたい．

き，追加されるカットが，その子問題だけでなく元問

2．整数計画問題と分枝限定法，分枝カット法

題（MIP）に対して妥当なときglobalと呼ぶ．
（MIP）に対して妥当な不等式はすべての子問題に対しても妥当であるため，globalなカットはカットプ

紙面の都合上，概略のみを説明する．詳細についてールに保持され，これ以降の子問題の計算で使われる．
分枝カット法のプロトタイプは図1のようになるが，は，4節で紹介する文献を参考にされたい．

本節では，次の混合整数計画問題（mixedinteger
programmingproblem）を考える：

実装の際には，図1（a）〜（e）に対応した次の技法が重要となる．

（MIP） 最小化 cT∬（a）前処理（Preprocessing）：分枝かソト法や分枝限条 件 A∬≦あ，定法を実行する前に，前処理を実行することがあ∬ど∈Z（オ＝1，2，・‥，β）．

る．すなわち，冗長な変数／制約式の削除，変数の

ただし，決定変数エ＝（れ，裁，…，エ乃）Tは乃次元ベク

上下限制約の強化，LP緩和問題を強化するためトルである．また，Cは乃次元ベクトル，∂は椚次の係数行列Aの改善等である［28］．前処理は非常

元ベクトル，Aは∽×乃行列であり，カはカ≦乃を満に効果的であることが知られている［1，22］．文献

たす整数である．整数変数∬どの取り得る値が0また［17］では，元問題だけでなく各子問題に対して前は1の場合，すなわち0≦れ≦1（グ＝1，2，…，カ）が制約処理を行った効果について検証している．

式に含まれているとき，（MIP）は0−1混合整数計画（b）子問題の選択（Node selection）：探さ優先探索，問題と呼ばれる．

幅優先探索，下界値優先探索，ヒューリスティッ

ほとんどの整数計画ソルバで採用されている分枝限ク探索［22］等が知られている．また，ソルバによ

定法・分枝カット法では，（MIP）の線形計画緩和問っては，これらを組み合わせた探索方法を実装し題（以後LP緩和問題と呼ぶ）ている．

（LP） 最小化 cT上方（C）カット（Cut）：LP緩和問題を強化する意味で，

条 件 A∬≦∂

カットは重要である．これについては次節で取りを解く．（LP）の最適解を烹とする．もし，烹1，・‥，
ぁがすべて整数値をとれば，烹は（MIP）の最適解

分枝カット法；となる．いま，このような状況ではないとする．このbegin

とき分枝限定法（branch−and−bound algorithm）では，整数でないあを選び，（MIP）にみ≦Lあ」という制約を加えた子問題（MIPl）と，（MIP）にみ≧「あ1という制約を加えた子問題（MIP2）を生成する．
一方，切除平面法（cuttingplanealgorithm）では，新しい不等式の追加を試みる．（MIP）のすべての実行可能解∬に対してゐTJ≦γが成り立つときこれを妥当不等式（validinequality）と呼ぶ．また，妥当
不等式ゐTこr≦γを加えることによって（LP）の領域（a）（MIP）に対する前処理を実行；Z＊：＝∝）；（MIP）を子問題プール￡に入れる；
カットプールを空にする；

WhileL：≠￠dobegin（b）子問題プール￡から子問題gを選択する；￡からgを除去する；

カットプールに含まれる不等式をgに追加する；（c）切除平面法を実行する；（d）if2：＊より良い実行可能解が見つかったthen

が真に小さくなるとき，この不等式を切除平面または∬＊とz＊を更新する；かソト（cuttingplane，Cut）と呼ぶ．切除平面法では，（e）if新しい子問題が生成されたthen

烹を削除するようなカットを追加し，新しいLP緩和

それらを子問題プール￡に入れる

問題を作る．そしてそれを再び解く，という操作を繰り返す．分枝カット法（branch−and−Cut algorithm）
は，分枝限定法に切除平面法を組み込んだ解法であり，LP緩和問題（LP）を解いて終わるのではなく，カッ936（60）end；
return∬♯emd．

図1分枝カット法のプロトタイプ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

が任意の（∬，S）∈月pに対して成り立つ．一般に，実扱う．

数αに対して0≦α−Lα」＜1であり，また∬，S≧0で（d）ヒューリスティックス（Heuristics）：（MIP）に対する分枝カット法や分枝限定法では，実行可能解の更新は，LP緩和問題の最適解が整数解となあるから（uTA−LuTA」）x＋（u−Lu」）Tsった場合にのみ行うのが一般的である．しかし，−（〟T∂−L〟丁机）＞−1（2）

最近のソルバの中には，LP緩和問題に基づくヒが任意の（∬，ざ）∈Pふに対して成り立つ．また，（1）式ューリスティックスを組み込んでいるものもある．

より（uTA−LuTA」）x＋（u−Lu」）Ts−（uTb−LuTbJ）（e）分枝変数の選択（VariableseIection）：整数値をとらないあの選択によって，【生成される子問題数】＝−LuTAJx−LuJTs＋LuTb」

は大きく変化する．最大実行不可能性ルール

であり，（∬，5）∈月もに対して右辺は整数になるので左（maximuminfeasibility rule）はテキストでよく辺も整数でなければならない．よって（2）式より目にする方法である．より現実的な方法として，（uTA−LuTA」）x＋（u−Lu」）Ts

文献［16，第4章］では，疑似コストルール−（〟T∂一L〟T机）≧0（pseudo−COStrule）が紹介されている．また近年，∬Jを選択したことによって生成される子問題を，（3）は月らに対する妥当不等式となることがわかる．∫を消去すると（LuTA」−LuJTA）x≦LuTb」一LuJTb

そのLP緩和問題に対して数回ピボット操作を実（4）は月pに対する妥当不等式になる．

行することで評価する強分枝ルール（strong

LP緩和問題の最適基底解の情報を使うと，必ずそbranchingrule）が提案されている［2，14］．実験結果によると，一つの方法が他よりも優位になるの解を削除するように〟を決定することができる．

ことはないが，疑似コストルールが一般に有効のGomoryの小数カット［10］は，このようにして構成さようである［19，22］．

れるカットである．

3．1．2 混合整数計画問題に対するGomoryカット

3．カットの理論

ここで紹介するカットの導出方法は，文献［26］に基づいている．（MIP）の連続変数をyと書くこととし，

本節では，整数計画ソルバで使用されているカットの紹介を行う．そのすべてを紹介することはできない（MIP）の実行可能解集合が凡IP＝（（∬，y）∈Z♪×R〝

ため，興味を持たれた方は，4節で紹介する文献が参

lAJ＋β〝＝∂，∬，〟≧0）として与えられているとする．

考になると思われる．カットは，問題の構造に依存しふたたび，〟∈Rmを任意のベクトルとする．このとないものと依存するものに大別される．前者はき「（MIP）の制約式AJ≦∂」＋「変数の整数性」からカ〟TA∬＋〝リ）〟＝αT∂が任意の（∬，〟）∈凡IPに対して成り立つ．S⊆（1，…，ットを生成するものであり，所与の不等式系A∬≦∂から作られる．一方，後者は（MIP）の実行可能解集合を明らかにするものであり，所与の不等式系A∬≦∂の形によらない不等式を生成する．なお，本節の♪）を∬の添字部分集合とする．このとき（uTA−LuTA」）x−∑xj＋uTDy J∈5−（uTb−LuTbJ）＝−LuTAJx−∑xj＋LuTbJ

内容の一部は文献［9］でも取り上げている．

J∈5

3．1問題の構造に依存しないカット（5）は（∬，〝）∈凡IPに対して整数値をとる．よって，（5）式

3．1．1整数計画問題に対するGomoryカットの左辺は0以上または−1以下となる．簡単のため／

月p＝（∬∈Z乃IA∬≦∂，∬≧0）とする．ただし，A，∂＝uTA−LuTA」，ム＝uTbTLuTb」とおくと，このこの成分はすべて整数であると仮定し，スラック変数sとはを導入して月ら＝（（∬，ざ）∈Z乃×Z∽lA∬＋5＝∂，∬，5≧0）とする．Gomoryカットは，LP緩和問題の最適基底∑ノね−∑（1−￡）JJ＋αT上）れ≧ふ J∈」Ⅳ−5

ノ∈5解から生成されるが［15］，ここではより一般的な導出（6）

方法を紹介する．〟∈取∽を任意のベクトルとする．

0r ∑ノ元一∑（1一差）∬J＋〟T功≦−（1−ふ） J∈一Ⅳ−5

このとき〟TA∬＋〟T∫＝〟丁∂2003年12月号

J∈5に等しい．ここで変数の非負条件などを考慮すると，（1）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（61）93丁（6）式から∑ノね＋（〟Tヱ））＋針≧カ

ブ∈〃−5

0r

（7）

−∑（1−￡）み＋（αT上））■y≦−（1一九）
jeSeSが導かれる．ただし，（〟Tヱ））＋は〟Tβの負成分を0に置き換えたベクトル，（αTβ）−は〝丁βの正成分を0に置き換えたベクトルである．つまり（7）式は（6）式を緩めたものである．（7）式は

図2 カット（10）式∑ノね＋（α丁上））＋y≧ム

J∈〃−5

Or

〝≦皿＋了ち（8）ム
1一九（是（1一触−（〟サy）≧カ（10）は月に対する妥当不等式（図2の点輝）であり，点と変形できる．ここで二つの不等式には変数の重なり（0，∂）を削除している（（10）式は点（0，∂）を削除する離がないことに注意する．そこで，

接カットと見ることもできる）．次に（10）式の導出方法

α≧0かつβ≧0であってしかもα≧／orβ≧／をならば，α＋β≧／が成り立つ

凡IP＝（（∬，〝）∈睨×Z乃l∑覧．αノダJ≦占＋∬，∬，〟≧0）という事実を（8）式に適用することができ，に対して適用する．／＝∂−L∂」，ム＝αノーLαJ」（ノ＝1，…，〝）とし，S＝（ノl亮≧／）とおく．しαノ」≦勘であるか＝血＋丁重諸（ト伽 J∈〟−∫ら，＋（〟T勅一了曳（〟サy≧ふ（9）∑吼動＋ ∑ しαJ」批≦詫＋∬ノ∈5

は凡IPに対する妥当不等式となる．（9）式において，SをS＝（jlj；＞ふ）とおくのが最良である．Gomoryの混合整数カット［11］は，Sをこのように選び，αを

（11）

J∈〃−5

が任意の（∬，〟）∈凡Ⅰ。に対して成り立つ．（11）式を
是「αJl狛＋∑LαJ」仇≦診＋∬＋∑（1一兢J J∈〃一5ノ∈5と変形して，（10）式の導出方法を通用するとLP緩和問題の最適基底解に従って決定した不等式（9）「αJl仇十∑Lα血≦L∂」
J∈〃−5

である．

∬＋∑J∈5（1−カ）〝J

3．1．3 離接カットl−／LP緩和問題の実行可能領域をP＝（∬∈R乃IA∬≦∂）となる．これを整理するととする．LP緩和問題の最適解を烹とし，あが整数でないとする．このとき，苫：＝（Pn（∬lみ≦Lあ」））∪（P

計d＋彗≡㌢）狛≦L小一与n（∬lみ≧「あ1））は虎を含まない．よって，烹を削除が得られる．ただし，（α）十＝maX（α，0）である．（1カ式

する旦の妥当不等式が存在する．このようにして生をMIR（mixedinteger rounding）不等式と呼ぶ．

成されるカットを離接カット（disjunctive cut）とい

文献［20］では，多くの種類のカットがMIR不等式とう．離接カットはBalasらによって1970年代から研なることを示し，また数値実験によりMIR不等式の究が行われている［3］．また近年，Balas−Ceria−Cor−

有効性を示している．

nejoIsは0−1混合整数計画問題に対する1ift−andq

3．2 問題の構造に依存したカット

projectカットを提案し，これが離接カットと等価で3．2．1被覆不等式あることを示した［4，5］（日本語による解説として文まず，ナップサック問題の制約式を考える：

献［18］がある）．

／l∑αノみ≦∂，み＝00rl（ノ＝1，…，乃）

まず，月＝（（∬，y）∈RXZl〝≦∂十∬，J≧0）を考える．ただし，∂は整数でないとし，∂の小数部分を／938（62）3‖監

J＝1

3．1．4 MIRカット＝∂−L∂」とする．このとき，（1カ

ただし，αJ＞0（ノ＝1，…，乃）である．（1湖の実行可能解集合の凸包はナップサック多面体と呼ばれ，その不等式表現に関して多くの研究がある（詳細は文献［15，18，24，31］等を参照されたい）．例えば，C⊆（1，…，乃）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

に関して∑J。。αJ＞∂となるとき，∑J∈。こrJ≦匿ト1ては文献［1，18，22，31］が詳しい．また，カットのはナップサック多面体の妥当不等式である．被覆不等理論については新しいサーベイ論文［21］がある．次に式（coverinequality）と呼ばれる不等式は，この式

整数計画ソルバをリストアップする．まず，商用ソフを精密にしたものであり，さらにナップサック多面体

トウェアをアルファベット順に列挙すると，CPLEXの極大面を定めるための拡張も行われている．

（ILOG，Inc．）1，LINDO（LINDO Systems，Inc．）2，

含まれるならば，そこから待られる被覆不等式などを

NUOPT（㈱数理システム）3，OSL（IBM）4，SOPT（㈱サイテック・ジャパン）5，Ⅹpress−MP（Dash（MIP）のカットとして使うことができる．さらに，Optimization，Inc．）6等がある．また，フリーで入手

負の係数が含まれる場合，つまりできるソフトウェアとしてGLPK7，1p−SOlve8等があもし（MIP）の制約の中に（l却式の形をしたものがる．さらに，最近では分杖カット法およびその並列化∑吼み−∑α品≦∂，∬J＝00rl（ノ∈凡∪鵡）
J∈一Ⅳ2

J∈」Ⅳ1

に関するオープンソースプロジェクトCOIN（IBM）9（14）が活発である．なお，整数計画ソルバ（商用／フリー）（αJ＞0（ノ∈凡∪邦））という場合にも，ノ∈邦に関するの比較をMittelmannのホームページ10で見ることが∬Jを仇＝1−みに置き換えれば（l劫式の形になり，同様できる．

の議論ができる
3．2．2 フロー被覆不等式

参考文献

ここでは，次の集合を考える．

（J，〝）∈
Al−P＝

Z乃×R乃

［1］Atamtiirk，L．andSavelsbergh，W．P．：Commercial∑完動≦占，

integer programmlng SOftware systems，Research0≦狛≦吼吼（ノ＝1，…，乃），report BCOL．03．01，University ofCalifornia at Ber−み∈（0，1）（ノ＝1，…，乃）keley，2003．

被覆不等式と同様，∑J∈。αJ＞∂を満たすC⊆（1，…，［2］Applegate，D．，Bixby，R．，Chvatal，Ⅴ．andCook，W乃）をと り，ス＝∑J∈Cαノー∂＞0とする．また，

Finding cutsin the TSP，Technicalreport95−05，

maxJ∈。（わ＞スであるとする．このとき，

DIMACS，1995．

∑（ダブ＋（αノース）＋（1−み））≦∂（15）［3］Balas，E．：Disjunctive programming，AnnaLs

ノ∈C

は凡IPに対する妥当不等式である［25］，（拍式はフロ

ー被覆不等式（flowcoverinequality）と呼ばれるものの一種である．フロー被覆不等式はその後拡張され，カットとして広く利用され七いる．

βゐc柁′g肋fゐg∽α′才α，5，3−51，1999．

［4］Balas，E．，Ceria S．andCornuejoIsG．：Alift−and−project cutting plane algorithm for mixed O−1pro−
grams，Mathematical乃て哲7ummlng，58，295−324，1993・［5］Balas，E．，Ceria，S．andCornuejoIs，G．：Mixed O−1
programmingbyliftrand−prOjectinabranch−and−Cut

4．おわりにframework，Manqement Science，42，1229−1246，1996，

文献［9］と重複するが，最後に代表的な文献および［6］Bixby，R．E．：Solvingrea卜worldlinearprograms：
Adecadeandmoreofprogress，（砂emtions Resea7Th，

整数計画ソルバの紹介をする．

整数計画を扱った本として文献［12，15，16，18，
23，24，27，29，31］等がある．分杖カット法につい

50，3−15，2002．

［7］Bixby，R．E．，FenelonM．，GuandZ．，RothbergE
Wunderling R．：MIP：Theoryandpractice−Closing

1http：／／www．ilog．co．jp／products／cplex／
2http：／／www．1indo．com／
3http：／／www．msi．co．jp／nuopt／index．htm1

4http：／／www−3．ibm．com／software／data／bi／osl／index．
htIlllthegap，TechnicalReport，ILOGIncリParis，France，
1999．

［8］Cornu6joIs，G．andDawande，M∴A classofhard
Sma11integer programs，1NFORMS Joumal qf
Co〝ゆ〟Jわ曙，11，205−210，1999．

5http：／／www．saitechLinc．com／
6http：／／www．dashoptimization．com／
7http：／／www．gnu．org／software／glpk／glpk．htm1［9］藤江哲也：

8ftp：／／ftp．es．ele．tue．nl／pub／1p＿SOlve／［10］Gomory，R．E∴Outlineofanalgorithmforinteger

9http：／／www．coin−Or．Org／
10ftp：／／plato．asu．edu／pub／milpc．txt，ftp：／／plato．asu．edu／pub／milpf．txt
2003年12月号

混合整数計画問題に対する分枝カット

法 ，計測と制御，42，770−775，2003．
SOlutionstolinearprograms，Bulletinqfthe
肋Jゐe研αオブcαJSocブgれ64，275−278，1958．

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（63）939

［11］Gomory，R．E．：Analgorithmforthemixedinte−［22］Martin，A．：Generalmixedintegerprogramming：

gerproblem．RM−2597，TheRandCorporation，1960． ComputationalissuesforbranCh−and−Cutalgorithms．
［12］茨木俊秀： 組合せ最適化一分枝限定法を中心として−M．andNaddef，D．，eds．），LectunNotesin Con4）uter，講座・数理計画法8，産業図書，1981．

［13］茨木俊秀，福島雅夫： 最適化の手法，情報数学講座

5cグe乃Ce，2241，1−25，2001．

［23］Martin，R．K．： Large Scale Linear andInteger

14，共立出版，1993．

［14］ILOG CPLEX8．O Reference Manual．ILOGInc，
2002．

Optimization−A Unified Approach，Kluwer Aca・

demic Publishers，1999．

［15］今野浩： 整数計画法 ，講座・数理計画法6，産業図書，1981．

［24］Nemhauser，G．L．and WoIsey，L．： Integer andCombinatorialOptimization［16］今野浩，鈴木久敏（編）： 整数計画法と組合せ最適

MIPソルバーの試作

新技法の効果検証に有効なLPベース・，東京農工大学大学院工学研究科

1988．

Validlinearinequalities forfixed charge problems，（砂e和才わ乃ざ虎硲eαⅣゐ，33，842−861，1985．

［26］padberg，M．：Classicalcuts for mixedLinteger

電子情報工学専攻修士論文，2003．
［18］久保幹雄，田村明久，桧井知己（編）：，John Wiley＆Sons，［25］padberg，MリVan Roy，T．）．and WoIsey，L．A．：

化 ，日科技連出版社，1982．
［17］鴻池祐輔：

ンドブック

ComputationalCombinatorialOptimization（Jhger，

応用数理計画ハ，朝倉書店，2002．

programmlng and branch−and−Cut，〃eJゐ0ゐ〆（如澗如郡長ぬ妙所，53，173−203，2001．

［19］Linderoth，J．and Savelsbergh，M．W．P．：A［27］坂和正敏： 離散システムの最適化く一目的から多目
computational study of search strategies for mixed
integerprogramming，1NFORMSJournalon Comput−

的へ〉 ，森北出版，2000．

［28］Savelsbergh，W．P．：Preprocessing and probing
techniquesformixedintegerprogrammlngprOblems，Zク曙，11，173−187，1999．

［20］Marchand，H．andWoIsey，L．：Aggregation and0月艮4カ〟用αJo乃C川砂祓喝，6，445−454，1994．
mixedinteger rounding to solve MIPs．qemtions［29］Schrijver，A．： Theoryoflinearandintegerpro−
gramming

βgsβαⅣゐ，49，363−371，2001．

，JohnWiley＆Sons，1986．

［21］Marchand，H．，Martin，A．，Weismantel，R．and［30］反町洋一（編）：
WoIsey，L．：Cutting planes and mixedinteger pro−

線形計画法の実際

gramming，Disc柁teAj坤IiedMathematics，123，397−446， ［31］WoIsey，L．：
2002．

940（64），講座・数理計画

法3，産業図書，1992．
Integer Programming

Wiley＆Sons，1998．

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ，John