/*Implementation of PStep_ColumnGenerator.h

It contains the member functions of PStep_ColumnGenerator19

*/

#include "PStep_ColumnGenerator.h"

//PStep_ColumnGenerator19:
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Generate columns
//------------------------------------------------------------------------------------

//The same setup as column generator 1, but using bi-directional labeling with completion bounds and
//decremental state space relaxation.
//Initially a regular bi-directional search is performed, for an initial state space relaxation.
//For any subsequent decremented state space relaxation, completion bounds are computed based on the
//previous state space and used for bi-directional labeling.
void PStep_ColumnGenerator19::GenerateColumns(){

	//Reinitialize the decremental state-space information, if required
	if (AlgorithmMembers.DSSRUsed && AlgorithmMembers.AlgorithmSettings.DSSRReset == 3){
		ResetDSSRNeighbourhoods();
	}

	//Initialize the decremental state-space relaxation loop
	RerunRequired = true;
	SetRerunRequiredPerPricingProblem(true);

	//Copy the current DSSRNeighbourhoods to old DSSRNeighbourhoods for all relevant pricing problems
	//which require a rerun.
	CopyCurrentDSSRNeighbourhoodsToOld();

	//Perform an initial run of bidirectional labeling
	GenerateColumns14();

	//Resolve the pricing problem as long as RerunRequired is true
	while (RerunRequired){
		
		//Obtain the second half of the completion bounds.
		//They are used for computing the (relevant) first half of completion bounds
		ObtainEverySecondHalfOfCompletionBounds();

		//Continue and finish the labeling, the result will be used to find
		//the first half of the completion bounds
		ContinueForwardAndBackwardLabeling();

		//Obtain the first half of the completion bounds.
		ObtainEveryFirstHalfOfCompletionBounds();

		//Copy the current DSSRNeighbourhoods to old DSSRNeighbourhoods for all relevant pricining problems
		//which require a rerun.
		CopyCurrentDSSRNeighbourhoodsToOld();

		//Apply bi-directional labeling with completion bounds
		GenerateColumns19();
		
	}

}

//The same setup as column generator 1, but using bi-directional labeling with completion bounds and
//decremental state space relaxation.
//NOTE: It is assumed that the completion bounds are set as well as the reduced costs. Moreover, it assumes
//		decremental state-space relaxation is applied.
void PStep_ColumnGenerator19::GenerateColumns19(){

	//Initialization:
	//*****************************************************************************************

	//Obtain p
	short int p = AlgorithmMembers.AlgorithmSettings.p;
	//Obtain Tolerance
	double Tolerance = AlgorithmMembers.Tolerance;
	//Obtain MaxMergeLabels;
	int MaxMergeLabels = AlgorithmMembers.AlgorithmSettings.MaxMergeLabels;
	//Obtain pricing problems
	PStep_PricingProblem** (&PricingProblems) = AlgorithmMembers.PricingProblems;
	//Obtain lists of relevant pricing problems
	std::list<PStep_PricingProblem*> &RelevantDepotCustomerPricingProblems = AlgorithmMembers.RelevantDepotCustomerPricingProblems;
	std::list<PStep_PricingProblem*> &RelevantCustomerDepotPricingProblems = AlgorithmMembers.RelevantCustomerDepotPricingProblems;
	std::list<PStep_PricingProblem*> &RelevantCustomerCustomerPricingProblems = AlgorithmMembers.RelevantCustomerCustomerPricingProblems;

	//Initialize list of bi-directional layered labeling algorithms
	std::forward_list<PStep_BiDirectionalLayeredLabelingWithCompletionBounds> LabelingAlgorithms;

	//Initialize list of solved pricing problems
	//This list gets updated after a succesful run of PStep_BiDirectionalLayeredLabelingAlgorithm
	std::forward_list<PStep_PricingProblem*> SolvedPricingProblems;

	//Initialize reachability setters:
	//********************************
	//Initialize Container for PStep_NGReachabilitySetter
	std::forward_list<PStep_NGReachabilitySetter> NGReachabilitySetters;
	//Initialize pointer to a current reachability setter
	PStep_ReachabilitySetter* CurrentReachabilitySetter;

	//Initialize extenders:
	//*********************
	//Initialize Container for PStep_StandardExtenders
	std::forward_list<PStep_StandardExtender> StandardExtenders;
	//Initialize bogus PStep_FinalExtender
	PStep_FinalExtender BogusFinalExtender = PStep_FinalExtender(0, 0, 0);

	//Initialize dominators:
	//**********************
	//Initialize load dominator
	PStep_LoadDominator LoadDominator(Tolerance);
	//Initialize pointer to the current dominator
	PStep_Dominator* CurrentDominator = &LoadDominator;
	//Initialize Container for PStep_NGReachabilityDominator, to be used
	//if dynamic state space relaxation is applied and LoadDominator should not be used.
	std::forward_list<PStep_NGReachabilityDominator> DSSRNGReachabilityDominators;

	//Initialize mergers:
	//*******************
	//Initialize Container for PStep_NGZeroLoadMergers
	std::forward_list<PStep_NGZeroLoadMerger> NGZeroLoadMergers;
	//Initialize Container for PStep_NGMaxLoadMerger
	std::forward_list<PStep_NGMaxLoadMerger> NGMaxLoadMergers;

	//Initialize algorithm for the pricing problem from depot to depot:
	//*****************************************************************
	//Check whether p is not 1, in which case this pricing problem is nonsense.
	if (p > 1){

		//Obtain pricing problem
		PStep_PricingProblem &CurrentPricingProblem = PricingProblems[0][0];

		//Check whether according to DSSR this pricing problem is redundant
		if (CurrentPricingProblem.RerunRequired){

			//Obtain demand
			double* Demand = CurrentPricingProblem.Demand;
			//Obtain capacity plus tolerance
			double CapacityPlusTolerance = CurrentPricingProblem.Capacity + Tolerance;

			//Create Reachability setter
			NGReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance, CurrentPricingProblem.CurrentDSSRNotInNeighbourhood);
			//Set current reachability setter
			CurrentReachabilitySetter = &(NGReachabilitySetters.front());
			//Check whether reachability should be checked
			if (!DoNotCheckReachability){
				//Create dominator
				DSSRNGReachabilityDominators.emplace_front(Tolerance, CurrentPricingProblem.CurrentDSSRNeighbourhoods);
				//Set current dominator
				CurrentDominator = &(DSSRNGReachabilityDominators.front());
			}

			//Create standard extender
			StandardExtenders.emplace_front(Demand, CurrentPricingProblem.ReducedArcCosts, *CurrentReachabilitySetter);
			//Create merger
			NGZeroLoadMergers.emplace_front(CurrentPricingProblem.Capacity, CapacityPlusTolerance, CurrentPricingProblem.CandidateMergeLabels, CurrentPricingProblem.CurrentDSSRNotInNeighbourhood);

			//Create Layered Labeling Algorithm
			LabelingAlgorithms.emplace_front(CurrentPricingProblem, StandardExtenders.front(), BogusFinalExtender, *CurrentDominator, NGZeroLoadMergers.front(), UseLimitedArcs, MaxMergeLabels, SolvedPricingProblems);
		}
	}

	//Initialize algorithm for the pricing problems from depot to customers:
	//**********************************************************************
	//Go over all relevant pricing problems from depot to customer
	for (auto RelevantPricingProblem = RelevantDepotCustomerPricingProblems.begin(); RelevantPricingProblem != RelevantDepotCustomerPricingProblems.end(); ++RelevantPricingProblem){

		//Obtain current pricing problem
		PStep_PricingProblem &CurrentPricingProblem = (**RelevantPricingProblem);
		//Check whether according to DSSR this pricing problem is redundant
		if (CurrentPricingProblem.RerunRequired){

			//Obtain current sink
			short int jMinusOne = CurrentPricingProblem.Sink - 1;
			//Obtain demand
			double* Demand = CurrentPricingProblem.Demand;
			//Obtain capacity plus tolerance
			double CapacityPlusTolerance = CurrentPricingProblem.Capacity + Tolerance;

			//Create Reachability setter
			NGReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance, CurrentPricingProblem.CurrentDSSRNotInNeighbourhood);
			//Set current reachability setter
			CurrentReachabilitySetter = &(NGReachabilitySetters.front());
			//Check whether reachability should be checked
			if (!DoNotCheckReachability){
				//Create dominator
				DSSRNGReachabilityDominators.emplace_front(Tolerance, CurrentPricingProblem.CurrentDSSRNeighbourhoods);
				//Set current dominator
				CurrentDominator = &(DSSRNGReachabilityDominators.front());
			}

			//Create standard extender
			StandardExtenders.emplace_front(Demand, CurrentPricingProblem.ReducedArcCosts, *CurrentReachabilitySetter);
			//Create merger
			NGZeroLoadMergers.emplace_front(CurrentPricingProblem.Capacity, CapacityPlusTolerance, CurrentPricingProblem.CandidateMergeLabels, CurrentPricingProblem.CurrentDSSRNotInNeighbourhood);

			//Create Layered Labeling Algorithm
			LabelingAlgorithms.emplace_front(CurrentPricingProblem, StandardExtenders.front(), BogusFinalExtender, *CurrentDominator, NGZeroLoadMergers.front(), UseLimitedArcs, MaxMergeLabels, SolvedPricingProblems);

		}
	}

	//Initialize algorithm for the pricing problems from customer to depot:
	//*********************************************************************
	//Go over all relevant pricing problems from customer to depot
	for (auto RelevantPricingProblem = RelevantCustomerDepotPricingProblems.begin(); RelevantPricingProblem != RelevantCustomerDepotPricingProblems.end(); ++RelevantPricingProblem){

		//Obtain current pricing problem
		PStep_PricingProblem &CurrentPricingProblem = (**RelevantPricingProblem);

		//Check whether according to DSSR this pricing problem is redundant
		if (CurrentPricingProblem.RerunRequired){

			//Obtain current source
			short int iMinusOne = CurrentPricingProblem.Source - 1;
			//Obtain demand
			double* Demand = CurrentPricingProblem.Demand;
			//Obtain capacity
			double Capacity = CurrentPricingProblem.Capacity;
			//Obtain capacity plus tolerance
			double CapacityPlusTolerance = Capacity + Tolerance;

			//Create Reachability setter
			NGReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance, CurrentPricingProblem.CurrentDSSRNotInNeighbourhood);
			//Set current reachability setter
			CurrentReachabilitySetter = &(NGReachabilitySetters.front());
			//Check whether reachability should be checked
			if (!DoNotCheckReachability){
				//Create dominator
				DSSRNGReachabilityDominators.emplace_front(Tolerance, CurrentPricingProblem.CurrentDSSRNeighbourhoods);
				//Set current dominator
				CurrentDominator = &(DSSRNGReachabilityDominators.front());
			}
			
			//Create standard extender
			StandardExtenders.emplace_front(Demand, CurrentPricingProblem.ReducedArcCosts, *CurrentReachabilitySetter);
			//Create merger
			NGMaxLoadMergers.emplace_front(Capacity, CapacityPlusTolerance, CurrentPricingProblem.CandidateMergeLabels, CurrentPricingProblem.CurrentDSSRNotInNeighbourhood);

			//Create Layered Labeling Algorithm
			LabelingAlgorithms.emplace_front(CurrentPricingProblem, StandardExtenders.front(), BogusFinalExtender, *CurrentDominator, NGMaxLoadMergers.front(), UseLimitedArcs, MaxMergeLabels, SolvedPricingProblems);

		}
	}

	//Initialize algorithm for the pricing problems from customer to customers:
	//*************************************************************************
	//Go over all relevant pricing problems from customer to customer
	for (auto RelevantPricingProblem = RelevantCustomerCustomerPricingProblems.begin(); RelevantPricingProblem != RelevantCustomerCustomerPricingProblems.end(); ++RelevantPricingProblem){

		//Obtain current source and sink
		short int i = (*RelevantPricingProblem)->Source;
		short int iMinusOne = i - 1;
		short int j = (*RelevantPricingProblem)->Sink;
		short int jMinusOne = j - 1;

		//Initialize indicators, indicating which customer, i or j, has larger Nu
		short int LargeNuCustomer = iMinusOne;
		short int SmallNuCustomer = jMinusOne;
		//Set indictors to the right value
		if (Nu[LargeNuCustomer] < Nu[SmallNuCustomer]){
			LargeNuCustomer = jMinusOne;
			SmallNuCustomer = iMinusOne;
		}

		//Check whether the p-step from LargeNuCustomer to SmallNuCustomer has a cost
		//lower or equal to the cost of the same p-step reversed.
		//Keep in mind that with strict inequality, the starting load of 'Large to Small' is set to the maximum,
		//while the reverse has starting load 0. In case equality, this is irrelevant.
		if (2 * (Mu[SmallNuCustomer] - Mu[LargeNuCustomer]) - Nu[LargeNuCustomer] * ((*RelevantPricingProblem)->Capacity + (*RelevantPricingProblem)->Demand[LargeNuCustomer]) + Nu[SmallNuCustomer] * ((*RelevantPricingProblem)->Capacity + (*RelevantPricingProblem)->Demand[SmallNuCustomer]) < -Tolerance){
			//A p-step from LargeNuCustomer to SmallNuCustomer has lower cost than its reverse.

			//Obtain current pricing problem
			PStep_PricingProblem* TempPricingProblem;
			if (LargeNuCustomer == iMinusOne){
				TempPricingProblem = *RelevantPricingProblem;
			}
			else{
				TempPricingProblem = &PricingProblems[j][i];
			}
			PStep_PricingProblem &CurrentPricingProblem = *TempPricingProblem;

			//Check whether according to DSSR this pricing problem is redundant
			if (CurrentPricingProblem.RerunRequired){

				//Set up the algorithm to generate p-steps with maximum load:

				//Obtain demand
				double* Demand = CurrentPricingProblem.Demand;
				//Obtain capacity
				double Capacity = CurrentPricingProblem.Capacity;
				//Obtain capacity plus tolerance
				double CapacityPlusTolerance = Capacity + Tolerance;

				//Create Reachability setter
				NGReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance, CurrentPricingProblem.CurrentDSSRNotInNeighbourhood);
				//Set current reachability setter
				CurrentReachabilitySetter = &(NGReachabilitySetters.front());
				//Check whether reachability should be checked
				if (!DoNotCheckReachability){
					//Create dominator
					DSSRNGReachabilityDominators.emplace_front(Tolerance, CurrentPricingProblem.CurrentDSSRNeighbourhoods);
					//Set current dominator
					CurrentDominator = &(DSSRNGReachabilityDominators.front());
				}
			
				//Create standard extender
				StandardExtenders.emplace_front(Demand, CurrentPricingProblem.ReducedArcCosts, *CurrentReachabilitySetter);
				//Create merger
				NGMaxLoadMergers.emplace_front(Capacity, CapacityPlusTolerance, CurrentPricingProblem.CandidateMergeLabels, CurrentPricingProblem.CurrentDSSRNotInNeighbourhood);

				//Create Layered Labeling Algorithm
				LabelingAlgorithms.emplace_front(CurrentPricingProblem, StandardExtenders.front(), BogusFinalExtender, *CurrentDominator, NGMaxLoadMergers.front(), UseLimitedArcs, MaxMergeLabels, SolvedPricingProblems);

			}
		}
		else{
			//A p-step from SmallNuCustomer to LargeNuCustomer has lower or equal cost compared to the reverse.

			//Obtain current pricing problem
			PStep_PricingProblem* TempPricingProblem;
			if (SmallNuCustomer == iMinusOne){
				TempPricingProblem = *RelevantPricingProblem;
			}
			else{
				TempPricingProblem = &PricingProblems[j][i];
			}
			PStep_PricingProblem &CurrentPricingProblem = *TempPricingProblem;

			//Check whether according to DSSR this pricing problem is redundant
			if (CurrentPricingProblem.RerunRequired){

				//Set up the algorithm to generate p-steps with zero load:

				//Obtain demand
				double* Demand = CurrentPricingProblem.Demand;
				//Obtain capacity
				double Capacity = CurrentPricingProblem.Capacity;
				//Obtain capacity plus tolerance
				double CapacityPlusTolerance = Capacity + Tolerance;

				//Create Reachability setter
				NGReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance, CurrentPricingProblem.CurrentDSSRNotInNeighbourhood);
				//Set current reachability setter
				CurrentReachabilitySetter = &(NGReachabilitySetters.front());
				//Check whether reachability should be checked
				if (!DoNotCheckReachability){
					//Create dominator
					DSSRNGReachabilityDominators.emplace_front(Tolerance, CurrentPricingProblem.CurrentDSSRNeighbourhoods);
					//Set current dominator
					CurrentDominator = &(DSSRNGReachabilityDominators.front());
				}

				//Create standard extender
				StandardExtenders.emplace_front(Demand, CurrentPricingProblem.ReducedArcCosts, *CurrentReachabilitySetter);
				//Create merger
				NGZeroLoadMergers.emplace_front(Capacity, CapacityPlusTolerance, CurrentPricingProblem.CandidateMergeLabels, CurrentPricingProblem.CurrentDSSRNotInNeighbourhood);

				//Create Layered Labeling Algorithm
				LabelingAlgorithms.emplace_front(CurrentPricingProblem, StandardExtenders.front(), BogusFinalExtender, *CurrentDominator, NGZeroLoadMergers.front(), UseLimitedArcs, MaxMergeLabels, SolvedPricingProblems);

			}
		}

	}

	//Solve pricing problems:
	//*****************************************************************************************

	//Make a list of pointers to the shortest path algorithms which refer to the Layered Labeling Algorithms
	std::forward_list<PStep_ShortestPathAlgorithm*> TempList;
	for (auto CurrentLA = LabelingAlgorithms.begin(); CurrentLA != LabelingAlgorithms.end(); ++CurrentLA){
		TempList.push_front(&(*CurrentLA));
	}

	//Solve
	Solver.Solve(TempList);

	//Add p-steps:
	//*****************************************************************************************

	//Add
	Adder.AddMultiplePPCandidateMergeLabels(SolvedPricingProblems);

}

//Neighbourhood functions
//------------------------------------------------------------------------------------

//Copy the current DSSRNeighbourhoods to old DSSRNeighbourhoods for all relevant pricining problems
//which require a rerun.
void PStep_ColumnGenerator19::CopyCurrentDSSRNeighbourhoodsToOld(){

	//Obtain lists of relevant pricing problems
	std::list<PStep_PricingProblem*> &RelevantDepotCustomerPricingProblems = AlgorithmMembers.RelevantDepotCustomerPricingProblems;
	std::list<PStep_PricingProblem*> &RelevantCustomerDepotPricingProblems = AlgorithmMembers.RelevantCustomerDepotPricingProblems;
	std::list<PStep_PricingProblem*> &RelevantCustomerCustomerPricingProblems = AlgorithmMembers.RelevantCustomerCustomerPricingProblems;

	//Check whether the depot-depot pricing problem is relevant and a rerun is required
	if (AlgorithmMembers.AlgorithmSettings.p > 1 && AlgorithmMembers.PricingProblems[0][0].RerunRequired){
		AlgorithmMembers.PricingProblems[0][0].CopyCurrentDSSRNeighbourhoodsToOld();
	}

	//Go over all relevant Depot-Customer pricing problems
	for (auto CurrentPricingProblem = RelevantDepotCustomerPricingProblems.begin(); CurrentPricingProblem != RelevantDepotCustomerPricingProblems.end(); ++CurrentPricingProblem){
		//Check whether a rerun is required
		if ((*CurrentPricingProblem)->RerunRequired){
			//Copy
			(*CurrentPricingProblem)->CopyCurrentDSSRNeighbourhoodsToOld();
		}
	}
	//Go over all relevant Customer-Depot pricing problems
	for (auto CurrentPricingProblem = RelevantCustomerDepotPricingProblems.begin(); CurrentPricingProblem != RelevantCustomerDepotPricingProblems.end(); ++CurrentPricingProblem){
		//Check whether a rerun is required
		if ((*CurrentPricingProblem)->RerunRequired){
			//Copy
			(*CurrentPricingProblem)->CopyCurrentDSSRNeighbourhoodsToOld();
		}
	}
	//Go over all relevant Customer-Customer pricing problems
	for (auto CurrentPricingProblem = RelevantCustomerCustomerPricingProblems.begin(); CurrentPricingProblem != RelevantCustomerCustomerPricingProblems.end(); ++CurrentPricingProblem){
		//Check whether a rerun is required
		if ((*CurrentPricingProblem)->RerunRequired){
			//Copy
			(*CurrentPricingProblem)->CopyCurrentDSSRNeighbourhoodsToOld();
		}
		//Also check the 'reverse' pricing problem
		if (AlgorithmMembers.PricingProblems[(*CurrentPricingProblem)->Sink][(*CurrentPricingProblem)->Source].RerunRequired){
			//Copy
			AlgorithmMembers.PricingProblems[(*CurrentPricingProblem)->Sink][(*CurrentPricingProblem)->Source].CopyCurrentDSSRNeighbourhoodsToOld();
		}
	}

}

//Completion bound functions
//------------------------------------------------------------------------------------

//Obtain the "second" half of the completion bounds for every relevant pricing problem
//that requires a rerun.
//That is, obtain the values of ForwardCompletionBounds[l][i], for all customers i and
//layers l such that MaxNumberOfForwardArcs < l < NumberOfForwardLayers.
//Furthermore, obtain the values of BackwardCompletionBounds[l][i] for all customers i
//and layers l such that MaxNumberOfBackwardArcs < l < NumberOfBackwardLayers.
//NOTE: It is assumed that ForwardLabels and BackwardLabels are sorted from lowest reduced costs
//		to highest.
void PStep_ColumnGenerator19::ObtainEverySecondHalfOfCompletionBounds(){

	//Obtain minus tolerance
	double MinusTolerance = -AlgorithmMembers.Tolerance;

	//Obtain lists of relevant pricing problems
	std::list<PStep_PricingProblem*> &RelevantDepotCustomerPricingProblems = AlgorithmMembers.RelevantDepotCustomerPricingProblems;
	std::list<PStep_PricingProblem*> &RelevantCustomerDepotPricingProblems = AlgorithmMembers.RelevantCustomerDepotPricingProblems;
	std::list<PStep_PricingProblem*> &RelevantCustomerCustomerPricingProblems = AlgorithmMembers.RelevantCustomerCustomerPricingProblems;

	//Check whether the depot-depot pricing problem is relevant and a rerun is required
	if (AlgorithmMembers.AlgorithmSettings.p > 1 && AlgorithmMembers.PricingProblems[0][0].RerunRequired){
		AlgorithmMembers.PricingProblems[0][0].ObtainSecondHalfOfCompletionBounds(MinusTolerance);
	}

	//Go over all relevant Depot-Customer pricing problems
	for (auto CurrentPricingProblem = RelevantDepotCustomerPricingProblems.begin(); CurrentPricingProblem != RelevantDepotCustomerPricingProblems.end(); ++CurrentPricingProblem){
		//Check whether a rerun is required
		if ((*CurrentPricingProblem)->RerunRequired){
			//Copy
			(*CurrentPricingProblem)->ObtainSecondHalfOfCompletionBounds(MinusTolerance);
		}
	}
	//Go over all relevant Customer-Depot pricing problems
	for (auto CurrentPricingProblem = RelevantCustomerDepotPricingProblems.begin(); CurrentPricingProblem != RelevantCustomerDepotPricingProblems.end(); ++CurrentPricingProblem){
		//Check whether a rerun is required
		if ((*CurrentPricingProblem)->RerunRequired){
			//Copy
			(*CurrentPricingProblem)->ObtainSecondHalfOfCompletionBounds(MinusTolerance);
		}
	}
	//Go over all relevant Customer-Customer pricing problems
	for (auto CurrentPricingProblem = RelevantCustomerCustomerPricingProblems.begin(); CurrentPricingProblem != RelevantCustomerCustomerPricingProblems.end(); ++CurrentPricingProblem){
		//Check whether a rerun is required
		if ((*CurrentPricingProblem)->RerunRequired){
			//Copy
			(*CurrentPricingProblem)->ObtainSecondHalfOfCompletionBounds(MinusTolerance);
		}
		//Also check the 'reverse' pricing problem
		if (AlgorithmMembers.PricingProblems[(*CurrentPricingProblem)->Sink][(*CurrentPricingProblem)->Source].RerunRequired){
			//Copy
			AlgorithmMembers.PricingProblems[(*CurrentPricingProblem)->Sink][(*CurrentPricingProblem)->Source].ObtainSecondHalfOfCompletionBounds(MinusTolerance);
		}
	}

}

//Obtain the "first" half of the completion bounds for every relevant pricing problem
//that requires a rerun.
//That is, obtain the values of ForwardCompletionBounds[l][i], for all customers i and
//layers l such that 0 < l <= MaxNumberOfForwardArcs.
//Furthermore, obtain the values of ForwardCompletionBounds[l][i] for all customers i
//and layers l such that 0 < l <= MaxNumberOfBackwardArcs.
//NOTE: It is assumed that ForwardLabels and BackwardLabels are sorted from lowest reduced costs
//		to highest.
void PStep_ColumnGenerator19::ObtainEveryFirstHalfOfCompletionBounds(){

	//Obtain minus tolerance
	double MinusTolerance = -AlgorithmMembers.Tolerance;

	//Obtain lists of relevant pricing problems
	std::list<PStep_PricingProblem*> &RelevantDepotCustomerPricingProblems = AlgorithmMembers.RelevantDepotCustomerPricingProblems;
	std::list<PStep_PricingProblem*> &RelevantCustomerDepotPricingProblems = AlgorithmMembers.RelevantCustomerDepotPricingProblems;
	std::list<PStep_PricingProblem*> &RelevantCustomerCustomerPricingProblems = AlgorithmMembers.RelevantCustomerCustomerPricingProblems;

	//Check whether the depot-depot pricing problem is relevant and a rerun is required
	if (AlgorithmMembers.AlgorithmSettings.p > 1 && AlgorithmMembers.PricingProblems[0][0].RerunRequired){
		AlgorithmMembers.PricingProblems[0][0].ObtainFirstHalfOfCompletionBounds(MinusTolerance);
	}

	//Go over all relevant Depot-Customer pricing problems
	for (auto CurrentPricingProblem = RelevantDepotCustomerPricingProblems.begin(); CurrentPricingProblem != RelevantDepotCustomerPricingProblems.end(); ++CurrentPricingProblem){
		//Check whether a rerun is required
		if ((*CurrentPricingProblem)->RerunRequired){
			//Copy
			(*CurrentPricingProblem)->ObtainFirstHalfOfCompletionBounds(MinusTolerance);
		}
	}
	//Go over all relevant Customer-Depot pricing problems
	for (auto CurrentPricingProblem = RelevantCustomerDepotPricingProblems.begin(); CurrentPricingProblem != RelevantCustomerDepotPricingProblems.end(); ++CurrentPricingProblem){
		//Check whether a rerun is required
		if ((*CurrentPricingProblem)->RerunRequired){
			//Copy
			(*CurrentPricingProblem)->ObtainFirstHalfOfCompletionBounds(MinusTolerance);
		}
	}
	//Go over all relevant Customer-Customer pricing problems
	for (auto CurrentPricingProblem = RelevantCustomerCustomerPricingProblems.begin(); CurrentPricingProblem != RelevantCustomerCustomerPricingProblems.end(); ++CurrentPricingProblem){
		//Check whether a rerun is required
		if ((*CurrentPricingProblem)->RerunRequired){
			//Copy
			(*CurrentPricingProblem)->ObtainFirstHalfOfCompletionBounds(MinusTolerance);
		}
		//Also check the 'reverse' pricing problem
		if (AlgorithmMembers.PricingProblems[(*CurrentPricingProblem)->Sink][(*CurrentPricingProblem)->Source].RerunRequired){
			//Copy
			AlgorithmMembers.PricingProblems[(*CurrentPricingProblem)->Sink][(*CurrentPricingProblem)->Source].ObtainFirstHalfOfCompletionBounds(MinusTolerance);
		}
	}

}

//Continue forward and backward labeling after a bidirectional labeling run.
//The forward and backward labeling will be "completed" and the results will be
//used to obtain completion bounds for a next run of bidirectional labeling.
//The labelng algorithm will make use of completion bounds (those found by 
//ObtainEverySecondHalfOfCompletionBounds).
void PStep_ColumnGenerator19::ContinueForwardAndBackwardLabeling(){

	//Initialization:
	//*****************************************************************************************

	//Obtain p
	short int p = AlgorithmMembers.AlgorithmSettings.p;
	//Obtain Tolerance
	double Tolerance = AlgorithmMembers.Tolerance;
	//Obtain pricing problems
	PStep_PricingProblem** (&PricingProblems) = AlgorithmMembers.PricingProblems;
	//Obtain lists of relevant pricing problems
	std::list<PStep_PricingProblem*> &RelevantDepotCustomerPricingProblems = AlgorithmMembers.RelevantDepotCustomerPricingProblems;
	std::list<PStep_PricingProblem*> &RelevantCustomerDepotPricingProblems = AlgorithmMembers.RelevantCustomerDepotPricingProblems;
	std::list<PStep_PricingProblem*> &RelevantCustomerCustomerPricingProblems = AlgorithmMembers.RelevantCustomerCustomerPricingProblems;

	//Initialize list of labeling algorithms
	std::forward_list<PStep_CompleteBiDirectionalLayeredLabeling> LabelingAlgorithms;

	//Initialize reachability setters:
	//********************************
	//Initialize Container for PStep_NGReachabilitySetter
	std::forward_list<PStep_NGReachabilitySetter> NGReachabilitySetters;
	//Initialize pointer to a current reachability setter
	PStep_ReachabilitySetter* CurrentReachabilitySetter;

	//Initialize extenders:
	//*********************
	//Initialize Container for PStep_StandardExtenders
	std::forward_list<PStep_StandardExtender> StandardExtenders;
	//Initialize bogus PStep_FinalExtender
	PStep_FinalExtender BogusFinalExtender = PStep_FinalExtender(0, 0, 0);

	//Initialize bogus list of solved pricing problems
	std::forward_list<PStep_PricingProblem*> BogusSolvedPricingProblems;

	//Initialize dominators:
	//**********************
	//Initialize load dominator
	PStep_LoadDominator LoadDominator(Tolerance);
	//Initialize pointer to the current dominator
	PStep_Dominator* CurrentDominator = &LoadDominator;
	//Initialize Container for PStep_NGReachabilityDominator, to be used
	//if dynamic state space relaxation is applied and LoadDominator should not be used.
	std::forward_list<PStep_NGReachabilityDominator> DSSRNGReachabilityDominators;

	//Initialize algorithm for the pricing problem from depot to depot:
	//*****************************************************************
	//Check whether p is not 1, in which case this pricing problem is nonsense.
	if (p > 1){

		//Obtain pricing problem
		PStep_PricingProblem &CurrentPricingProblem = PricingProblems[0][0];

		//Check whether according to DSSR this pricing problem is redundant
		if (CurrentPricingProblem.RerunRequired){

			//Obtain demand
			double* Demand = CurrentPricingProblem.Demand;
			//Obtain capacity plus tolerance
			double CapacityPlusTolerance = CurrentPricingProblem.Capacity + Tolerance;

			//Create Reachability setter
			NGReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance, CurrentPricingProblem.OldDSSRNotInNeighbourhood);
			//Set current reachability setter
			CurrentReachabilitySetter = &(NGReachabilitySetters.front());
			//Check whether reachability should be checked
			if (!DoNotCheckReachability){
				//Create dominator
				DSSRNGReachabilityDominators.emplace_front(Tolerance, CurrentPricingProblem.OldDSSRNeighbourhoods);
				//Set current dominator
				CurrentDominator = &(DSSRNGReachabilityDominators.front());
			}

			//Create standard extender
			StandardExtenders.emplace_front(Demand, CurrentPricingProblem.ReducedArcCosts, *CurrentReachabilitySetter);

			//Create Labeling Algorithm
			LabelingAlgorithms.emplace_front(CurrentPricingProblem, StandardExtenders.front(), BogusFinalExtender, *CurrentDominator, UseLimitedArcs, BogusSolvedPricingProblems);
		}
	}

	//Initialize algorithm for the pricing problems from depot to customers:
	//**********************************************************************
	//Go over all relevant pricing problems from depot to customer
	for (auto RelevantPricingProblem = RelevantDepotCustomerPricingProblems.begin(); RelevantPricingProblem != RelevantDepotCustomerPricingProblems.end(); ++RelevantPricingProblem){

		//Obtain current pricing problem
		PStep_PricingProblem &CurrentPricingProblem = (**RelevantPricingProblem);
		//Check whether according to DSSR this pricing problem is redundant
		if (CurrentPricingProblem.RerunRequired){

			//Obtain current sink
			short int jMinusOne = CurrentPricingProblem.Sink - 1;
			//Obtain demand
			double* Demand = CurrentPricingProblem.Demand;
			//Obtain capacity plus tolerance
			double CapacityPlusTolerance = CurrentPricingProblem.Capacity + Tolerance;

			//Create Reachability setter
			NGReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance, CurrentPricingProblem.OldDSSRNotInNeighbourhood);
			//Set current reachability setter
			CurrentReachabilitySetter = &(NGReachabilitySetters.front());
			//Check whether reachability should be checked
			if (!DoNotCheckReachability){
				//Create dominator
				DSSRNGReachabilityDominators.emplace_front(Tolerance, CurrentPricingProblem.OldDSSRNeighbourhoods);
				//Set current dominator
				CurrentDominator = &(DSSRNGReachabilityDominators.front());
			}
			
			//Create standard extender
			StandardExtenders.emplace_front(Demand, CurrentPricingProblem.ReducedArcCosts, *CurrentReachabilitySetter);

			//Create Layered Labeling Algorithm
			LabelingAlgorithms.emplace_front(CurrentPricingProblem, StandardExtenders.front(), BogusFinalExtender, *CurrentDominator, UseLimitedArcs, BogusSolvedPricingProblems);

		}
	}

	//Initialize algorithm for the pricing problems from customer to depot:
	//*********************************************************************
	//Go over all relevant pricing problems from customer to depot
	for (auto RelevantPricingProblem = RelevantCustomerDepotPricingProblems.begin(); RelevantPricingProblem != RelevantCustomerDepotPricingProblems.end(); ++RelevantPricingProblem){

		//Obtain current pricing problem
		PStep_PricingProblem &CurrentPricingProblem = (**RelevantPricingProblem);

		//Check whether according to DSSR this pricing problem is redundant
		if (CurrentPricingProblem.RerunRequired){

			//Obtain current source
			short int iMinusOne = CurrentPricingProblem.Source - 1;
			//Obtain demand
			double* Demand = CurrentPricingProblem.Demand;
			//Obtain capacity
			double Capacity = CurrentPricingProblem.Capacity;
			//Obtain capacity plus tolerance
			double CapacityPlusTolerance = Capacity + Tolerance;

			//Create Reachability setter
			NGReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance, CurrentPricingProblem.OldDSSRNotInNeighbourhood);
			//Set current reachability setter
			CurrentReachabilitySetter = &(NGReachabilitySetters.front());
			//Check whether reachability should be checked
			if (!DoNotCheckReachability){
				//Create dominator
				DSSRNGReachabilityDominators.emplace_front(Tolerance, CurrentPricingProblem.OldDSSRNeighbourhoods);
				//Set current dominator
				CurrentDominator = &(DSSRNGReachabilityDominators.front());
			}
		
			//Create standard extender
			StandardExtenders.emplace_front(Demand, CurrentPricingProblem.ReducedArcCosts, *CurrentReachabilitySetter);
			
			//Create Layered Labeling Algorithm
			LabelingAlgorithms.emplace_front(CurrentPricingProblem, StandardExtenders.front(), BogusFinalExtender, *CurrentDominator, UseLimitedArcs, BogusSolvedPricingProblems);

		}

	}

	//Initialize algorithm for the pricing problems from customer to customers:
	//*************************************************************************
	//Go over all relevant pricing problems from customer to customer
	for (auto RelevantPricingProblem = RelevantCustomerCustomerPricingProblems.begin(); RelevantPricingProblem != RelevantCustomerCustomerPricingProblems.end(); ++RelevantPricingProblem){

		//Obtain current source and sink
		short int i = (*RelevantPricingProblem)->Source;
		short int iMinusOne = i - 1;
		short int j = (*RelevantPricingProblem)->Sink;
		short int jMinusOne = j - 1;

		//Initialize indicators, indicating which customer, i or j, has larger Nu
		short int LargeNuCustomer = iMinusOne;
		short int SmallNuCustomer = jMinusOne;
		//Set indictors to the right value
		if (Nu[LargeNuCustomer] < Nu[SmallNuCustomer]){
			LargeNuCustomer = jMinusOne;
			SmallNuCustomer = iMinusOne;
		}

		//Check whether the p-step from LargeNuCustomer to SmallNuCustomer has a cost
		//lower or equal to the cost of the same p-step reversed.
		//Keep in mind that with strict inequality, the starting load of 'Large to Small' is set to the maximum,
		//while the reverse has starting load 0. In case equality, this is irrelevant.
		if (2 * (Mu[SmallNuCustomer] - Mu[LargeNuCustomer]) - Nu[LargeNuCustomer] * ((*RelevantPricingProblem)->Capacity + (*RelevantPricingProblem)->Demand[LargeNuCustomer]) + Nu[SmallNuCustomer] * ((*RelevantPricingProblem)->Capacity + (*RelevantPricingProblem)->Demand[SmallNuCustomer]) < -Tolerance){
			//A p-step from LargeNuCustomer to SmallNuCustomer has lower cost than its reverse.

			//Obtain current pricing problem
			PStep_PricingProblem* TempPricingProblem;
			if (LargeNuCustomer == iMinusOne){
				TempPricingProblem = *RelevantPricingProblem;
			}
			else{
				TempPricingProblem = &PricingProblems[j][i];
			}
			PStep_PricingProblem &CurrentPricingProblem = *TempPricingProblem;

			//Check whether according to DSSR this pricing problem is redundant
			if (CurrentPricingProblem.RerunRequired){

				//Set up the algorithm to generate p-steps with maximum load:

				//Obtain demand
				double* Demand = CurrentPricingProblem.Demand;
				//Obtain capacity
				double Capacity = CurrentPricingProblem.Capacity;
				//Obtain capacity plus tolerance
				double CapacityPlusTolerance = Capacity + Tolerance;

				//Create Reachability setter
				NGReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance, CurrentPricingProblem.OldDSSRNotInNeighbourhood);
				//Set current reachability setter
				CurrentReachabilitySetter = &(NGReachabilitySetters.front());
				//Check whether reachability should be checked
				if (!DoNotCheckReachability){
					//Create dominator
					DSSRNGReachabilityDominators.emplace_front(Tolerance, CurrentPricingProblem.OldDSSRNeighbourhoods);
					//Set current dominator
					CurrentDominator = &(DSSRNGReachabilityDominators.front());
				}
				
				//Create standard extender
				StandardExtenders.emplace_front(Demand, CurrentPricingProblem.ReducedArcCosts, *CurrentReachabilitySetter);

				//Create Layered Labeling Algorithm
				LabelingAlgorithms.emplace_front(CurrentPricingProblem, StandardExtenders.front(), BogusFinalExtender, *CurrentDominator, UseLimitedArcs, BogusSolvedPricingProblems);

			}
		}
		else{
			//A p-step from SmallNuCustomer to LargeNuCustomer has lower or equal cost compared to the reverse.

			//Obtain current pricing problem
			PStep_PricingProblem* TempPricingProblem;
			if (SmallNuCustomer == iMinusOne){
				TempPricingProblem = *RelevantPricingProblem;
			}
			else{
				TempPricingProblem = &PricingProblems[j][i];
			}
			PStep_PricingProblem &CurrentPricingProblem = *TempPricingProblem;

			//Check whether according to DSSR this pricing problem is redundant
			if (CurrentPricingProblem.RerunRequired){

				//Set up the algorithm to generate p-steps with zero load:

				//Obtain demand
				double* Demand = CurrentPricingProblem.Demand;
				//Obtain capacity
				double Capacity = CurrentPricingProblem.Capacity;
				//Obtain capacity plus tolerance
				double CapacityPlusTolerance = Capacity + Tolerance;

				//Create Reachability setter
				NGReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance, CurrentPricingProblem.OldDSSRNotInNeighbourhood);
				//Set current reachability setter
				CurrentReachabilitySetter = &(NGReachabilitySetters.front());
				//Check whether reachability should be checked
				if (!DoNotCheckReachability){
					//Create dominator
					DSSRNGReachabilityDominators.emplace_front(Tolerance, CurrentPricingProblem.OldDSSRNeighbourhoods);
					//Set current dominator
					CurrentDominator = &(DSSRNGReachabilityDominators.front());
				}
				
				//Create standard extender
				StandardExtenders.emplace_front(Demand, CurrentPricingProblem.ReducedArcCosts, *CurrentReachabilitySetter);

				//Create Layered Labeling Algorithm
				LabelingAlgorithms.emplace_front(CurrentPricingProblem, StandardExtenders.front(), BogusFinalExtender, *CurrentDominator, UseLimitedArcs, BogusSolvedPricingProblems);

			}
		}

	}

	//Solve pricing problems:
	//*****************************************************************************************

	//Make a list of pointers to the shortest path algorithms which refer to the Layered Labeling Algorithms
	std::forward_list<PStep_ShortestPathAlgorithm*> TempList;
	for (auto CurrentLA = LabelingAlgorithms.begin(); CurrentLA != LabelingAlgorithms.end(); ++CurrentLA){
		TempList.push_front(&(*CurrentLA));
	}

	//Solve
	Solver.Solve(TempList);

}