## 分支定界 (branch and bound) 算法
是一種在問題的解空間樹上搜索問題的解的方法。但與回溯算法不同，分支定界算法采用廣度優先或最小耗費優先的方法搜索解空間樹，并且，在分支定界算法中，每一個活結點只有一次機會成為擴展結點。
除少數整數規劃可以用線性規劃的單純形法直接求解外，一般整數規劃必需尋找新的求解方法。這里我們介紹全整數規劃的分枝定界方法，它也可以用于求解混合整數規劃問題和0-1規劃問題。下面我們從一個例子出發來討論它的思路和步驟。
例1 解下面的整數規劃問題
解:
（1）首先我們注意到問題(4.3)的可行解集為圖4-2的陰影部分內的整數格子點組成的集合，暫時不考慮整數限制條件(5)。解相應的線性規劃(1)~(4)，即(4.3)的松弛問題：
用線性規劃的方式得到如下的圖案
得最優解
由(1)和(5)可知ILP的最優解
，且必為整數，從而可以斷言
。這一過程稱為定界，即給出ILP0問題目標函數最優解z*的下界和上界。
（2）其次我們注意到線性規劃(4.4)的解
具有小數，但這兩個變量在(4.3)中都必須是整數，那就是說必須把小數部分**劃掉**。我們注意到，對!
而言(對!)
也是如此)，最終的最優解不會在3和4之間取值，亦即必然有：
這種表達式實際上是將!
在3和4間的小數部分劃掉了，把可行域![]
分成了!
和!
，顯然這種分法把原來線性規劃的解A點**(2.25,3.75)**排除出去了。但沒有排除任何整數可行解。這一過程稱為**分枝**，即用兩個矛盾的約束條件(4.5)分別代入原問題(4.3)形成兩個子問題ILP1和ILP2：
解ILP1的松弛問題ILP1得到
解ILP2的松弛問題ILP2得到
（3）修改上下界：從LP1和LP2的解我們知道有
（4）再分枝：
下面我們就是要劃掉!
LP1的解中!
的小數部分，增加約束!
對ILP1進一步的分枝，即
求解LP3得：
對于LP4，不難看出，無可行解。
（5）再修改界，此時我們又有!
（6）再分枝，繼續對ILP3進行分枝(由于!)
是小數，增限制條件!又得到
求解LP5得到：
求解LP6得到：
至此，所有的子問題都已探明，求解結束。我們得到了ILP0(即原問題)的最優解：
### 分枝定界法的一般步驟如下：
第一步，先不考慮原問題的整數限制，求解相應的松弛問題，若求得最優解，檢查它是否符合整數約束條件；如符合整數約束條件，即轉下一步。
第二步，定界。在各分枝問題中，找出目標函數值最大者作為整數規劃最優值!
的上界記為!
，從已符合整數條件的分枝中，找出目標函數值最大者作為下界，記為
。即 
第三步，分枝。根據對變量重要性的了解，在最優解中選擇一個不符合整數條件的
，令
，(
不為整數)則用下列兩個約束條件：
其中
表示不超過
的最大整數，分別加入問題形成兩個子問題。
第四步，應用對目標函數估界的方法，或對某一分枝重要性的了解，確定出首先要解的某一分枝的后繼問題，并解此問題。若所獲得的最優解符合整數條件，則就是原問題的解，若不符合整數條件，再回到第二步，并參照第四步終止后繼問題。
在上述過程中，要不斷應用分枝、定界、估界來進行判斷。當我們求解某子問題的松弛問題時，只要出現下列情況之一，該問題就已探明：
1. 松弛問題沒有可行解，則原問題也沒有可行解；
2. 松弛問題的最優解恰好全取整數，則該最優解也是其對應的子問題的最優解；
3. 松弛問題的最大值小于現有的下界z，則無論其最優解是否取整數值，都將對應的子問題剪枝；
已探明的子問題就不再用分枝了，如果所有的子問題都已探明，則原整數規劃的最優解就一定可以求出，或可以判定它無解。
JAVA實現分支定界代碼：
~~~
package sy2;
import sy1.*;
/*
* 假設這里所解的整數規劃問題的目標函數取的是max
*/
public class FenZhiDingJie {
double A[][]; //原矩陣的系數矩陣
String D[]; //原矩陣的符號矩陣
double b[]; //原矩陣的常數矩陣
public int count=0;
int index=-1;
public double C[];//目標函數的初始系數向量
public double Uz;//目標函數值下界
public double Lz;//目標函數值上界
public double z;//現在的目標函數值
public double X[];//定義最優解
public double zX[];//定義最優解
public double yX[];//定義最優解
public double Z;//定義整數線性規劃的最優值
public double Ix[];//定義整數線性規劃的最優解
public double As[][];
public double bs[];
public String Ds[];
public double Xs[];
public int lc;
int M,N;
//初始化分支定解法
FenZhiDingJie(double[][] a,double[] B,String[] d,double[] c){
M=B.length;
N=c.length;
A=a;
b=B;
D=d;
C=c;
X=new double[N];
zX=new double[N];
yX=new double[N];
Ix=new double[N];
}
//分支定解過程
public void FZDJ(double[][] a,double[] B,String[] d,double[] c,double x[]){
boolean flag1=true;
boolean flag2=true;
//利用兩階段法解出該整數線性規劃的最優值的上界（第一次使用兩階段法）
while(count<10){
if(count==0){
System.out.println("\n第 "+count+" 次迭代");
TwoStepMethod tm=new TwoStepMethod(A,b,D,C);
if(!tm.flag){
break;
}
X=tm.X;
x=X;
Lz=0;
Uz=-tm.z;
System.out.print("該整數線性規劃問題對應的松弛線性規劃問題的最優解是：x={");
for(int i=0;i<N-1;i++){
System.out.print(tm.X[i]+",");
}
System.out.print(tm.X[N-1]+"}\n");
System.out.println("該整數線性規劃問題對應的松弛線性規劃問題的最優值是："+Uz);
index=AllInteger(X,index);
if(index==-1){
System.out.println("該整數線性規劃問題的最優解即為它的松弛線性規劃問題的最優解，如上所示！");
}
//第一次分支
else{
count++;//跳入分支定解環節
}// else*/
}// if
else{//接下來實現繼續的分支定解法
//System.out.println(Lz);
double A1[][]=new double[B.length+1][N];
double yA1[][]=new double[B.length+1][N];
double ytA[][]=new double[B.length+1][N];
double tA[][]=tempA(a,B.length,index);
for(int i=0;i<B.length+1;i++){
for(int j=0;j<N;j++){
A1[i][j]=tA[i][j];
yA1[i][j]=tA[i][j];
ytA[i][j]=tA[i][j];
//System.out.print(ytA[i][j]+" ");
}
//System.out.println();
}
double yb1[]=new double[B.length+1];
double b1[]=new double[B.length+1];
double ytb[]=tempb(B,(int)x[index]+1);
double ztb[]=tempb(B,(int)x[index]);
for(int i=0;i<B.length+1;i++){
b1[i]=ztb[i];
yb1[i]=ytb[i];
//System.out.println(b1[i]+" "+yb1[i]);
}
//左分支
String D1[]=new String[B.length+1];
String ztD[]=LeftD(d);
for(int i=0;i<B.length+1;i++){
D1[i]=ztD[i];
}
String yD1[]=new String[B.length+1];
String ytD[]=RightD(d);
for(int i=0;i<B.length+1;i++){
yD1[i]=ytD[i];
//System.out.print(yD1[i]+" ");
}
TwoStepMethod ztm=new TwoStepMethod(tA,ztb,ztD,c);//左分支利用兩階段法求解
TwoStepMethod ytm=new TwoStepMethod(ytA,ytb,ytD,c);//左分支利用兩階段法求解
if(count==1){
As=yA1;
bs=yb1;
Ds=yD1;
Xs=ytm.X;
}
if(ztm.flag){
double zz=ztm.z;
zX=ztm.X;
index=AllInteger(zX,index);
if(index!=-1){
//System.out.println(DingJie(z,Uz));
if(DingJie(zz,Uz)){
//左分支
System.out.print("第"+count+"次迭代得到一個松弛線性規劃的最優解：\nzx={");
for(int i=0;i<N-1;i++){
System.out.print(zX[i]+",");
}// for i
System.out.print(zX[N-1]+"}\n");
System.out.println("對應的最優值是："+-zz);
count++;
if(-zz<Lz){
flag1=false;
lc=count;
}
}// if
else{
System.out.println("不存在可行解");
break;
}//else
}else{
System.out.print("第 "+count+" 次迭代得到一個可行解:\nzx={");
for(int i=0;i<N-1;i++){
System.out.print(zX[i]+",");
}//for i
System.out.print(zX[N-1]+"}\n");
System.out.println("對應的最優值是："+-zz);
Lz=-zz;
Z=Lz;//記錄可行解對應的目標函數值
Ix=zX;//記錄可行解
count++;
//lc=count;
}//else
}// if
else{
flag1=false;
System.out.println(count+++"次迭代無可行解");
}
if(ytm.flag){
double yz=ytm.z;
yX=ytm.X;
index=AllInteger(yX,index);
if(index!=-1){
//System.out.println(DingJie(z,Uz));
if(DingJie(yz,Uz)){
if(DingJie(yz,Uz)){
//右分支
System.out.print("第"+count+"次迭代得到一個松弛線性規劃的最優解：\nyx={");
for(int i=0;i<N-1;i++){
System.out.print(yX[i]+",");
}
System.out.print(yX[N-1]+"}\n");
System.out.println("對應的最優值是："+-yz);
//System.out.println(2);
if(-yz<Lz){
flag2=false;
break;
}
//System.out.println(2);
count++;
}//if
else{
System.out.println("不存在可行解");
break;
}
}
}else{
System.out.println("第 "+count+" 次迭代得到一個可行解:\nyx={");
for(int i=0;i<N-1;i++){
System.out.print(yX[i]+",");
}
System.out.print(yX[N-1]+"}\n");
System.out.println("對應的最優值是："+-yz);
Uz=-yz;
Z=Uz;//記錄可行解對應的目標函數值
Ix=yX;//記錄可行解
}
}// if
else{
flag2=false;
System.out.println(count+++"次迭代無可行解");
}
if(flag1){
index=AllInteger(zX,index);
FZDJ(A1,b1,D1,c,zX);
count++;
}else{
break;
}
index=AllInteger(Xs,index);
FZDJ(As,bs,Ds,c,Xs);
break;
}
}//else
}//while
//確定可行解存在性
public boolean DingJie(double z,double Uz){
boolean flag=true;
//首先保證算出的最優解對應的目標函數值位于整數線性規劃問題的目標函數值的上下界中
if(z<=Lz || z>=Uz){
flag=true;//表示該分支繼續往下分不可能找到一個可行解
}// if
else{
flag=false;
}
return flag;
}
//判斷所給向量的元素是否全為整數如果不是返回對應第一個非整數的下標
public int AllInteger(double X[],int index){
boolean flag=true;
for(int i=0;i<X.length;i++){
if(X[i]-(int)X[i]!=0){//表示最優解中存在分數
flag=false;//表示此解不是該整數規劃的最優解
index=i;//記錄下最優解中非整數解的位置
break;
}// if
}// for
if(flag){
index=-1;
}
return index;
}
//左分支各參數處理過程
public String[] LeftD(String d[]){
String D[]=new String[d.length+1];
//對D做相應的轉換
for(int i=0;i<D.length;i++){
if(i<d.length){
D[i]=d[i];
}
else{
D[i]="<";
}
}
return D;
}
//右分支各參數處理過程
public String[] RightD(String d[]){
String D[]=new String[d.length+1];
//對D做相應的轉換
for(int i=0;i<D.length;i++){
if(i<d.length){
D[i]=d[i];
}
else{
D[i]=">";
}
}
return D;
}
//每次分支擴展參數過程
public double[][] tempA(double a[][],int m,int index){
double A[][]=new double[m+1][N];
//對原約束條件添加一個限制
for(int i=0;i<m+1;i++){
if(i<m){
for(int j=0;j<N;j++){
A[i][j]=a[i][j];
}// for
}// if
else{
for(int j=0;j<N;j++){
if(j==index){
A[i][j]=1;
}//if
else
{
A[i][j]=0;
}// else
}//for j
}// else
}//for i
return A;
}
public double[] tempb(double B[],int Lx){
double b[]=new double[B.length+1];
//對b做相應的變換
for(int i=0;i<B.length+1;i++){
if(i<B.length){
b[i]=B[i];
}// if
else{
b[i]=Lx;
}// else
}// for i
return b;
}
}
~~~
~~~
package sy2;
import java.util.Scanner;
import sy1.TwoStepMethod;
/*
* 代碼測試程序
*/
public class Text {
public static void main(String args[]){
int M=2,N=2;//M是約束條件個數，N是未知數個數
double A[][]=new double[M][N];
double b[]=new double[M];
String D[]=new String[M];//原符號向量
double C[]=new double[N];//原目標函數的系數向量
Scanner S=new Scanner(System.in);
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
A[i][j]=S.nextDouble();
//System.out.print(" ");
}
//System.out.println();
}
for(int i=0;i<M;i++){
b[i]=S.nextDouble();
//System.out.print(" ");
}
for(int i=0;i<M;i++){
D[i]=S.next();
//System.out.print(" ");
}
for(int i=0;i<N;i++){
C[i]=S.nextDouble();
//System.out.print(" ");
}
System.out.println("請輸出初始矩陣的方程個數"+M);
System.out.println("請輸出初始未知數的個數"+N);
System.out.println("請輸出初始矩陣的系數矩陣：");
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
System.out.print(A[i][j]+" ");
}
System.out.println();
}
System.out.println("請輸出初始矩陣的常數項：");
for(int i=0;i<M;i++){
System.out.print(b[i]+" ");
}
System.out.println("\n"+"請輸出初始矩陣的符號項：");
for(int i=0;i<M;i++){
System.out.print(D[i]+" ");
}
System.out.println("\n"+"請輸出目標函數的系數向量：");
for(int i=0;i<N;i++){
System.out.print(C[i]+" ");
}/*
TwoStepMethod tm=new TwoStepMethod(A,b,D,C);
if(tm.flag){
System.out.print("\n請輸出通過兩階段法得到的最優解：X={");
for(int i=0;i<N-1;i++){
System.out.print(tm.X[i]+",");
}
System.out.print(tm.X[N-1]+"}\n");
System.out.println("請輸出通過兩階段法得到的最優值是："+tm.z);
}*/
System.out.println("\n\n分支定界法過程：");
double A1[][]=new double[M][N];
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
A1[i][j]=A[i][j];
}
}
double b1[]=new double[M];
for(int i=0;i<M;i++){
b1[i]=b[i];
}
String D1[]=new String[M];
for(int i=0;i<M;i++){
D1[i]=D[i];
}
double x[]=new double[N];
FenZhiDingJie fzdj=new FenZhiDingJie(A, b, D, C);
fzdj.FZDJ(A1, b1, D1, C,x);
System.out.print("該整型線性規劃問題的最優解為X={");
for(int i=0;i<N-1;i++){
System.out.print(fzdj.Ix[i]+",");
}
System.out.print(fzdj.Ix[N-1]+"}");
System.out.println("\n該整型線性規劃問題的最優值為：Z="+fzdj.Z);
}
}
~~~
