對于0-1分數規劃的Dinkelbach算法的分析

武鋼三中 吳豪[譯]

摘要:

0-1分數規劃問題是指求出解集{xi|xi=0或1}使目标(c1x1+c2x2+...+cnxn) /(d1x1+d2x2+…+dnxn)=cx/dx達到最大。對于分數規劃問題，Dinkelbach提出了一個算法，它通過解決一個子問題Q(L)來得到原文題的解。這裡Q是一個線性的最小化目标函數cx-Ldx，且滿足x等于0或1。在本文中，我們證明了Dinkelbach算法在最壞情況下可以在O(log(nM))的時間内解決子問題，這裡M=max{max|ci|,max|di|,1}。

1．0-1分數規劃問題

要使兩個線性函數的比值最大或最小的問題，我們稱作分數規劃問題或雙曲線問題。分數規劃問題在許多領域都可以找到[22]。它在經濟學中的應用有些常見的例子，如尋找最優收入比率或者在效益限制下的最佳物資調配問題。另外，系統效率也常常用比率來衡量，如收益/時間、利潤/風險和消費/時間。有大量的文章對這類問題做了分析[3，5，12，20，24]。

有幾類分數規劃問題已被廣泛地研究。如0-1分數規劃問題[1],它包含最優比率生成樹問題[4]，最優比率環問題[8，6，19]，分數背包問題[15]，以及分數剪枝問題[10]。在本文中，我們研究0-1分數規劃問題，它的描述如下：

令c=(c1,c2,…,cn)和d=(d1,d2,…,dn)為n維整數向量，那麼一個0-1分數規劃問題用公式描述如下:

FP: 最小化

(c1x1+…cnxn)/(d1x1…dnxn)=cx/dx

xi∈{0,1}

這裡x表示列向量(x1,x2,…,xn)T .0-1值向量的子集Ω稱作可行域，而x則是Ω的一個元素，我們稱x為可行解。貫穿全文，我們假定對于任意可行解x,dx都是正數。這裡我們記C=max{max|ci|,1},D=max{max|di|,1}。那麼，顯然問題的最優解在區間[-nC,nC]内。

對于分數規劃問題，有許多算法都能利用下面的線性目标函數解決問題。

Q(L): 最小化 cx-Ldx

xi∈{0,1}

記z(L)為Q(L)的最值。令x*為分數規劃的最優解，并且令L*=(cx*)/(dx*)(注：分數規劃的最值)。那麼下面就容易知道了：

z(L) > 0

當且僅當

L<L*

z(L) = 0

當且僅當

L=L*

z(L) < 0

當且僅當

L>L*

此外，Q(L*)的最優解也能使分數規劃最優化[7,16,17]。是以，解決分數規劃問題在本質上等同于尋找L=L*使z(L)=0。出于這個目的，關于L的函數z(L)具有很多不錯的性質：分段線性，凹函數，嚴格遞減，z(-nC)<0，且z(nC)>0。根據上面的性質，顯然當我們确定參量L，我們可以檢驗最值L*是否大于小于或等于目前的L。

有一些方法能夠産生一系列收斂于L*的參量。其中一種借助于二分搜尋[17,21,13]。在兩個不同的可行解的目标值不相同的情況下，他們的差距将大于等于1/(nD)^2。這暗示我們，當我們采用二分搜尋時，最優值L*可以通過解決子問題Q(L)在最多O(log(2nC/(1/nD)^2))<=O(log(nCD))的時間内得到。

在1979年，Megiddo[18]提出了一個巧妙的方法來系統地産生參量序列。他證明了如果子問題Q(L)能夠通過O(p(n))的比較和O(q(n))的累加被解決，那麼分數規劃問題就能用O(p(n)+q(n))的時間被解決。

另一種方法理論上類似于牛頓疊代法，他被Isbell、Marlow[14]和Dinkelbach[7]提出（也被稱作Dinkelbach算法）。這個算法在[17,21,11]中被讨論（也可能是其他文獻）。下一節将對它進行正式的論述。Schaible[21]證明了對于非線性分數規劃問題，二分搜尋的方法的收斂速度僅僅是線性的，而Dinkelbach的收斂速度卻是超線性的。另外，據說Dinkelbach算法在實際應用中強力而有效（參見[13,23]的例子）。然而，Dinkelbach算法對于0-1分數規劃問題的最壞時間複雜度卻沒有被證明。在本文中，我們證明了,Dinkelbach算法最多會在O(log(nCD))的時間内解決子問題。注意它的時間複雜度與普通的二分搜尋相同。我們的結論暗示了，如果對于子問題Q(L)存在多項式算法，Dinkelbach算法也能夠在多項式時間内解決分數規劃問題。另外，即使子問題Q(L)是NP-完全或NP-難的，對于特殊的分數規劃我們也能夠在多項式時間内出解。

2．Dinkelbach算法的論述

它本質上是觀察直線

z=cx’-Ldx’

于函數z(L)在L=L’處相切，這裡x’是子問題Q(L’)的最優解。是以，-dx’是z(L)在L’處的斜率。而且很容易看出上面的直線與L軸相交與L=cx’/dx’.

現在我們來描述Dinkelbach對于分數規劃的算法。Dinkelbach算法産生了收斂于L*的參量序列，如圖1中細線所示的方式。

Dinkelbach算法：

步驟1：設L=L1,使 L*<=L1<=nC

步驟2：解決子問題Q(L)并得到最優解x

步驟3：如果z(L)=0，那麼輸出x并終止。否則，設L=cx/dx跳到步驟2

為了初始化L1,将用到nC，是以充分挖掘拓展問題的結構将能做出更好的選擇。