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

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

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


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


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

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

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

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

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

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

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

 
0/1規(guī)劃問題就相當(dāng)于一個求極值問題，將要求解得數(shù)看成一個未知數(shù)，然后根據(jù)二分查找求得這個未知數(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;
}