對(duì)于0-1分?jǐn)?shù)規(guī)劃的Dinkelbach算法的分析

                  武鋼三中 吳豪[譯]
摘要:
0-1分?jǐn)?shù)規(guī)劃問(wèn)題是指求出解集{xi|xi=0或1}使目標(biāo)(c1x1+c2x2+...+cnxn) /(d1x1+d2x2+…+dnxn)=cx/dx達(dá)到最大。對(duì)于分?jǐn)?shù)規(guī)劃問(wèn)題，Dinkelbach提出了一個(gè)算法，它通過(guò)解決一個(gè)子問(wèn)題Q(L)來(lái)得到原文題的解。這里Q是一個(gè)線性的最小化目標(biāo)函數(shù)cx-Ldx，且滿足x等于0或1。在本文中，我們證明了Dinkelbach算法在最壞情況下可以在O(log(nM))的時(shí)間內(nèi)解決子問(wèn)題，這里M=max{max|ci|,max|di|,1}。
1．0-1分?jǐn)?shù)規(guī)劃問(wèn)題

要使兩個(gè)線性函數(shù)的比值最大或最小的問(wèn)題，我們稱作分?jǐn)?shù)規(guī)劃問(wèn)題或雙曲線問(wèn)題。分?jǐn)?shù)規(guī)劃問(wèn)題在許多領(lǐng)域都可以找到[22]。它在經(jīng)濟(jì)學(xué)中的應(yīng)用有些常見(jiàn)的例子，如尋找最優(yōu)收入比率或者在效益約束下的最佳物資調(diào)配問(wèn)題。另外，系統(tǒng)效率也常常用比率來(lái)衡量，如收益/時(shí)間、利潤(rùn)/風(fēng)險(xiǎn)和消費(fèi)/時(shí)間。有大量的文章對(duì)這類問(wèn)題做了分析[3，5，12，20，24]。


有幾類分?jǐn)?shù)規(guī)劃問(wèn)題已被廣泛地研究。如0-1分?jǐn)?shù)規(guī)劃問(wèn)題[1],它包含最優(yōu)比率生成樹(shù)問(wèn)題[4]，最優(yōu)比率環(huán)問(wèn)題[8，6，19]，分?jǐn)?shù)背包問(wèn)題[15]，以及分?jǐn)?shù)剪枝問(wèn)題[10]。在本文中，我們研究0-1分?jǐn)?shù)規(guī)劃問(wèn)題，它的描述如下：


令c=(c1,c2,…,cn)和d=(d1,d2,…,dn)為n維整數(shù)向量，那么一個(gè)0-1分?jǐn)?shù)規(guī)劃問(wèn)題用公式描述如下:

FP: 最小化
(c1x1+…cnxn)/(d1x1…dnxn)=cx/dx
                     xi∈{0,1}
這里x表示列向量(x1,x2,…,xn)T .0-1值向量的子集Ω稱作可行域，而x則是Ω的一個(gè)元素，我們稱x為可行解。貫穿全文，我們假定對(duì)于任意可行解x,dx都是正數(shù)。這里我們記C=max{max|ci|,1},D=max{max|di|,1}。那么，顯然問(wèn)題的最優(yōu)解在區(qū)間[-nC,nC]內(nèi)。
對(duì)于分?jǐn)?shù)規(guī)劃問(wèn)題，有許多算法都能利用下面的線性目標(biāo)函數(shù)解決問(wèn)題。

Q(L): 最小化 cx-Ldx

xi∈{0,1}
記z(L)為Q(L)的最值。令x*為分?jǐn)?shù)規(guī)劃的最優(yōu)解，并且令L*=(cx*)/(dx*)(注：分?jǐn)?shù)規(guī)劃的最值)。那么下面就容易知道了：

z(L) > 0
當(dāng)且僅當(dāng)
L<L*

z(L) = 0
當(dāng)且僅當(dāng)
L=L*

z(L) < 0
當(dāng)且僅當(dāng)
L>L*

此外，Q(L*)的最優(yōu)解也能使分?jǐn)?shù)規(guī)劃最優(yōu)化[7,16,17]。因此，解決分?jǐn)?shù)規(guī)劃問(wèn)題在本質(zhì)上等同于尋找L=L*使z(L)=0。出于這個(gè)目的，關(guān)于L的函數(shù)z(L)具有很多不錯(cuò)的性質(zhì)：分段線性，凹函數(shù)，嚴(yán)格遞減，z(-nC)<0，且z(nC)>0。根據(jù)上面的性質(zhì)，顯然當(dāng)我們確定參量L，我們可以檢驗(yàn)最值L*是否大于小于或等于當(dāng)前的L。
有一些方法能夠產(chǎn)生一系列收斂于L*的參量。其中一種借助于二分搜索[17,21,13]。在兩個(gè)不同的可行解的目標(biāo)值不相同的情況下，他們的差距將大于等于1/(nD)^2。這暗示我們，當(dāng)我們采用二分搜索時(shí)，最優(yōu)值L*可以通過(guò)解決子問(wèn)題Q(L)在最多O(log(2nC/(1/nD)^2))<=O(log(nCD))的時(shí)間內(nèi)得到。
在1979年，Megiddo[18]提出了一個(gè)巧妙的方法來(lái)系統(tǒng)地產(chǎn)生參量序列。他證明了如果子問(wèn)題Q(L)能夠通過(guò)O(p(n))的比較和O(q(n))的累加被解決，那么分?jǐn)?shù)規(guī)劃問(wèn)題就能用O(p(n)+q(n))的時(shí)間被解決。
另一種方法理論上類似于牛頓迭代法，他被Isbell、Marlow[14]和Dinkelbach[7]提出（也被稱作Dinkelbach算法）。這個(gè)算法在[17,21,11]中被討論（也可能是其他文獻(xiàn)）。下一節(jié)將對(duì)它進(jìn)行正式的論述。Schaible[21]證明了對(duì)于非線性分?jǐn)?shù)規(guī)劃問(wèn)題，二分搜索的方法的收斂速度僅僅是線性的，而Dinkelbach的收斂速度卻是超線性的。另外，據(jù)說(shuō)Dinkelbach算法在實(shí)際應(yīng)用中強(qiáng)力而有效（參見(jiàn)[13,23]的例子）。然而，Dinkelbach算法對(duì)于0-1分?jǐn)?shù)規(guī)劃問(wèn)題的最壞時(shí)間復(fù)雜度卻沒(méi)有被證明。在本文中，我們證明了,Dinkelbach算法最多會(huì)在O(log(nCD))的時(shí)間內(nèi)解決子問(wèn)題。注意它的時(shí)間復(fù)雜度與普通的二分搜索相同。我們的結(jié)論暗示了，如果對(duì)于子問(wèn)題Q(L)存在多項(xiàng)式算法，Dinkelbach算法也能夠在多項(xiàng)式時(shí)間內(nèi)解決分?jǐn)?shù)規(guī)劃問(wèn)題。另外，即使子問(wèn)題Q(L)是NP-完全或NP-難的，對(duì)于特殊的分?jǐn)?shù)規(guī)劃我們也能夠在多項(xiàng)式時(shí)間內(nèi)出解。

2．Dinkelbach算法的論述
它本質(zhì)上是觀察直線

z=cx’-Ldx’
于函數(shù)z(L)在L=L’處相切，這里x’是子問(wèn)題Q(L’)的最優(yōu)解。因此，-dx’是z(L)在L’處的斜率。而且很容易看出上面的直線與L軸相交與L=cx’/dx’.
現(xiàn)在我們來(lái)描述Dinkelbach對(duì)于分?jǐn)?shù)規(guī)劃的算法。Dinkelbach算法產(chǎn)生了收斂于L*的參量序列，如圖1中細(xì)線所示的方式。

Dinkelbach算法：
步驟1：設(shè)L=L1,使 L*<=L1<=nC
步驟2：解決子問(wèn)題Q(L)并得到最優(yōu)解x
步驟3：如果z(L)=0，那么輸出x并終止。否則，設(shè)L=cx/dx跳到步驟2

為了初始化L1,將用到nC，因此充分挖掘拓展問(wèn)題的結(jié)構(gòu)將能做出更好的選擇。

 
0/1規(guī)劃問(wèn)題就相當(dāng)于一個(gè)求極值問(wèn)題，將要求解得數(shù)看成一個(gè)未知數(shù)，然后根據(jù)二分查找求得這個(gè)未知數(shù)的最值。



#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;
}