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

整数計画法による定式化入門
藤江 哲也
整数計画法の魅力の一つとして，定式化の表現力の高さがある．特にバイナリ変数 (0-1 変数) が重要な役割を果たす．本稿では，初学者を対象に，いくつかの例を通して定式化を示すとともに，注意すべき点について説明する．

キーワード：定式化，整数計画，線形計画，バイナリ変数，線形化

1. はじめに
本稿では，整数線形計画 (Integer Linear Program-ming : ILP)1 による定式化を扱う．
まずイントロダクションとして，ILP の典型的と思われる例題を 2 つ挙げる．例題 1 は，線形計画問題に「整数条件」が追加された形をしている．線形計画問題に触れたことのない方は，方程式の文章題を解くようなものと思って見てほしい．
例題 1.

図 2 (ILP1 ) の図示（破線）

図 1 (ILP1) の図示

A 社では，テーブルとチェアを製造販売しとができる．テーブルとチェアは整数個しか製造できている．それぞれ製造工程が 2 つあり，1 個 (1 卓，ないため，x1 , x2 に整数条件がつけられている．

1 脚) 当たりの所要時間および利益が次のように(ILP1)

与えられている．

最大化

Z = 4x1 + 5x2(総利益 Z 千円)

2x1 + 2x2

7

(工程 1 の所要時間),

3x1 + 5x2

14

(工程 2 の所要時間),

テーブル

チェア

2 時間

2 時間

工程 2

3 時間

5 時間

x1 , x2

利益

4 千円

5 千円

x1 , x2 : 整数

工程 1

条

件

0

(製造数は 0 以上),
(製造数は整数).

この会社で働く職人の関係上，工程 1 は 1 日 7 時(ILP1) から整数条件を除去すると線形計画問題にな

間，工程 2 は 1 日 14 時間とることができる．テーるが，これを (LP1) とする．(LP1) の最適解と最適値

ブルとチェアはすべて売れるものとした場合，利は x1 = 7/4, x2 = 7/4, Z = 63/4 = 15.75 であり，益を最大にするにはテーブルとチェアをそれぞれ(ILP1) の最適解と最適値は x1 = 1, x2 = 2, Z = 14

1 日当たり何個製造すればよいか．

である (図 1)． この例題では，(LP1) の最適解を，x1は切り捨て，x2 は切り上げると (ILP1) の最適解が得テーブルとチェアの製造数をそれぞれ x1 , x2 とする．

られる．しかし，問題が複雑になると，このように線

このとき，この最大化問題は次のように定式化するこ

形計画問題の解を見て ILP の解を求めることは一般に困難である．

1

混合整数計画 (Mixed Integer Programming : MIP) と同じ問題を指すが，「線形」を強調するために，本稿ではILP と表記する．

次の例題 2 は，バイナリ変数 (0-1 変数) を用いる問題である．ILP が高い表現力を発揮するのは，選択する／しないなどをバイナリ変数で表現できるためであ

ふじえ てつや兵庫県立大学大学院経営研究科〒 651–2197 兵庫県神戸市西区学園西町 8–2–1

る．3 節以降を見てもわかるように，バイナリ変数はILP による定式化において重要な役割を果たす．

c by ORSJ. Unauthorized reproduction of this article is prohibited.
190 （18）Copyright 

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

例題 2 (ナップサック問題).

高さを紹介することである．Dantzig による 1960 年

B 社では，予算 160(単位:百万円) を次年度の新規プロジェクトに計上している．ただし，候補となるプロジェクトは複数あり，予算の都合上すべてを採用することはできない．各プロジェクト (P1,. . .,P5) の NPV (正味現在価値) と予算 (いずれも推定値，単位：百万円) は次の通りである．

の論文 [2]（[3] にも収録）は，ILP の解法 (Gomory の切除平面法) が開発されたことを受けて，さまざまな問題が ILP として定式化できることを示したものであり，“We shall show that a host of diﬃcult, indeed

seemingly impossible, problems of a nonlinear, nonconvex, and combinatorial character are now open
for direct attack.” と述べている ([2], p. 30)．そし

P1

P2

P3

P4

P5

て，目的関数が非線形 (nonlinear) の問題，目的関数

NPV

17

16

14

10

8

や実行可能領域が非凸 (nonconvex) の問題，組合せ的

予算

60

50

40

30

20

な性質 (combinatorial character) をもつ問題 (組合

このとき，予算 100 を超えることなく， NPV のせ最適化問題) の定式化が紹介されている．これに加合計を最大にするには，どのプロジェクトを採用

え，ILP を使って問題を近似的に解くアプローチもあすればよいか．

る (3.3 節)．

ILP はこのようにさまざまな問題をカバーするとはいえ，「ILP として定式化できる」=「整数計画ソル
変数 xj を，プロジェクト j を採用するとき 1，しない

バーで解ける」であることに注意しなければならない．

とき 0 を示すバイナリ変数とする．このとき，この問

特に，変数や制約式の数が膨大になる場合はもちろん，

題は次のように定式化することができる．

定式化に非常に大きい数 (big-M) が含まれる場合も注意が必要である (2 節を参照)．このような場合，big-M(ILP2)
最大化

Z = 17x1 + 16x2 + 14x3 + 10x4 + 8x5(NPV の合計)

条件

60x1 + 50x2 + 40x3 + 30x4 + 20x5100

(予算の合計),x1 , . . . , x5 = 0 または 1.

で表現せず元の表現の特徴を使った解法を適用するのが妥当なこともある (制約プログラミング (constraint

programming) との融合は，このアプローチである)．
それでも，整数計画ソルバーおよび計算機パワーが急速に進歩し続けている現在，「整数計画ソルバーで解ける」問題の範囲は広がっており，ソルバーを利用する(ILP2) の最適解と最適値は x1 = 0, x2 = 1, x3 = 0,

価値は十分高まっていると言える．

x4 = 1, x5 = 1, Z = 34 である．すなわち，P2, P4,

本稿では，[1, 5, 9, 15] を基に，ILP の定式化につP5 を採用するとき NPV の合計が最大の 34 となる．

いて解説する．また，最近の整数計画ソルバーで設定

このように，ILP はが可能な，SOS (Special Ordered Set)，半連続変数(a) 目的関数と制約式が線形 (線形不等式または線形等式)(b) 変数の一部またはすべてが整数である問題を対象とする．バイナリ変数は，0 以上 1 以
下の整数変数であるため，(b) に含まれる．条件 (b) を除去する (バイナリ変数 xj に対しては「xj = 0 または 1」
を「0xj(semi-continuous variable) を適宜取り上げて説明す
る．興味を持たれた方，あるいは本稿の内容では物足1」にする) と線形計画問題になるが，りない方は，直接これらの文献をご覧いただきたい．

2. 定式化について
ILP に限らず，数理最適化 (数理計画法) における定式化手順の一例は

この操作は線形計画緩和 (linear programming relax-

1. 変数を定義する．

ation) あるいは連続緩和 (continuous relaxation) と2. 問題の実行可能解を過不足なく表現するよう制約

よばれ，ILP の解法において重要な役割を果たす．例
題 1 の (LP1) は，(ILP1) の線形計画緩和問題である．

式を記述する．

3. 目的関数を記述する．

ILP の応用例は数多く存在する．和書では [7–10] なとなるであろう [16]．例題 1 と例題 2 は，問題文からどがあり，また，本学会誌でも応用例を数多く見つけ

ほぼ自動的に定式化を記述することができた．しかし，ることができる．しかし，本稿の目的は，それらを紹これらの問題に対しても定式化は一通りではない．例え介することではなく，その背景にある ILP の表現力のば，例題 1 では (x1 , x2 ) = (0, 0), (0, 1), (0, 2), (1, 0),2012 年 4 月号

c by ORSJ. Unauthorized reproduction of this article is prohibited.（19） 191
Copyright (1, 1), (1, 2), (2, 0), (2, 1), (3, 0) が実行可能解 (製造の整数計画ソルバーのアルゴリズムは，線形計画緩和

可能なテーブル数とチェア数の組合せ) であるから，をベースにした解法 (分枝限定法／分枝カット法) であ(ILP1 )最大化

Z = 4x1 + 5x2

条x1 + x2

件

x2

るため，一般に，次の条件を満たすほど良い定式化であると言うことができる．

3,(a) 線形計画緩和がよい (凸包に近い)

2,x1 , x2(b) 変数の数が少ない

 0,(c) 制約式の数が少ない

x1 , x2 : 整数

変数や制約式の数が少ない問題でも，解くことが難しも正しい定式化である (図 2)．また，例題 2 においい場合があるのが ILP の特徴であると言える．上記のても(a)–(c) 以外にも，極端に大きい・極端に小さい係数を含めないことなどが挙げられるが，まずは (a)–(c) に(ILP2  )最大化

Z = 17x1 + 16x2 + 14x3 + 10x4 + 8x5

条

x1 + x2

件1,

x1 + x4 + x5

注目すべきであろう．例えば big-M を含む定式化は係数が大きいうえに (a) の意味で弱いことが多く，よって多用しないことを心がけるべきとされている．また，

2,

x1 + x2 + x3 + x4

2,

x1 + x2 + x3 + x52,

変数の上下限が予めわかっていれば，それを記述しておくのがよい．

3. 様々な表現方法

x1 , . . . , x5 = 0 または 1が正しい定式化になっていることを示すことができる2．

例題 2 のナップサック問題においてバイナリ変数を

そして，このように線形制約 (線形不等式系) が異な導入した．例えば x1 は，P1 が採用されるとき x1 = 1，

ると，線形計画緩和問題も異なる．例えば例題 1 では，採用されないとき x1 = 0 であった．本節では，この(ILP1 ) の線形計画緩和問題の実行可能解領域 (多面ようなバイナリ変数を使ったさまざまな表現方法につ体) は，(ILP1) のそれに含まれている (図 1，図 2)．

いて概観する．

前者は ILP の実行可能解集合 (x1 , x2 ) = (0, 0), . . . ,3(3, 0) の凸包 であり，これ以上領域を小さくするように線形制約を記述することはできない．つまり，凸包は最強の定式化 (理想の定式化) を与えるが，それを記述する線形制約をすべて求めることは一般に非常に3.1 論理的関係 1
再び例題 2 を例として，いくつかの追加条件とその表現方法をリストアップする．

1. 採用されるプロジェクト数が高々3 (3 以下) :x1 + x2 + · · · + x53.

困難である．ただし，最近の整数計画ソルバーは凸包2. 採用されないプロジェクト数が高々3 :に近づける機能 (前処理，カット生成など) を備えてい(1 − x1 ) + (1 − x2 ) + · · · + (1 − x5 )る．例えば例題 1 の制約 2x1 + 2x2
で割ると x1 + x2

7 は，両辺を 2

3.5 となるが，整数条件によって左辺は整数の値しかとらない．よって，x1 + x2

3としてよい．これが前処理の一つである．

3.

3. P1 または P2 を採用 :x1 + x2

 1.

4. P1 を採用するならば P2 を採用 :
x1

x2 .

また，定式化手順の「1. 変数の定義」をどのように

5. P1 , . . . , P5 のうち採用できる数は 0 または 2 :するかによって，さらにバラエティに富んだ定式化が

x1 + x2 + · · · + x5 = 2y, y = 0 または 1.

可能となる．これについては 4 節で紹介する．

あるいは，y を使わず

ところで，整数計画ソルバーによって解きやすい定式化を「良い」定式化とよぶことにする．ほぼすべて

2

これは極小被覆に基づく定式化であり， [7] の定理 8.9 を適用した．
3
集合 S を含む凸集合の中で (包含関係の意味で) 最小のものを凸包とよぶ．例題 1, 例題 2 のように S が有限集合の場合，凸包は多面体，つまり線形不等式系で記述できることが知られている (Weyl の定理)．

⎧⎪+x1 + x2 + · · · + x5
⎪
⎪
⎪
⎪
⎪
⎪
−x1 + x2 + · · · + x5⎪⎪⎨
+x1 − x2 + · · · + x5
⎪
⎪
⎪
⎪
⎪
...,
⎪
⎪
⎪
⎪
⎩
+x1 + x2 + · · · − x5

2,

 0,
 0,
0

と表現することもできる．

c by ORSJ. Unauthorized reproduction of this article is prohibited.
192 （20）Copyright 

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

表1

4 の実行可能解
x1
1
0
0

x2
1
0
1
図 3 4 の図示

図 5 区分線形関数近似

図 4 区分線形関数

2 については，x1 の反転 (否定) は 1−x1 である (x1 = 1

は，制約が冗長となるように選択する．2 は 1 の拡張のとき 1 − x1 = 0，x1 = 0 のとき 1 − x1 = 1) ことである．

から導かれる．2 は x1 + x2 + · · · + x5

 2 と同じ意「x = 0 または xu」なる条件 (ただし  > 0，

味 (採用されないプロジェクト数を 3 以下にするため

u は +∞ でもよい) がある変数 x を半連続変数という．

には，2 つ以上のプロジェクトを採用しなければなら

これは離接制約であるが，例えば u が有界の場合⎧⎨yない) であるが，反転を使うと上記のように直接的に記述することができる．

xuy,

論理的関係はこれに限らず数多くあるが，このよう⎩y = 0 または 1

な式を導くための一助として，4 を例として説明する．

として表現することができる．u が +∞ の場合，big-M

4 では，変数は x1 と x2 であり，実行可能解は 3 通りを導入する．

ある（表 1）．そしてこの凸包をとると，x1x2 が導かれる (図 3)．

3.3 非線形関数 1
図 4 に示す区分線形関数の表現を考える．応用例と3.2 論理的関係 2

して，図 5 のように，非線形関数 y = f (x) の区分線

次に，制約式に関する論理的関係を取り上げる．こ形関数近似がある．



こでは，線形不等式をb と表している ( は

1.


1



b1 または


2



b2 ：

⎧

⎪
 − b1⎪⎪⎨ 1(x, y) = t1 (x1 , y1 ) + t2 (x2 , y2 ), t1 + t2 = 1, t1 , t2

M (1 − y),M y,2  − b2⎪⎪⎪⎩y = 0 または 1.

2. m 本の線形不等式


i





bi (i = 1, . . . , m) の

bi を線形不等式系 Ai i に拡張することができる．

る．M は十分大きい定数 (big-M) である．y = 1 の

b1 ，つまり 1 番目の制約を有効にして 2

番目の制約を冗長にしている．よって，M の値として2012 年 4 月号



t1 + · · · + t4 = 1, t1 , . . . , t4 0,⎪⎪⎪⎩高々2 つの隣り合う t が正 (非零)iとして表現することができる．
「高々2 つの隣り合う tiが正」の形をした制約を満たす変数群 (t1 , . . . , t4 ) を，

SOS2 (SOS of Type 2) 変数群という．これは，バイ
ナリ変数 z1 , z2 , z3 を導入することで，次のように表現することができる．

⎧⎨t1 z1 , t2 z1 + z2 , t3 z2 + z3 , t4 z3 ,⎩z + z + z = 1, z , z , z = 0 または 1.
1
2
3
1
2
3
絶対値関数 y = |x| (−

1 は離接制約 (disjunctive constraint) と呼ばれてい
とき， 
1 

として表現することができる4．これを考慮すると，一⎧⎪⎪⎪(x, y) = t1 (x1 , y1 ) + · · · + t4 (x4 , y4 ),
⎨

⎧
⎪
⎪ 
M (1 − yi ) (i = 1, . . . , m),i  − bi⎪⎪⎪m⎨
yi = p,
⎪
⎪
⎪ i=1
⎪
⎪
⎩yi = 0 または 1 (i = 1, . . . , m).
i

0

般に (x, y) は

うち p 本を満たす：

1, 2 とも線形不等式

区分線形関数上の点 (x, y) は，ある線分上にある．例
えば (x1 , y1 ) と (x2 , y2 ) で結ばれる線分上にある場合，

転置記号)．

xu, , u(1)

 0 は定数)4(x, y) = t(x1 , y1 ) + (1 − t)(x2 , y2 ), 0t
1 という表現と同じものである．実際，t1 = t, t2 = 1 − t とおけばよい．

c by ORSJ. Unauthorized reproduction of this article is prohibited.（21） 193
Copyright 

は区分線形関数であるため，(−, ), (0, 0), (u, u) につ

考える．x には上下限制約 

いて上記の議論を適用することができる．ただし，こる．このとき，の場合については

⎧
⎪
−x
⎪
⎪
⎨

y

−x + 2uz,x y x + 2(1 − z),⎪⎪⎪⎩z = 0 または 1⎧⎪
z y uz,⎪⎪⎨x − u(1 − z) y⎪⎪⎪⎩z = 0 または 1u があると仮定す

x − (1 − z),とすることができる．

3.5 整数変数からバイナリ変数への変換と表現することもできる．

 |x| に置き換えることができる
場合には，さらに y  |x| を y  x, y  −x に置き換
また，y = |x| を y

バイナリ変数の表現力の高さを示すため，一般の整数変数も表現できることを紹介する．例えば

えればよく，バイナリ変数を導入する必要はない．例
えば，目的関数が |f (x)| の最小化問題では，目的関数を y とし，制約式に yx f (x), y  −f (x) を追加すればよい．y = max{a1 x + b1 , . . . , am x + bm } に対しても同様である．これは線形計画法におけるテクニッ
クであるが，重要と思われるためここでも取り上げた．

3.4 非線形関数 2
前節では非線形関数の区分線形関数近似を紹介したが，ここではバイナリ変数を含む非線形関数の線形化を取り上げる．
ま ず，バ イ ナ リ 変 数 x1 と x2 の 積 y= x1 x2を 考 え る ．こ の 場 合 ，実 行 可 能 解 は (x1 , x2 , y) =(0, 0, 0), (1, 0, 0), (0, 1, 0), (1, 1, 1) であるから，
y = x1 x2 , x1 , x2 = 0 または 10xj

9, xj : 整数に対して，次に挙げる複数の方法で変数 xj を消去することができる．

⎧⎨xj = y1j + 2y2j + 22 y3j + 23 y4j ,⎩y , . . . , y = 0 または 1.
1j
4j
⎧
⎪
xj = y1j + 2y2j + 3y3j + · · · + 9y9j ,⎪⎪⎨y1j + · · · + y9j 1,⎪⎪⎪⎩y , . . . , y = 0 または 1.
1j
9j⎧⎨xj = y1j + y2j + y3j + · · · + y9j ,⎩y , . . . , y = 0 または 1.
1j

9j

最後の方法においては，y1j y  · · ·  y という2j9j

制約を加えて解の対称性と冗長性を排除するのがよい．
また，xj が限られた離散値を取る場合，例えばを⎧⎨1 − x1 − x2 + y 0, x1 − y⎩x , x = 0 または 1

1 0, x − y  0,22に置き換えることができる．これらの線形不等式は，実xj = 3 または 4 または 9の場合，⎧⎨xj = 3y1 + 4y2 + 9y3 ,⎩y + y + y = 1, y , y , y = 0 または 1
1
2
3
1
2
3

行可能解の凸包から得られる．この拡張として，k 個と書き直すことができる．y1 , y2 , y3 は，ちょうど一つの積 y = x1 · · · xk (x1 , . . . , xk はバイナリ変数) では，が正 (非ゼロ) にならなければならず，このような変数

⎧
k

⎪
⎪
⎪
(k − 1) −xi + y
⎪
⎪
⎨
i=1

 0,



⎪
xi − y 0 (i = 1, . . . , k),⎪⎪⎪⎪⎩x , . . . , x = 0 または 11kとすることができる．よって，バイナリ変数の多項式は線形化できることがわかる．なぜなら，バイナリ変数 xi
n−1
は xn= · · · = x2i = xi を満たす (xi に 0 と 1
i = xiを代入して確認できる) ため，例えば x21 x52 x34 = x1 x2 x4であるように，バイナリ変数の積は xi1 xi2 · · · xik の形にすることができるためである．
次に，連続変数 x とバイナリ変数 z の積 y = xz を

群を SOS1 (SOS of Type 1) 変数群という．連続変数

x1 , x2 , x3 (ただし，x1 , x2 , x3 0) が SOS1 の場合⎧⎪x1 M y1 , x2 M y2 , x3 M y3 ,
⎪
⎪
⎪
⎪
⎪
⎨x1 , x2 , x3 0,⎪⎪
y1 + y2 + y3 = 1,
⎪
⎪
⎪
⎪
⎩
y1 , y2 , y3 = 0 または 1と表現することができる (M は十分大きい定数)．SOS2の表現 ((1) 式) においても，SOS1 変数群 z1 , z2 , z3 が現れている．

4. 変数の定義について最後に，さまざまな変数の定義方法があることを紹

c by ORSJ. Unauthorized reproduction of this article is prohibited.
194 （22）Copyright 

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

介するために，スケジューリング問題 (例題 3) と巡回
セールスマン問題 (例題 4) を取り上げる．初学者の方は必ずしも詳細まで追う必要はなく，変数の定義によって定式化が大きく変わることを理解していただきたい．
例題 3.

Z=

最小化

n





wj

j=1

条

pk xkj + pjk=jxkj + xjk = 1

件(j, k = 1, . . . , n, j = k),

xjk + xk + xj

2(j, k,  = 1, . . . , n, j = k, j = , k = ),

4 つのジョブを 1 台の機械で処理する．

xjk = 0 または 1

ジョブに関するデータは次のように与えられている．

(j, k = 1, . . . , n, j = k)と定式化することができる．ジョブ j の完了時刻は

ジョブ j

1

2

3

4

wj
pj

2
3

1
2

3
5

5
7

Cj =



k=j

pk xkj + pj と表現することができるので，これが目的関数に使われている．2 番目の制約式は，推移律 (j → k, k →  ならば j → ) を表している．

ジョブ j の処理時間は pj で与えられている．この定式化 2 時刻を単位時間ごとに区切り，時刻 t − 1 にとき，重み付き完了時刻和 Z = w1 C1 +· · ·+w4 C4

始まり時刻 t に終わる範囲を期間 t とよぶ．また，計画期を最小にするジョブの処理順序を求めよ．Cj は間を 1, . . . , T とする．このとき xjt (j = 1, . . . , n, t =ジョブ j の完了時刻である．機械は同時に二つ以

1, . . . , T − pj + 1) を，ジョブ j が期間 t に処理を開上のジョブを処理できず，また，一度処理を開始始するとき 1，しないとき 0 を示すバイナリ変数とす

すると完了まで中断はできないものとする．

ると，

例えばジョブを 1, 2, 3, 4 の順に処理するとき，各ジョ
ブの処理開始時刻 Sj と完了時刻 Cj は次のようになる．

n


Z=

最小化

⎛

⎞

T −pj +1



wj ⎝

j=1

(t + pj − 1)xjt ⎠t=1

T −pj +1

ジョブ j1

開始時刻 Sj

0

3

5

10

完了時刻 Cj

3

5

10

17

2

3

4

条



件

t=1
n



時刻の条件追加など) すると容易には解けなくなるた
め，1||



wj Cj に対する定式化を考えることは無意味ではない．ここでは [13] などを基として，さまざまな定式化を紹介する．[9] では 1||

1(t = 1 . . . , T ),(j = 1, . . . , n, t = 1, . . . , T − pj + 1)と定式化することができる．
定式化 3 ジョブ j の完了時刻 Cj (j = 1, . . . , n) を変数とする．

ルが最適になることが知られている [14]．しかし，この問題を拡張 (一機械から多機械への拡張，開始可能

xjs

xjt = 0 または 1

17 = 126 である．最適な処理順序は 4, 3, 1, 2 であるができる．実際，wj /pj の降順に処理するスケジューt(j = 1, . . . , n),

j=1 s=t−pj +1

よって，Z = w1 C1 + · · · + w4 C4 = 2 × 3 + · · · + 5 ×(Z = 118)．この問題は，スケジューリング理論では
1|| wj Cj と記述される問題であり，容易に解くこと

xjt = 1

最小化

Z=

n


wj Cj

j=1

条

件

Cj
Ck

 p (j = 1, . . . , n), C + p または C  C + p
j

j

k

j

k

j

(j, k = 1, . . . , n, j = k).

wj Cj の線形計画問 C + p または C 

題による定式化 (制約式の数が指数オーダー) が紹介さこの定式化には離接制約「Ckれている．なお，以下ではジョブ数を n とし，簡単のCk + pj 」が含まれる．これは，3.2 節で紹介した方法

ため pj はすべて正の整数と仮定する．

を適用すると定式化 1

xjk (j, k = 1, . . . , n, j = k) を，ジョブ jがジョブ k より先に処理される (j → k と記す) とき 1，
されないとき 0 を示すバイナリ変数とする．このとき，

j

k

j

⎧
⎪
⎪
⎨ Cj − Ck + pk M (1 − yjk ),Ck − Cj + pj M yjk ,⎪⎪⎩ y = 0 または 1jkとすることができる．

2012 年 4 月号

c by ORSJ. Unauthorized reproduction of this article is prohibited.（23） 195
Copyright が得られる．右辺は 3 より小さいため，(3) は部分巡
頂点

回路除去制約になっているものの，定式化としては弱集合 (都市の集合) を V = {1, . . . , n} とし，頂点いことが推測され，実際その通りであることが知られi から j への費用 (距離，移動時間等) を cij とすている．詳細については最近の解説 [6, 9, 12] をご覧る．このとき，すべての頂点 (都市) をちょうど一いただきたい．

例題 4 ((非対称) 巡回セールスマン問題).

度ずつ通る巡回路のうち，総費用最小のものを求めよ．

5. おわりに
本稿では，整数計画法の定式化に焦点を当てて解説を行った．専門的な内容も含まれているが，(教科書的この問題に対して，次の定式化が標準的である [4,8–10]．xij を，巡回路として i から j に直接移動するとき 1，そうでないとき 0 を示すバイナリ変数とする．また，A を直接移動できる頂点ペア (i, j) の集合とする．このとき，最小化件考えている．
本稿で紹介したように，同じ問題でもさまざまな定
実際には試行錯誤が欠かせないはずである．整数計画

cij xij

ソルバーは使いやすさの点でも向上しており，試行錯誤(i,j)∈A

条

法にあることが伝われば，本稿の役目は果たされたと式化が可能な場合があるが，そうでなくとも定式化のZ=な) 例題 1 よりもさらに広い世界や可能性が整数計画

xij = 1(j ∈ V ),する際の道具としても便利なものである．この点も含

xij = 1(i ∈ V ),参考文献

め，本特集の他の解説を是非参考にしていただきたい．

i:(i,j)∈A

j:(i,j)∈A

xij|S| − 1(i,j)∈A:i∈S,j∈S(S ⊆ V \ {1}, |S|
xij = 0 または 1

 2),

(2)

(i, j = 1, . . . , n).

(2) は部分巡回路除去制約とよばれている．(2) は制
約式の数が O(2n ) あり，n が大きくなると整数計画ソルバーで直接解かせることが難しくなる．そこで，制約
式の数を抑える方法が研究されている．例えば (2) をui − uj + (n − 1)xij

n−2(i, j ∈ V \ {1}, i = j)(3)に置き換えることができる [11]．この置き換えによって制約式の数は O(n2 ) にまで減少するが，弱い定式化になる．これを見るため，例として S = {i, j, k} を考える．この S に対する (2) 式は

xij + xji + xik + xki + xjk + xkj

2

である．一方，有向閉路 (部分巡回路)(i, j), (j, k), (k, i)のそれぞれについて (3) 式の和をとると，変数 u が消去され

xij + xjk + xki

3×

n−2
n−1

[1] D.-S. Chen, R. G. Baston and Y. Dang, Applied
Integer Programming: Modeling and Solution, Wiley,2010.
[2] G. B. Dantzig, “On the Significance of Solving Linear Programming Problems with Some Integer Variables,” Econometrica, 28 (1960), 30–44.
[3] G. B. Dantzig, Linear Programming and Extensions,” Princeton University Press, 1963. （小山昭雄
訳，『線型計画法とその周辺』，ホルト・サウンダース・ジャ
パン, 1983.）[4] G. B. Dantzig, D. R. Fulkerson and S. M. Johnson,“Solution of a Large Scale Traveling Salesman Problem,” Operations Research, 2 (1954), 393–410.
[5] Fair Isaac Corporation, FICO Xpress Optimization
Suite, MIP formulations and linearizations, Quickreference, 2010.
[6] 藤江哲也，「最近の混合整数計画ソルバーの進展について」『オペレーションズ・リサーチ』，56 (2011), 263–268.
[7] 今野浩，『整数計画法』，産業図書，1981．
[8] 今野浩，鈴木久敏 (編)，『整数計画法と組合せ最適化』，
日科技連出版社，1982.
[9] 久保幹雄，『サプライ・チェイン最適化ハンドブック』，
朝倉書店，2007.
[10] 久保幹雄，田村明久，松井知己（編），『応用数理計画
ハンドブック』，朝倉書店，2002.
[11] C. Miller, A. Tucker and R. Zemlin, “Integer Programming Formulations and Traveling Salesman Problems,” Journal of the Association for Computing Machinery, 7 (1960), 326–329.
[12] 沼田一道，「汎用 MIP ソルバによる巡回セールスマン
問題の求解―多項式オーダ本数の部分巡回路除去制約―」，『オペレーションズ・リサーチ』，56 (2011), 452–455.
[13] M. Pinedo, Scheduling: Theory, Algorithms, andSystems, Prentice Hall, 1995.
[14] W. E. Smith, “Various Optimizer for Single-

c by ORSJ. Unauthorized reproduction of this article is prohibited.
196 （24）Copyright 

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

Stage Production,” Naval Research Logistics Quarterly, 3 (1956), 59–66.
[15] H. P. Williams, Model Building in Mathematical
Programming,” John Wiley and Sons, 1993. （前田英2012 年 4 月号

次郎監訳，小林英三訳，『数理計画モデルの作成法』，産業
図書，1995.）[16] L. Wolsey, Integer Programming, Wiley, 1998.

c by ORSJ. Unauthorized reproduction of this article is prohibited.（25） 197
Copyright