数理解析研究所講究録 1297 巻 2002 年 59-69

59
混合整数計画に対する弱双対定理*
北海道大学大学院経済学研究科

田中嘉浩 (Yoshihiro Tanaka) \dag er

Graduate School of Economics and Business Administration,
Hokkaido University

1

序Balas の昨年の Rotterdam での EURO Gold Medal 講演 [1] に依れば、 整数計画法
は、 大別すると変数を分割統治する branch-and-bound 法、 真の解集合を含み各反復解を分離する切除平面を生成してい$\text{く}$cutting plane 法、 0-1 計画の disjunctive 法と関連の有る lift-and-project 法等に大別できる。

緩和法は上記の中では branch-and-bound 法の部分問題の下界値を求めるのにも利用できるが、 より直接的にビューリステイツク解法として、 上記の厳密解法の直接適用が不可能な問題に対して精度の良い近似値としての下界値を求める実用的解法として意味の有るものであり、 非線形計画や凸計画の関連からも興味深い。
ラグランジュ双対緩和は、 Everett [3] に依って非線形計画からの類推として形式的に提案されたものであるが、 Held and Karp [8] は対称巡回セールスマン問題 (TSP) に対下界と言われる誤差 1%以するラグランジュ緩和が最小 1 木問題になることを示し、$\mathrm{H}\mathrm{K}$内の良質な下界を効率的に得ることに成功した。 更に、 Geoffrion [5] はラグランジュ双対解と元問題の関係に対して見通しの良い結果を与えている。
一方、代理 (surrogate) 双対緩和はラグランジュ双対緩和とほぼ時を同じくして Glover[6] に提案されたものであり、 Greenberg and Pierskalla [7] に依って代理双対ギャツプカ 8
ラグランジュ双対ギャップ以下であることが確立されて以来、 きつい下界を与える緩和法
として主に実用的見地から注目されてきている。 Karwan and Rardin [9] はギャツプの関係の精緻化と条件に依って代理双対に切り替わる 2 フエイズアルゴリズムを提案した。
代理双対緩和の有効な応用例としては、 Lorena and Lopes [13] が集合被覆問題(SCP)

minimize$c^{T}x$subject to$Ax\geq e$,$x\in\{0,1\}^{n}$*京都大学数理解析研究所講究録 (2002)-mail:tanaka@econ hokudai .ac.jp$\uparrow \mathrm{E}$

,

60
但し、

$c$

は正ベクトル、 $A$ は $m\cross n$ の {0, 1} 成分行列、 $e=(1, \cdots, 1)^{T}$ . が有り、 代理

双対緩和の有効性を示しているが、施設配置等実際にその問題に定式化される問題は多い。
, Espejo, and Boffey [4] は最大被覆地点問題$\mathrm{G}\mathrm{a}\mathrm{l}\mathrm{v}\tilde{\mathrm{a}}0$(MCLP)

maximize$f^{T}x$subject to$y^{T}A-x\geq 0$$y^{T}e=p$

但し、
$p$

$f_{j}$,,

は人口、$x_{j}\in\{0,1\},$ $j\in J$ は被覆, $yi\in\{0,1\},$ $i\in I$ は施設稼動, $e=(1, \cdots, 1)^{T}$ ,は施設稼動数、 に於いても代理双対緩和が有効なことを示している。 最近では、 対称

TSP 問題等のグラフ・ネットワークの$\mathrm{N}\mathrm{P}$完全に属する問題に対して、 ラグランジュ双対緩和の初期の不安定さを代理双対緩和で補う

法 [16][14] の実用$\mathrm{L}\mathrm{a}\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{i}\mathrm{a}\mathrm{n}/\mathrm{s}\mathrm{u}\mathrm{r}\mathrm{r}\mathrm{o}\mathrm{g}\mathrm{a}\mathrm{t}\mathrm{e}$的な有効性が示されつつある。
ところで Ram and Karwan [19] は混合整数計画に於ける代理双対ギャップを初めて示したが彼等は整数計画ではギャップは無いと思っていた。整数計画に於ける弱双対定理はまだ研究されるべきことは多く残っている。

本稿では整数計画で既に代理双対ギャップが存在することやその拡大として混合整数
計画の代理双対ギャップを考えれることや、 ラグランジュ双対緩和との関係を中心に、混合整数計画に於ける弱双対 理を導出することを主眼にする。
$\acute{\dot{\text{定}}}$2

整数計画に対する結果
一般の整数線形計画問題は次の様に述べられる:(P)

但し $A$ は $m\cross n$ 有理数行列、$\mathbb{Z}_{+}^{n},$$Gx\leq h$

かつ有界}, 但し

minimize$c^{T}x$subject to$Ax\geq b$,$x\in S$,は適当な次元の有理数ベクトル、 $S=\{x\geq 0|S\subset$

$b,$

$c$

$G$

は $k\cross n$ 有理数行列、 $h1\mathrm{h}k\cross 1$ 有理数ベクトル、 とする。

(P) に関するラグランジュ緩和 (Lagrangian relaxation) は$(P_{\lambda})$minimiz$\mathrm{e}$subject to$c^{T}x+\lambda^{T}(b-Ax)$$x\in S$,$\lambda\geq 0$

に対して、

61
と定義され、 対応するラグランジュ双対 (Lagrangian dual) t ま、$(D_{L})$$\max_{\lambda\geq 0}\{v(P_{\lambda})\}$

.

となる。

(P) に関する代理制約緩和 (surrogate constraint relaxation) [ま $\mu\geq 0$ [こ対して、

minimize$(P^{\mu})$$c^{T}x$subject to$\mu^{T}$(b-Ax)$\leq 0$,$x\in S$.

と定義され、 対応する代理双対 (surrogate dual) は、$\max_{\mu\geq 0}\{v(P^{\mu})\}$$(D_{S})$.

となる。
$v(Ds)$を求めるアルゴリズムの一つを示す (cf. [18])。

アルゴリズム

Step 0:$karrow 1,$$\alpha^{0}arrow-\infty$とし、任意のStep 1(代理緩和) : 代理緩和$\mu^{1}\geq 0$

を選ぶ。

を解き、解

$(P^{\mu k})$$x^{k}$

を得る。 $Ax^{k}\geq b$ ならば$x^{k}$は(P) の解となり、 $c^{T}x^{k}=v(D_{S})=v(P)$ と火て停止。

Step 2(暫定解更新) :ならば \mbox{\boldmath $\alpha$}k\leftarrow cTxk。 さもなければ、$c^{T}x^{k}>\alpha^{k-1}$$\alpha^{k}arrow\alpha^{k-1}$とする。

Step 3(

$\mu$

の更新)

:

$x^{k}$

を集合 $X$(今迄に生成された$x^{k}$

全て)$\subset T$に付け加える。

線形計画

minimizesubject to$\epsilon$$\epsilon\leq\mu^{T}(b-Ax),$$x\in X$$\mu\geq 0$$e^{T}\mu\leq 1$の解を$(\mu^{k+1}, \epsilon^{k+1})$$karrow k+1$とする。 $\epsilon^{k+1}=0$ ならば $v(D_{S})=\alpha^{k}$ で停止。 さもなければと置いて Step 1^。

62$v(P^{\lambda})$$=\Delta$$v(\begin{array}{lllll}\min c^{T}x \mathrm{s}\mathrm{u}\mathrm{b} \mathrm{t}\mathrm{o} \lambda^{T}(b-Ax) \leq 0 x\in S\end{array})$$\geq$$v(\begin{array}{lll}\min c^{T}x+\lambda^{T}(b-Ax)\mathrm{s}\mathrm{u}\mathrm{b} \mathrm{t}\mathrm{o} \lambda^{T}(b-Ax)\leq 0,x\in S\end{array})$$\geq$$v(\begin{array}{lll}\min c^{T}x+\lambda^{T}(b-Ax)\mathrm{s}\mathrm{u}\mathrm{b} \mathrm{t}\mathrm{o} x\in S\end{array})$$=\Delta$$v(P_{\lambda})$

依って、$v(D_{L})= \sup_{\lambda\geq 0}v(\Delta P_{\lambda})\leq\sup_{\mu\geq 0}v(P^{\mu})\Delta=v(D_{S})$

一般に、$v(D_{L})\leq v(Ds)\leq v(P)$の関係が成立する (Greenberg and Pierskalla [7])。

例.

(P)

maximize$x_{1}+2x_{2}$subject to$3x_{1}+2x_{2}\leq 9$$x_{1}+4x_{2}\leq 8$,$0\leq x_{1},$ $x_{2}\leq 5$

最適解 :$x^{*}=\{(0,2)^{T}, (2,1)^{T}\},$

代理双対解 :,,

$x_{\lambda}^{*}=$.

$v(P)=4$ ,$x_{S}^{*}=\{(1,2)^{T}, (3,1)^{T}, (5,0)^{T}\},$ $v(P^{\mu})=5$

ラグランジュ双対解:$x_{1},$ $x_{2}\in \mathbb{Z}_{+}^{2}$,{ 内の整数点}, $v(P\lambda)=5$ .
$S$

Ram and Karwan [19] の推測とは異なり、 この例の様に整数計画問題に於いてさえ双対ギャツプがある。 同様に純整数計画に対しては既に Parker and Rardin [18], Example

516 にも例が示されていた。

63
先に進む前に元問題 (P) の線形緩和 (linear relaxation) を、$(\overline{P})$但し、$\overline{S}=$

定理 1

{

$x\in \mathbb{R}_{+}^{n}|Gx\leq h$$\overline{x}\not\in bdry\overline{S}$minimize$c^{T}x$subject to$Ax\geq b$,$x\in\overline{S}$かつ有界} で定義し、 この解を,$\overline{x}$とする。

を仮定する。 問題 (P) と問題 (Ds) の間に双対ギャツプ、 即ち、(2.1)$v(D_{S})<v(P)$となる必要十分条件は離散集合 $C=$ { $x|c^{T}\overline{x}\leq c^{T}x<c^{T}x^{*}$ , x\in S}\neq \phi 、 であること
である。

[証明]

問題

に Kuhn-Tucker 条件を適用する。

$(\overline{P})$$c-A^{T}\overline{\mu}=0$$\overline{\mu}\geq 0$,$A\overline{x}\geq b$,$\overline{\mu}^{T}(b-A\overline{x})=0$

.

その時、

,

$c^{T}\overline{x}=\overline{\mu}^{T}A\overline{x}=\overline{\mu}^{T}b$が成立する。
問題と$\overline{\mu}^{T}A$$(D_{\overline{S}})$に対しての間の為す角$\frac{\pi}{2}<(\frac{\pi}{2}+\gamma)<\pi$$k>0$ と $x\in\{x|\mu^{T}(b-Ax)=0\}$ を取ると、の間の為す角はとは $0<\gamma<\pi$ となるので、$\overline{\mu}^{T}A$$\gamma$と取れる。 この時
$c^{T}x-c^{T}\overline{x}$となるがこれは$\overline{x}$$\mu^{T}A$$\mu\neq k\overline{\mu},$$c^{T}=\overline{\mu}^{T}A$$x-\overline{x}$

だから、

$=$

$\overline{\mu}^{T}A(x-\overline{x})$$=$$\overline{\mu}^{T}A|x-\overline{x}|\cos(\frac{\pi}{2}+\gamma)<0$,の最適性を示している。

だから、問題 $(D_{S})$ の解で$\mu=\overline{\mu}$を取ると、$c^{T}=\overline{\mu}^{T}A$となり、 $\overline{\mu}^{T}(b-Ax)=c^{T}\overline{x}-c^{T}x$だから、 問題 $(D_{S})$ は次の問題によって決定される。

(Ps)

minimize$c^{T}x$subject to$c^{T}\overline{x}-c^{T}x\leq 0$,$x\in S$

,

64
ならば

$C\neq\phi$$x$は問題 $(D_{S})$ で実行可能なので、 $c^{T}x<c^{T}x^{*}$ となる。

逆に、 $(D_{S})$ の実行可能解が

注意 1を満たすならば、 $C\neq\phi$ が保証される。

$\blacksquare$の時には必要十分条件に制約が入り、 離散集合 $D=\{x|c^{T}\overline{x}\leq$$\overline{x}\in bdry\overline{S}$$c^{T}x<c^{T}x^{*},$$c^{T}x<\mathrm{c}^{T}x^{*}$$\mu^{T}(b-Ax)\leq 0,$$\mu\geq 0,$$\mu\neq 0$, x\in S}\neq \phi 、 であることであるが、本稿では詳細は省く。

次にラグランジュ双対解と元問題の解の目的関数値で成立する関係を示す。

定理 2

問題 (P) と問題 $(D_{L})$ の間に双対ギャツプ、 即ち、(2.2)$v(D_{L})<v(P)$となる必要十分条件は線形緩和解$\overline{x}$が整数解でない$-\mathrm{p}$ち、整数性 (integmlity property)が成立しない)、 ことである。

[$\text{証}$Bfl]

Geoffrion [5]$\mathrm{X}1\mathrm{h}$Nemhauser and Wolsey [17]$\sigma)_{\text{、}}$(2.3)$v(D_{L})= \min\{c^{T}x|Ax\geq b, x\in \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v} S\}$から言えるが、 洞察に役立つ別証明を記す。
問題$(\overline{P})$の解$\overline{x}\not\in \mathrm{b}\mathrm{d}\mathrm{r}\mathrm{y}\overline{S}$に対して、$(\overline{P})$に Kuhn-Tucker 条件を適用することにより、$c-A^{T}\overline{\lambda}=0$が必要となる。 その時、問題 (P) の解

ならば$\overline{\lambda}$

及ひ$x^{*}\not\in \mathrm{b}\mathrm{d}\mathrm{r}\mathrm{y}\overline{S}$$v(P_{\lambda})=c^{T}x_{\lambda}’,$,$v(D_{L})=v(P_{\overline{\lambda}})=\overline{\lambda}^{T}b$が$x$に無関係に決定される。
が存在する。

$\lambda_{k}=0$, となるがそれは矛盾である。 それ故に$\lambda_{k}>0$に対して、 $(b-Ax^{*})_{k}<0$ となる$\overline{S}$$x^{*}=x_{\lambda}’\in \mathrm{b}\mathrm{d}\mathrm{r}\mathrm{y}$$k$と$v(P)=c^{T}x^{*}>c^{T}x^{*}+\lambda^{T}(b-Ax^{*})=v(D_{L})$,を得る。
証明の残りの部分は bdry{$\overline{S}$の解に対する考察である。 ベクトル場$c-A^{T}\lambda(x_{\lambda}^{*})|x_{\lambda}^{*}\in \mathrm{b}\mathrm{d}\mathrm{r}\mathrm{y}$$\overline{S}$is asolution of$(P_{\lambda})$}65
は [21] の Theorem 612 から連続でー

結局$\lambda(x\ovalbox{\tt\small REJECT})$

$\xi$

,

に等しく、

$\xi \mathrm{C}N\ovalbox{\tt\small REJECT}(x\ovalbox{\tt\small REJECT}$$x\ovalbox{\tt\small REJECT}$で内側方向である。

は $(D_{L})$ の解でない。

$\blacksquare$

次にラグランジュ双対解と代理双対解の目的関数値で成立する関係を導出する。
定理 3$\overline{x}\not\in bdry\overline{S}$を仮定する。 問題 $(D_{S})$ と問題 $(D_{L})$ の間に双対ギャツプ、 即ち、(2.4)$v(D_{L})<v(D_{S})$となる必要十分条件は超平面 $H=\{x|cx=c\overline{x}\}$ が[証明]$v(D_{L})$は (2.3) から、線形緩和解となる。 定理 1 の証明と同様に、 $v(Ds)$ は$\overline{x}$$S$の点を含まないことである。

での目的関数値に等しく、$\mu=\overline{\mu}$と取ると、$c^{T}=\overline{\mu}^{T}A$$v(D_{L})=c^{T}\overline{x}$となり、 問題I(Ds) は問題 (Ps) で決定される。 従って題意が成立する。

3

混合整数計画に対する結果
一般の混合整数線形計画問題は次の様に述べられる :minimiz$(P^{M})$$c^{T}x$$\mathrm{e}$subject to$Ax\geq b$,$x\in T$,上の問題の領域制約 $T$ は、
$T$

$=$

$\{x\geq 0|x_{i}\in \mathbb{Z}_{+},$$Iz$

但し、 $I_{Z}\cup IR=$ {$(P^{M})$$1,$$\ldots$と$I_{R}$$i\in I_{Z}$,$x_{j}\in \mathbb{R}_{+},$

は所与, $Gx\leq h$ かつ$j\in I_{R;}$は有界 }.

$T$, n}、 と定義する。

に関するラグランジュ緩和 (Lagrangian relaxation) は$(P_{\lambda}^{M})$minimiz$\mathrm{e}$subject to$c^{T}x+\lambda^{T}(b-Ax)$$x\in T$,と定義され、 対応するラグランジュ双対 (Lagrangian dual) 12、$(D_{L}^{M})$$\max_{\lambda\geq 0}\{v(P_{\lambda}^{M})\}$.

$\lambda\geq 0$[こ対して、

66$(P^{M})[]_{\llcorner}^{\vee}\ovalbox{\tt\small REJECT} T$]$\mathrm{f}\mathrm{f}\mathrm{E}\#\mathrm{J},\#\backslash$$\ovalbox{\tt\small REJECT} \mathrm{f}\mathrm{f}\mathrm{l}$(surrogate constraint relaxation)$\#\mathrm{J}\mu\geq 0[]\subset*_{\backslash }\}$

して、$(P^{M^{\mu}})$minimize$c^{T}x$subject to$\mu^{T}$(b-Ax)$\leq 0$,$x\in T$,と定義され、 対応する代理双対 (surrogate dual) は、$\max_{\mu\geq}0\{v(P^{M^{\mu}})\}$$(D_{S}^{M})$,

先に進む前に元問題 $(P^{M})$ の線形緩和 (linear relaxation) を、$(\overline{P}^{M})$但し、$\overline{T}=$

この解を

補題 1

$\overline{x}${$x\in \mathbb{R}_{+}^{n}|Gx\leq h$minimize$c^{T}x$subject to$Ax\geq b$,$x\in\overline{T}$

,

かつ有界}

とする。

ノルム空間 $X$ に於いて、凸集合 $K$ の非空の内部を含まずに線形多様体 $V$ を含む閉超平面 $H$ が存在しない必要十分条件は $V$ が $K$ の非空の内部を含むことである。

[証明]

定理 4

1

Hahn-Banach の幾何型定理の対偶から言える。

$\overline{x}\not\in bdry\overline{T}$を仮定する。 $ck\neq 0$ となる k\in I。が存在すると仮定する。 その時、 問題 $(P^{M})$ と問題$(D_{S}^{M})$の間に双対ギャップが存在する、 即ち、(3.1)$v(D_{S}^{M})<v(P^{M})$となる必要十分条件は$\overline{x}\not\in T$となることである。 $c_{k}=0,$$\{x|c^{T}\overline{x}\leq c^{T}x<c^{T}x_{M}^{*}, x\in T\}\neq\phi$

[証明]
様に問題

解 x\mbox{\boldmath $\zeta$}*こ於いて、$(D_{S}^{M})$$\forall k\in I_{R}$の時 [こ上の不等式が成立する。

$\mu=\overline{\mu}_{\text{、}}c^{T}=\overline{\mu}^{T}A$が成立するので、 定理 1 の証明と同

ま次の問題$(P_{S}^{M})$ならば、 集合 $C_{M}=$mi imiz$\mathrm{n}$$\mathrm{e}$subject to$c^{T}x$$c^{T}\overline{x}-c^{T}x\leq 0$$x\in T$,,

67で定義される。
$c_{k}\neq 0,$$k\in I_{R}$の場合は、$\overline{x}\not\in T$

ならば補題 1 から超平面 $H=\{x|c^{T}x=c^{T}\overline{x}\}$ と交わる線形多様体 $V=\{x|x_{k}=x, x_{l}=x_{M}^{*}, k\neq l\}$ 上でbdry$\overline{T}$と交わる $V$ 上で$c^{T}x_{S}^{M^{*}}=c^{T}\overline{x}$$c^{T}\overline{x}\leq c^{T}x_{S}^{M^{*}}\leq c^{T}\tilde{x}^{M}<c^{T}x_{M}^{*}$

を満足するを満足するか、$\tilde{x}^{M}\in T$

力\leq 存在する。
$c_{k}=0,$ $\forall k\in I_{R}$

定理 5

1

の場合は、 定理は定理 1 に帰着される。

問題 $(P^{M})$ と問題$(D_{L}^{M})$の間に双対ギャツプ、 即ち、(3.2)$v(D_{L}^{M})<v(P^{M})$が存在する必要十分条件は線形緩和解が$\overline{x}\not\in T$となることである。

先す、 コンパクト集合 $T$ 上での線形関数の最小化だから、[証明]$v(P_{\lambda}^{M})$$=$$v(\begin{array}{ll}\min c^{T}x+\lambda^{T}(b-Ax)\mathrm{s}\mathrm{u}\mathrm{b}.

\mathrm{t}\mathrm{o} Tx\in \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}\end{array})$となる。 従って、$v(D_{L}^{M})$$=$$v( \min_{\mathrm{s}\mathrm{u}\mathrm{b}}$

$=$

$v\{$

. to

$\min_{\mathrm{s}\mathrm{u}\mathrm{b}}$. to$x\in \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}Tc^{T}x+\overline{\lambda}^{T}(b-Ax))$$T)$$c^{T}xAx\geq b,$$x\in \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}$1となるから題意が成り立つ。

定理 2 等と関連するが、一般に (P) の制約条件 $\{x|Ax\geq b, x\geq 0\}$ で $A,$

時に任意の

$b$

に対して端点が整数となる為の必要十分条件は

$A$

$b$

が整数の

が完全ユニモジュラ行列(totally unimodular matrix) であることが分っている.
完全ユニモジュラ行列 (totally unimodular matrix) :0 である。

$A$の全ての$/[]\mathrm{a}$行列式力 i$\pm 1$

力\supset68$b$が任意でなく制限的な時にはより緩い条件で良い。 $A,$

$b,$

$c$

が有理数の時に、

完全双対整数性 (totally dual integer) : 制約 $\{x|Ax\geq b, x\geq 0\}$ で双対問題 (D) が

任意の整数

$c$

に対して最適解$y$が整数である。

という条件が考えられているが、更に $A,$$b$が整数ならば端点が整数になる良い性質を持ち、 マッチング問題等との関連が考えられている。
他に最近、 M. Conforti, G. Cornu\’ejols, and$\mathrm{M}.\mathrm{R}$. Rao (1999) は、

バランス行列 (balanced matrix) :0,1 行列が行にも列にも 2 つの 1 を含む奇数次の正方小行列を含まない時にバランスされる (balanced) という。
を考え、それを係数行列 $A$ にする線形計画では整数解を持つことから、パッキング問題、

被覆問題との関連が考えられている。

4

纏め
整数計画及ひ混合整数計画に対する弱双対定理として次の関係が成立する。

・整数計画に於いて既に代理双対ギャップが存在する例が存在する。
・整数計画、 混合整数計画共にラグランジュ双対ギャップが有るかどうかを決定する問題はクラス$\mathrm{P}$に属する。

・整数計画の代理双対ギャップを調べる問題は場合は$\exists c_{k}\neq 0,$$k\in I_{R}$の時にはクラス$\mathrm{P}$$\mathrm{N}\mathrm{P}$完全に属するが、混合整数計画の

に属する。

参考文献
[1] Balas, E. (2002): “Some thoughts on the development of integer programming during myresearch career–lecture delivered upon receiving the EURO Gold Medal July 9, 2001,
Rotterdam,” European Journal of Operational Research, 141, 1-7.

. (1999): “Decomposition of Balanced Ma[2] Conforti, M., Cornu\‘ejols, G., and Rao,trices,” Journal of Combinatorial Theory, Series $B,$ $77$ ,292-406.
$\mathrm{M}.\mathrm{R}$[3] Everett III, H. (1963): “Generalized lagrange multiplier method for solving problems of
optimum allocation of resources, ” Operations Research 11, 399-417.

69
[4]

, Espejo, L.G.A., and Boffey, B. (2000): “A comparison of Lagrangian andsurrogate relaxations for the maximal covering location problem,” European Journal ofOperahonal Research 124, 377-389.
$\mathrm{G}\mathrm{a}\mathrm{l}\mathrm{v}\tilde{\mathrm{a}}0,$$\mathrm{R}.\mathrm{D}.$[5] Geoffrion, AM. (1974): “Lagrangian relaxation for integer programming,” Mathematical
Programming Study 2, 82-114.
[6] Glover, F. (1965): “A multiphase-dual algorithm for the zerO-One integer programming
problem,” Operations Research 13, 879-919.

. and Pierskalla,[7] Greenberg,
Operations Research 18, 924-939.

. (1970): “Surrogate mathematical programming,”$\mathrm{W}.\mathrm{P}$$\mathrm{H}.\mathrm{J}$. (1970): “The traveling-salesman problem and minimum spanand Karp,[8] Held,ning trees,” Operations Research 18, 1138-1162.
. (1979): “Some relationships between lagrangian and. and Rardin,[9] Karwan,
Mathematical Programming 17, 320-334.
programming,”
integerdualityinsurrogate. (1979): “A polynomial algorithm for linear programming,” Doklady[10] Khachian,
Akad. Nauk USSR, 244, 1093-1096.
$\mathrm{R}.\mathrm{M}$$\mathrm{M}$$\mathrm{R}.\mathrm{L}$$\mathrm{M}.\mathrm{H}$$\mathrm{L}.\mathrm{G}$. (1951): “Nonlinear programming,” Proceedings of the. and Tucker,[11] Kuhn,
Second Berkeley Syrnposium on Mathematical Statistics and Probability, Univ. California
Press, Berkeley.
$\mathrm{A}.\mathrm{W}$$\mathrm{H}.\mathrm{W}$[12] Lemar\’echal, C. and Renaud, A. (2001): “A geometric study of duality gaPs, with aPPlications,” Mathematical Programming 90, 399-427.
. (1994): “A surrogate heuristic for set covering problems,”
N. and Lopes,[13] Lorena,
European Journal of Operational Research 79, 138-150.
$\mathrm{F}.\mathrm{B}$$\mathrm{L}.\mathrm{A}$. (2002): “Using logical surrogate information in La[14] Lorena, L.A.N. and Narciso,
grangean relaxation: An application to symmetric traveling salesman problems,” EurOpean Joumal of Operational Research 138, 473-483.
. (1969): Optimization by Vector Space Methods, Wiley, New York.
[15] Luenburger,$\mathrm{M}.\mathrm{G}$$\mathrm{D}.\mathrm{G}$relaxation for gener. and Lorena, L.A.N. (1999): “[16] Narciso,
114, 165-177.
Research
Operational
European
Journal of
alized assignment problem,”$\mathrm{L}\mathrm{a}\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}\mathrm{a}\mathrm{n}/\mathrm{s}\mathrm{u}\mathrm{r}\mathrm{r}\mathrm{o}\mathrm{g}\mathrm{a}\mathrm{t}\mathrm{e}$$\mathrm{M}.\mathrm{G}$. and Wolsey,[17] Nemhauser,
Wiley, New York.
$\mathrm{G}.\mathrm{L}$[18] Parker,$\mathrm{R}.\mathrm{G}$. and Rardin,$\mathrm{R}.\mathrm{L}$$\mathrm{L}.\mathrm{A}$. (1988): Integer and Combinatorial Optimization,. (1988): Discrete Optimization, Academic, San Diego.

. (1989): “A result in surrogate duality for certain integer[19] Ram, B. and Karwan,
programming problems,” Math. Program. 43, 103-106.
$\mathrm{M}.\mathrm{H}$[20] Rockafellar,$\mathrm{R}.\mathrm{T}$[21] Rockafellar,$\mathrm{R}.\mathrm{T}$. (1970): Convex Analysis, Princeton Univ. Press, Princeton.
. and Wets, R.J-B. (1998): Variational Analysis, Springer, Berlin.

[22] Tanaka, Y. (2002): “On the existence of duality gaPs for mixed integer programming,”
manuscript.