对于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;
}