對于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，因此充分挖掘拓展問題的結構將能做出更好的選擇。
0/1規劃問題就相當于一個求極值問題，將要求解得數看成一個未知數，然后根據二分查找求得這個未知數的最值。
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,k,a[1110],b[1110];
double low,higth,mid;
double s[1005],sum;
int cmp(double x,double y)
{
return x>y;
}
int main()
{
//freopen("in.txt","r",stdin);
int i;
while(cin>>n>>k)
{
if(k == 0 && n == 0)
break;
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<=n;i++)
cin>>b[i];
low = 0.0;
higth = 100.0;
while(higth - low >= 0.001)
{
mid = (higth+low)/2;
for(i=1;i<=n;i++)
s[i] = a[i]*100.0-1.0*b[i]*mid;
sort(s+1,s+n+1,cmp);
sum = 0;
for(i=1;i<=n-k;i++)
sum += s[i];
if(sum>=0)
low = mid;
else
higth = mid;
}
cout<<(int)(low+0.5)<<endl;
}
return 0;
}