/*Implementation of PStep_Algorithm::BranchPriceAndCut.

*/

#include "PStep_Algorithm.h"

//Solve the CVRP to integer optimality.
//This function executes a branch-price-and-cut algorithm to solve the CVRP.
//If an integer solution is found AlgorithmMembers.IntegerSolutionFound=true. In that case
//the best integer solution can be found in AlgorithmMembers.BestIntegerSolution.
//Statistics are stored in AlgorithmMembers.CurrentBPCStatistics.
void PStep_Algorithm::BranchPriceAndCut(const CVRPInstance &NewInstance, const PStep_AlgorithmSettings &NewAlgorithmSettings){

	//Initialize time
	timePoint StartTime, toc;
	StartTime = HomeMadeclock::now();

	//Initialize algorithm
	Initialize(NewInstance, NewAlgorithmSettings);

	//Initialize tree node selecter
	//------------------------------------------------------------------------------
	//Initialize all TreeNodeSelecters and select the right one.
	PStep_TreeNodeSelecter* TreeNodeSelecter;
	PStep_DeepestNodeSelecter DeepestNodeSelecter(AlgorithmMembers.Nodes, AlgorithmMembers.CurrentTreeNode);
	PStep_LowestLBNodeSelecter LowestLBNodeSelecter(AlgorithmMembers.Nodes, AlgorithmMembers.CurrentTreeNode);
	PStep_DepthFirstLowestLBSecondNodeSelecter DFLLBNodeSelecter(AlgorithmMembers.Nodes, AlgorithmMembers.CurrentTreeNode,AlgorithmMembers.IntegerSolutionFound);
	//Check which tree node selecter should be used
	if (AlgorithmMembers.AlgorithmSettings.NodeSelectionStrategy == 1){
		TreeNodeSelecter = &DeepestNodeSelecter;
	}
	else if (AlgorithmMembers.AlgorithmSettings.NodeSelectionStrategy == 2){
		TreeNodeSelecter = &LowestLBNodeSelecter;
	}
	else /*if (AlgorithmMembers.AlgorithmSettings.NodeSelectionStrategy == 3)*/{
		TreeNodeSelecter = &DFLLBNodeSelecter;
	}

	//Initialize brancher
	//------------------------------------------------------------------------------
	//Initialize all Branchers and select the right one.
	PStep_Brancher* Brancher;
	PStep_MostFractionalEdgeBrancher MostFractionalEdgeBrancher(AlgorithmMembers);
	//List of PStep_MostFractionalEdgeBranchers
	std::list<PStep_MostFractionalEdgeBrancher> ListOfPStep_MostFractionalEdgeBranchers;
	//List of PStep_LysgaardBranchers
	std::list<PStep_LysgaardBrancher> ListOfPStep_LysgaardBranchers;
	//Check which brancher should be used
	if (AlgorithmMembers.AlgorithmSettings.BranchingStrategy == 1){
		ListOfPStep_MostFractionalEdgeBranchers.emplace_front(AlgorithmMembers);
		Brancher = &ListOfPStep_MostFractionalEdgeBranchers.front();
	}
	else /*if (AlgorithmMembers.AlgorithmSettings.BranchingStrategy == 2)*/{
		ListOfPStep_LysgaardBranchers.emplace_front(AlgorithmMembers);
		Brancher = &ListOfPStep_LysgaardBranchers.front();
	}

	//Create references to objects for easy reference
	PStep_BranchPriceAndCutStatistics& CurrentBPCStatistics = AlgorithmMembers.CurrentBPCStatistics;
	PStep_ColumnGenerationStatistics& CurrentCGStatistics = AlgorithmMembers.CurrentCGStatistics;
	PStep_Solution& CurrentSolution = AlgorithmMembers.CurrentSolution;
	bool& IntegerSolutionFound = AlgorithmMembers.IntegerSolutionFound;
	PStep_Solution& BestIntegerSolution = AlgorithmMembers.BestIntegerSolution;
	int& NumberOfTreeNodes = AlgorithmMembers.CurrentNumberOfNodes;
	std::list<PStep_TreeNode>& Nodes = AlgorithmMembers.Nodes;
	int& CurrentNumberOfNodes = AlgorithmMembers.CurrentNumberOfNodes;
	auto& CurrentTreeNode = AlgorithmMembers.CurrentTreeNode;

	//Obtain Algorithm settings
	double TargetRelOptGap = AlgorithmMembers.AlgorithmSettings.RelativeOptGap;
	double TargetAbsoluteOptGap = AlgorithmMembers.AlgorithmSettings.AbsoluteOptGap;
	double TimeLimit = AlgorithmMembers.AlgorithmSettings.TimeLimit;
	double Tolerance = AlgorithmMembers.Tolerance;
	bool PrintProgress = AlgorithmMembers.AlgorithmSettings.PrintBPProgress;
	int PrintBPPeriod = AlgorithmMembers.AlgorithmSettings.PrintBPPeriod;

	//Initialize BranchPriceAndCutStatistics
	CurrentBPCStatistics.EmptyStatistics();
	CurrentBPCStatistics.NumberOfPStepsStart = AlgorithmMembers.PSteps.size();
	CurrentBPCStatistics.NumberOfCCEnd = AlgorithmMembers.NumberOfCapacityCuts;
	CurrentBPCStatistics.NumberOf2EHEnd = AlgorithmMembers.NumberOf2EHCuts;
	CurrentBPCStatistics.NumberOfSCombEnd = AlgorithmMembers.NumberOfSCombCuts;
	CurrentBPCStatistics.NumberOfFCCEnd = AlgorithmMembers.NumberOfFramedCapacityCuts;
	CurrentBPCStatistics.NumberOfHMCEnd = AlgorithmMembers.NumberOfHomogeneousMultistarCuts;
	PStep_SingleBPCIterationStatistics SingleBPCIterationStatistics;
	SingleBPCIterationStatistics.LowerBound = 0;
	SingleBPCIterationStatistics.UpperBound = -1;
	SingleBPCIterationStatistics.Time = 0;
	CurrentBPCStatistics.IterationStatistics.push_back(SingleBPCIterationStatistics);

	//Branch-Price-And-Cut
//------------------------------------------------------------------------------------

	//Branch until any of the termination criteria is met
	while (!(IntegerSolutionFound && (((CurrentBPCStatistics.IterationStatistics.back().UpperBound - CurrentBPCStatistics.IterationStatistics.back().LowerBound) / CurrentBPCStatistics.IterationStatistics.back().UpperBound <= TargetRelOptGap) || ((CurrentBPCStatistics.IterationStatistics.back().UpperBound - CurrentBPCStatistics.IterationStatistics.back().LowerBound) < TargetAbsoluteOptGap))) && (CurrentBPCStatistics.IterationStatistics.back().Time <= TimeLimit) && (NumberOfTreeNodes > 0)){
	
		//Select the next node:
		//----------------------------------------------------------------------------

		TreeNodeSelecter->Select();

		//Manage separation algorithms
		//----------------------------------------------------------------------------

		CurrentSeparationManager->Manage();

		//Solve the node:
		//----------------------------------------------------------------------------

		ColumnGeneration();

		//Process solution:
		//----------------------------------------------------------------------------
		//Check the completion status
		if (CurrentCGStatistics.Flag == 0){
			//LP bound found to the current node

			//Check whether the solution value is worse than the current UB
			if (IntegerSolutionFound && CurrentSolution.SolutionValue>CurrentBPCStatistics.IterationStatistics.back().UpperBound){

				//The current node should be deleted
				Nodes.erase(CurrentTreeNode);
				--CurrentNumberOfNodes;
				
			}
			//Check whether the current solution is integer
			else if (CurrentSolution.IsInteger(Tolerance)){
				//The current solution is integer

				//Process solution

				//Initialize indicator indicating whether a new best integer solution is found
				bool NewBestIntegerSolutionFound = false;

				//Check whether an integer solution has already been found
				if (IntegerSolutionFound){
					//Check whether the new integer solution is better than the current
					if (BestIntegerSolution.SolutionValue>CurrentSolution.SolutionValue){
						//Update the solution
						BestIntegerSolution = CurrentSolution;
						NewBestIntegerSolutionFound = true;
					}
				}
				else{
					//The current solution is the first integer solution found
					IntegerSolutionFound = true;
					BestIntegerSolution = CurrentSolution;
					NewBestIntegerSolutionFound = true;
				}
				//Delete the current node
				Nodes.erase(CurrentTreeNode);
				--CurrentNumberOfNodes;

				//Check whether a new best integer solution is found
				if (NewBestIntegerSolutionFound){
					//Go over all nodes and delete the nodes with a higher parentLB than the current solution value:
					//Obtain the solution value
					double CurrentSolutionValue = BestIntegerSolution.SolutionValue;
					//Obtain iterator pointing to the first node
					auto NextNode = Nodes.begin();
					//Go over all nodes
					while (NextNode != Nodes.end()){
						//Check whether the ParentLB of NextNode is higher than the current solution value
						if (NextNode->ParentLB >= CurrentSolutionValue-Tolerance){
							//The ParentLB is already higher than the UB, erase the node
							NextNode = Nodes.erase(NextNode);
							--CurrentNumberOfNodes;
						}
						else{
							//The ParentLB is not higher than the UB, go to the next node
							++NextNode;
						}
					}
				}

			}
			//The current solution is not integer
			else{
				//Branch

				//DO NOT FORGET TO UPDATE THE NUMBER OF NODES WHEN BRANCHING

				Brancher->Branch();

			}

		}
		else if (CurrentCGStatistics.Flag == 1){
			//The current node is infeasible

			//Delete the current node
			Nodes.erase(CurrentTreeNode);
			--CurrentNumberOfNodes;

		}
		else if (CurrentCGStatistics.Flag == 2){
			//Time limit exceeded

		}

		//Update statistics:
		//----------------------------------------------------------------------------
		
		//Update iteration counter
		++CurrentBPCStatistics.NumberOfProcessedNodes;
		//Initialize iteration statistics
		PStep_SingleBPCIterationStatistics CurrentIterationStatistics;
		//Update LB
		CurrentIterationStatistics.LowerBound = FindLowestLB();
		//Update UB
		if (IntegerSolutionFound){
			CurrentIterationStatistics.UpperBound=BestIntegerSolution.SolutionValue;
		}
		else{
			CurrentIterationStatistics.UpperBound = -1;
		}
		//Update LP and RootNode statistics
		if (CurrentBPCStatistics.NumberOfProcessedNodes == 1){
			CurrentBPCStatistics.LPValue = CurrentCGStatistics.ValueBeforeInequalities;
			CurrentBPCStatistics.LPTime = CurrentCGStatistics.TimeBeforeInequalities;
			CurrentBPCStatistics.RootNodeValue = CurrentCGStatistics.FinalValue;
			CurrentBPCStatistics.RootNodeTime = CurrentCGStatistics.TotalComputationTime;
		}
		//Update time
		toc = HomeMadeclock::now();
		CurrentIterationStatistics.Time = HomeMadeclock::seconds(StartTime, toc);

		//Add the current iteration statistics to CurrentBPCStatistics
		CurrentBPCStatistics.IterationStatistics.push_back(CurrentIterationStatistics);

		//Print progress:
		//----------------------------------------------------------------------------

		if (AlgorithmMembers.AlgorithmSettings.PrintBPProgress && (CurrentBPCStatistics.NumberOfProcessedNodes - 1) % PrintBPPeriod == 0){
			std::cout << CurrentBPCStatistics.NumberOfProcessedNodes << ": " << CurrentNumberOfNodes << " " << CurrentIterationStatistics.LowerBound << " " << CurrentIterationStatistics.UpperBound << " " << CurrentIterationStatistics.Time << std::endl;
		}
	
	}

	//Output
	//------------------------------------------------------------------------------------

	//Update statistics
	if (IntegerSolutionFound){
		CurrentBPCStatistics.TimeSolutionFound = HomeMadeclock::seconds(StartTime, BestIntegerSolution.ConstructionTime);
	}
	else{
		CurrentBPCStatistics.TimeSolutionFound = -1;
	}
	CurrentBPCStatistics.TotalTime = CurrentBPCStatistics.IterationStatistics.back().Time;
	CurrentBPCStatistics.NumberOfPStepsEnd=AlgorithmMembers.PSteps.size();
	CurrentBPCStatistics.NumberOfCCEnd = AlgorithmMembers.NumberOfCapacityCuts;
	CurrentBPCStatistics.NumberOf2EHEnd = AlgorithmMembers.NumberOf2EHCuts;
	CurrentBPCStatistics.NumberOfSCombEnd = AlgorithmMembers.NumberOfSCombCuts;
	CurrentBPCStatistics.NumberOfFCCEnd = AlgorithmMembers.NumberOfFramedCapacityCuts;
	CurrentBPCStatistics.NumberOfHMCEnd = AlgorithmMembers.NumberOfHomogeneousMultistarCuts;
	CurrentBPCStatistics.NumberOfConstructedNodes = AlgorithmMembers.LastUsedNodeID;
	//Check reason for termination
	if (IntegerSolutionFound && ((CurrentBPCStatistics.IterationStatistics.back().UpperBound - CurrentBPCStatistics.IterationStatistics.back().LowerBound) / CurrentBPCStatistics.IterationStatistics.back().UpperBound <= TargetRelOptGap || (CurrentBPCStatistics.IterationStatistics.back().UpperBound - CurrentBPCStatistics.IterationStatistics.back().LowerBound) < TargetAbsoluteOptGap)){
		//Relative gap achieved
		CurrentBPCStatistics.Flag = 0;
		//Copy solution
		CurrentBPCStatistics.Solution = BestIntegerSolution;
	}
	else if (CurrentBPCStatistics.TotalTime >= TimeLimit){
		//Time limit exceded
		CurrentBPCStatistics.Flag = 2;
	}
	else if (!IntegerSolutionFound){
		//No feasible integer solution identified
		CurrentBPCStatistics.Flag = 1;
	}

}