branchdemarkationmethod.java

[数学问题]用分支定界发解线性混合整数规划问题

package com.sea0108.simpmethod;

public class BranchDemarkationMethod extends GeneralSimpMethod
{	
	private GeneralSimpMethod gsm;
	private int[] integerVar=null; 
	private Fraction lowerBound = MAX.contraryNumber();	
	public int searchCount = 0;
	
	public BranchDemarkationMethod(Fraction[][] matA, Fraction[] vecB,Fraction[] funCoefs,
	                                                 int[] equationTypes,boolean[] isInteger,boolean isMaximization)
	{
		init(matA, vecB, funCoefs, equationTypes, isInteger, isMaximization);
		solve();
	}
	
	public BranchDemarkationMethod(Fraction[][] matA, Fraction[] vecB,Fraction[] funCoefs,
	                                                 int[] equationTypes,boolean isMaximization)
	{
		boolean[]  isInteger = new boolean[funCoefs.length];
		for(int i=0;i<isInteger.length;i++)
			isInteger[i] = true;
			
		init(matA, vecB, funCoefs, equationTypes, isInteger, isMaximization);
		solve();
	}		
	
	private void init(Fraction[][] matA, Fraction[] vecB,Fraction[] funCoefs, int[] equationTypes,boolean[] isInteger,boolean isMaximization)
	{
		this.isMaximization = isMaximization;
		gsm = new GeneralSimpMethod(matA, vecB, funCoefs, equationTypes, isMaximization);		
	
		int intVarNum = 0;          
		for(boolean b: isInteger)
			if(b)
				intVarNum++;
		
		if(intVarNum>0)
		{		
			integerVar = new int[intVarNum];		
			int c =0;
			for(int i=0;i<isInteger.length;i++)
				if(isInteger[i])
					integerVar[c++] = i;
			
			for(int i =0;i<intVarNum-1;i++)
				for(int j=i+1;j<intVarNum;j++)
					if(funCoefs[i].abs().compareTo(funCoefs[j].abs()) < 0)
					{
						int temp = integerVar[i];
						integerVar[i] = integerVar[j];
						integerVar[j] = temp;
					}						
		}
	}
	
	private void search(GeneralSimpMethod gsm)
	{
		if(searchFinish(gsm))
			return;
		else
		{	
			updateIter(gsm);		
			GeneralSimpMethod[] gsms =  branch(gsm);	
			search(gsms[0]);
			search(gsms[1]);		
		}			
	}	

	private GeneralSimpMethod[] branch(GeneralSimpMethod gsm)
	{	
		if(!searchFinish(gsm))
		{		
			int branchVar = -1;
			if(integerVar!=null)
				for(int i : integerVar)
					if(!gsm.ans[i].isInteger())
					{
						branchVar = i;
						break;
					}
				
			if(branchVar>-1)
			{						
				Fraction[] fs = new Fraction[]{gsm.ans[branchVar].floor(), gsm.ans[branchVar].ceil()};
				return new GeneralSimpMethod[]
				{
					leftOrRightBranch(branchVar, gsm, -1, fs[0]),
					leftOrRightBranch(branchVar, gsm, 1, fs[1])
				};								
			}		
			else
			{
				lowerDemarkation(gsm);
				return new GeneralSimpMethod[]{null,null};	
			}				
		}
		else
			return new GeneralSimpMethod[]{null,null};	
	}
	
	// param leftOrRight: int    -1 for left-branch and 1 for right-branch
	private GeneralSimpMethod leftOrRightBranch(int branchVar,GeneralSimpMethod gsm, int leftOrRight, Fraction f )
	{		
		final int row = gsm.matA.length +1;
		final int col = gsm.matA[0].length;
		Fraction[][] mA = new Fraction[row][col];
		Fraction[] vB = new Fraction[row];
		int[] eTypes = new int[row];
		
		for(int i =0;i < row-1; i++)
		{				
			for(int j=0;j<col;j++)
				mA[i][j] = gsm.matA[i][j];
			vB[i] = gsm.vecB[i];
			eTypes[i] = gsm.equationTypes[i];
		}
		
		for(int j=0;j<col;j++)		
			if(j==branchVar)
				mA[row-1][j] = new Fraction(1);
			else
				mA[row-1][j] = new Fraction(0);
		
		eTypes[row-1] = leftOrRight;
		vB[row-1] = f;		 
				
		return new 	GeneralSimpMethod(mA, vB, gsm.funCoefs, eTypes, isMaximization);
	}
	
	private void lowerDemarkation(GeneralSimpMethod gsm)
	{
		Fraction gfval = isMaximization? gsm.fval : gsm.fval.contraryNumber();	
		if(gfval.compareTo(this.lowerBound) > 0)
		{		
			this.lowerBound = gfval;
			this.ans = gsm.ans;
			this.fval = gsm.fval;
		}		
	}

	private boolean searchFinish(GeneralSimpMethod gsm)
	{			
		if( gsm == null || gsm.fval ==null || (isMaximization? gsm.fval : gsm.fval.contraryNumber()).compareTo(lowerBound) < 0 )		
			return true;
		else
			return false;
	}
	
	private void solve()
	{	
		if(searchFinish(gsm))		
			updateIter(gsm);
		search(gsm);
		this.iterProcess.add("\t（分支定界：搜索完毕，共搜索" + searchCount + "次，迭代" +iterCount+  "次）\n");
	}	
	
	private void updateIter(GeneralSimpMethod gsm)
	{
		this.iterCount += gsm.iterCount;
		this.iterProcess.add("\n\n\t（分支定界：第"+ ++searchCount + "次搜索，迭代" + gsm.iterCount + "次）\n");	
		this.iterProcess.addAll(gsm.iterProcess);	
	}
}