/*Implementation of PStep_Adder

It contains the member functions of PStep_Adder and all derived classes

*/

#include "PStep_Adder.h"

//PStep_Adder:
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Backtrack function:
//------------------------------------------------------------------------------------

//Backtrack FinalLabel and add the resulting pstep to AlgorithmMembers.PSteps
//and AlgorithmMembers.CurrentPSteps.
void PStep_Adder::Backtrack(PStep_FinalLabel& FinalLabel){

	//Add new p-step
	AlgorithmMembers.PSteps.emplace_back();
	//Obtain iterator to the newly added p-step
	auto NewPStep = AlgorithmMembers.PSteps.end();
	--NewPStep;
	//Add p-step to the list of p-steps in the current formulation
	AlgorithmMembers.CurrentPSteps.push_back(NewPStep);
	++AlgorithmMembers.NumberOfCurrentPSteps;
	//Obtain reference to the new p-step
	PStep& CurrentPStep = AlgorithmMembers.PSteps.back();

	//Obtain travel costs
	double** TravelCosts = AlgorithmMembers.Instance.TravelCosts;
	//Obtain the current label
	Label* CurrentLabel = &FinalLabel.FinalLabel;

	//Initialize values of the current p-step
	CurrentPStep.Cost = 0;	
	CurrentPStep.TotalLoad = FinalLabel.StartingLoad + CurrentLabel->Load;
	CurrentPStep.Locations.push_front(CurrentLabel->LastLocation);
	//Initialize the starting load of the p-step.
	//Note that it is actually the starting load plus the demand of the first customer.
	CurrentPStep.StartingLoad = FinalLabel.StartingLoad;

	//Backtrack labels
	while (CurrentLabel->PreviousLabel != 0){
		//Obtain new current label
		CurrentLabel = CurrentLabel->PreviousLabel;

		//Update values of the current p-step
		CurrentPStep.Cost += TravelCosts[CurrentLabel->LastLocation][CurrentPStep.Locations.front()];
		CurrentPStep.Locations.push_front(CurrentLabel->LastLocation);
	}

	//Add the demand of the first customer to the starting load
	if (CurrentLabel->LastLocation>0){
		CurrentPStep.StartingLoad += AlgorithmMembers.Instance.Demand[CurrentLabel->LastLocation - 1];
	}

}

//Backtrack and merge MergeLabel and add the resulting pstep to AlgorithmMembers.PSteps
//and AlgorithmMembers.CurrentPSteps.
void PStep_Adder::Backtrack(PStep_MergeLabel& MergeLabel){

	//Add new p-step
	AlgorithmMembers.PSteps.emplace_back();
	//Obtain iterator to the newly added p-step
	auto NewPStep = AlgorithmMembers.PSteps.end();
	--NewPStep;
	//Add p-step to the list of p-steps in the current formulation
	AlgorithmMembers.CurrentPSteps.push_back(NewPStep);
	++AlgorithmMembers.NumberOfCurrentPSteps;
	//Obtain reference to the new p-step
	PStep& CurrentPStep = AlgorithmMembers.PSteps.back();

	//Obtain travel costs
	double** TravelCosts = AlgorithmMembers.Instance.TravelCosts;
	//Obtain the current labels
	ForwardLabel* CurrentForwardLabel = &MergeLabel.CurrentForwardLabel;
	BackwardLabel* CurrentBackwardLabel = &MergeLabel.CurrentBackwardLabel;

	//Initialize values of the current p-step
	CurrentPStep.Cost = TravelCosts[CurrentForwardLabel->LastLocation][CurrentBackwardLabel->FirstLocation];
	CurrentPStep.TotalLoad = MergeLabel.StartingLoad + MergeLabel.TotalLoad;
	CurrentPStep.Locations.push_front(CurrentForwardLabel->LastLocation);
	CurrentPStep.Locations.push_back(CurrentBackwardLabel->FirstLocation);
	//Initialize the starting load of the p-step.
	//Note that it is actually the starting load plus the demand of the first customer.
	CurrentPStep.StartingLoad = MergeLabel.StartingLoad;

	//Backtrack forward labels
	while (CurrentForwardLabel->PreviousLabel != 0){
		//Obtain new current label
		CurrentForwardLabel = CurrentForwardLabel->PreviousLabel;

		//Update values of the current p-step
		CurrentPStep.Cost += TravelCosts[CurrentForwardLabel->LastLocation][CurrentPStep.Locations.front()];
		CurrentPStep.Locations.push_front(CurrentForwardLabel->LastLocation);
	}

	//Backtrack backward labels
	while (CurrentBackwardLabel->NextLabel != 0){
		//Obtain new current label
		CurrentBackwardLabel = CurrentBackwardLabel->NextLabel;

		//Update values of the current p-step
		CurrentPStep.Cost += TravelCosts[CurrentPStep.Locations.back()][CurrentBackwardLabel->FirstLocation];
		CurrentPStep.Locations.push_back(CurrentBackwardLabel->FirstLocation);
	}

	//Add the demand of the first customer to the starting load
	if (CurrentForwardLabel->LastLocation>0){
		CurrentPStep.StartingLoad += AlgorithmMembers.Instance.Demand[CurrentForwardLabel->LastLocation - 1];
	}

}

//PStep_AllPStepsAdder:
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Add p-steps function
//------------------------------------------------------------------------------------

//Add all p-steps created by backtracking labels to AlgorithmMembers.PSteps
//and AlgorithmMembers.CurrentPSteps.
void PStep_AllPStepsAdder::Add(std::forward_list<PStep_FinalLabel>& FinalLabels){

	//Go over all final labels
	for (auto CurrentFinalLabel = FinalLabels.begin(); CurrentFinalLabel != FinalLabels.end(); ++CurrentFinalLabel){
		//Backtrack
		Backtrack(*CurrentFinalLabel);
	}

}

//Create p-steps by backtracking labels found in CandidateLabels of in AlgorithmMembers.PricingProblems
//and adding them to the front of AlgorithmMembers.PSteps and AlgorithmMembers.CurrentPSteps.
//It is particularly designed for the case in which multiple pricing problems are considered.
void PStep_AllPStepsAdder::AddMultiplePPCandidateLabels(std::forward_list<PStep_PricingProblem*> &SolvedPricingProblems){

	//Check whether decremental state space relaxation is applied
	if (*ApplyDSSR){
		//Decremental state space relxation is applied.
		DSSRAddMultiplePPCandidateLabels(SolvedPricingProblems);
	}
	else{
		//Decremental state space relaxation is not applied.
		//Go over all pricing problems
		for (auto CurrentPricingProblem = SolvedPricingProblems.begin(); CurrentPricingProblem != SolvedPricingProblems.end(); ++CurrentPricingProblem){
			Add((*CurrentPricingProblem)->CandidateLabels);
		}
	}

}

//Add All p-steps in the list to the front of AlgorithmMembers.PSteps
//and AlgorithmMembers.CurrentPSteps.
void PStep_AllPStepsAdder::Add(std::forward_list<PStep> &PStepList){

	//Go over all p-steps in the list
	for (auto CurrentPStep = PStepList.begin(); CurrentPStep != PStepList.end(); ++CurrentPStep){
		//Add p-step to the list
		AlgorithmMembers.PSteps.push_back(*CurrentPStep);
		//Obtain iterator to the newly added p-step
		auto NewPStep = AlgorithmMembers.PSteps.end();
		--NewPStep;
		//Add p-step to the list of p-steps in the current formulation
		AlgorithmMembers.CurrentPSteps.push_back(NewPStep);
		++AlgorithmMembers.NumberOfCurrentPSteps;
	}

}

//Add All p-steps to the front of AlgorithmMembers.PSteps and
//AlgorithmMembers.CurrentPSteps.
//It is particularly designed for the case in which multiple pricing problems are considered.
void PStep_AllPStepsAdder::AddMultiplePPCandidatePSteps(std::forward_list<PStep_PricingProblem*> &SolvedPricingProblems){

	//Go over all pricing problems
	for (auto CurrentPricingProblem = SolvedPricingProblems.begin(); CurrentPricingProblem != SolvedPricingProblems.end(); ++CurrentPricingProblem){
		Add((*CurrentPricingProblem)->CandidatePSteps);
	}

}

//Create p-steps by merging and backtracking every label in MergeLabels and add ALL of them to
//the front of AlgorithmMembers.PSteps and AlgorithmMembers.CurrentPSteps.
void PStep_AllPStepsAdder::Add(std::forward_list<PStep_MergeLabel>& MergeLabels){

	//Go over all merge labels
	for (auto CurrentMergeLabel = MergeLabels.begin(); CurrentMergeLabel != MergeLabels.end(); ++CurrentMergeLabel){
		//Backtrack
		Backtrack(*CurrentMergeLabel);
	}

}

//Create p-steps by merging and backtracking the CandidateMergeLabels of the pricing problems in the
//list SolvedPricingProblems. Add all these p-steps to the front of AlgorithmMembers.PSteps and
//AlgorithmMembers.CurrentPSteps.
//It is particularly designed for the case in which multiple pricing problems are considered.
void PStep_AllPStepsAdder::AddMultiplePPCandidateMergeLabels(std::forward_list<PStep_PricingProblem*> &SolvedPricingProblems){

	//Check whether decremental state space relaxation is applied
	if (*ApplyDSSR){
		//Decremental state space relxation is applied.
		DSSRAddMultiplePPCandidateMergeLabels(SolvedPricingProblems);
	}
	else{
		//Decremental state space relaxation is not applied.
		//Go over all pricing problems
		for (auto CurrentPricingProblem = SolvedPricingProblems.begin(); CurrentPricingProblem != SolvedPricingProblems.end(); ++CurrentPricingProblem){
			Add((*CurrentPricingProblem)->CandidateMergeLabels);
		}
	}

}

//Decremental state space relaxation functions:
//-------------------------------------------------------------------------------------

//Create p-steps by backtracking labels found in CandidateLabels of in AlgorithmMembers.PricingProblems.
//For these p-steps it is checked whether they are feasible ng-paths.
//If not, the neighborhoods of the corresponding pricing problem are updated.
//When only negative reduced cost p-steps which are not feasible ng-paths are found.
//RerunRequired is set to true. Otherwise (so if at least one negative reduced cost feasible
//ng-path is found, or no CandidateLabels were generated), it is set to false.
void PStep_AllPStepsAdder::DSSRAddMultiplePPCandidateLabels(std::forward_list<PStep_PricingProblem*> &SolvedPricingProblems){
	
	
	//Obtain the number of customers
	short int NumberOfCustomers = AlgorithmMembers.Instance.NumberOfCustomers;
	//Obtain neighborhoods
	bool** (&NotInNeighbourhood) = AlgorithmMembers.NotInNeighbourhood;

	//Initialize indicator indicating whether a feasible p-step was found among all pricing problems
	bool FeasiblePStepFound = false;
	//Initialize indicator indicating whether a forbidden cycle is found among all pricing problems
	bool ForbiddenCycleFound = false;

	//Go over all solved pricing problems
	for (auto CurrentSolvedPP = SolvedPricingProblems.begin(); CurrentSolvedPP != SolvedPricingProblems.end(); ++CurrentSolvedPP){

		//Obtain current pricing problem
		PStep_PricingProblem &CurrentPricingProblem = **CurrentSolvedPP;
		//Obtain maximum number of locations on a p-step for this pricing problem
		short int MaxNumberOfLocations = CurrentPricingProblem.MaxNumberOfArcs + 1;

		//Initialize ToAdd
		bool** ToAdd = new bool*[NumberOfCustomers];
		for (short int i = 0; i < NumberOfCustomers; ++i){
			ToAdd[i] = new bool[NumberOfCustomers];
			for (short int j = 0; j < NumberOfCustomers; ++j){
				ToAdd[i][j] = false;
			}
		}
		CurrentPricingProblem.ToAdd = ToAdd;

		//Initialize indicator indicating whether a forbidden cycle was found for this pricing problem.
		CurrentPricingProblem.ForbiddenCycleFound = false;

		//Go over all candidate labels
		for (auto CurrentLabel = CurrentPricingProblem.CandidateLabels.begin(); CurrentLabel != CurrentPricingProblem.CandidateLabels.end(); ++CurrentLabel){

			//Construct p-step
			Backtrack(*CurrentLabel);
			//Obtain p-step
			PStep& NewPStep = AlgorithmMembers.PSteps.back();

			//Check whether the NewPStep is a feasible ng-path according to the 'real'neighborhoods
			//(as oposed to being feasible for CurrentDSSRNeighborhoods):
			//-------------------------------------------------------------------------------------

			//Initialize indicator indicating whether a Forbidden Cycle is found for this p-step
			bool CurrentForbiddenCycleFound = false;

			//Initialize location resources
			//LocationResource[i][j] indicates whether the (i+1)'th location on the p-step 'remembers' visiting location j.
			//Here remembering is meant in the ng-sense, and j=0 is the first customer.
			bool** LocationResource = new bool*[MaxNumberOfLocations];
			//Initialize the information of the first location on the p-step:
			//Initialize current location
			auto CurrentLocation = NewPStep.Locations.begin();
			//Initialize location resources
			LocationResource[0] = new bool[NumberOfCustomers];
			for (short int j = 0; j < NumberOfCustomers; ++j){
				LocationResource[0][j] = false;
			}
			//Check whether the CurrentLocation is not the depot
			if (*CurrentLocation > 0){
				//The current location is not the depot, update the corresponding location resource
				LocationResource[0][(*CurrentLocation) - 1] = true;
			}
			//Initialize counter for the current location
			short int CurrentLocationCounter = 0;
			//Initialize next location
			++CurrentLocation;

			//Go over all locations on the p-step
			while (CurrentLocation != NewPStep.Locations.end() && !(CurrentForbiddenCycleFound)){
				//Check whether the next location is not the depot
				if (*CurrentLocation > 0){
					//The next location is not the depot

					//Obtain the current location index
					short int CurrentLocationIndex = *CurrentLocation - 1;

					//Check whether the next location constitutes a forbidden cycle
					if (LocationResource[CurrentLocationCounter][CurrentLocationIndex]){
						//A cycle has been found
						//Update indicator over all pricing problems
						ForbiddenCycleFound = true;
						//Update indicator for this specific pricing problem
						CurrentPricingProblem.ForbiddenCycleFound = true;
						//Update indicator for this specific p-step
						CurrentForbiddenCycleFound = true;
					}
					else{
						//Update location resources:
						//Update counters
						short int PreviousLocationCounter = CurrentLocationCounter;
						++CurrentLocationCounter;

						//Initialize resources
						LocationResource[CurrentLocationCounter] = new bool[NumberOfCustomers];
						//Go over all customers
						for (short int j = 0; j < NumberOfCustomers; ++j){
							//Check whether j is in the ng-neighborhood and the resource is used
							if (LocationResource[PreviousLocationCounter][j] && !(NotInNeighbourhood[CurrentLocationIndex][j])){
								LocationResource[CurrentLocationCounter][j] = true;
							}
							else{
								LocationResource[CurrentLocationCounter][j] = false;
							}
						}
						//Set the location resource of the current location
						LocationResource[CurrentLocationCounter][CurrentLocationIndex] = true;

						//Update NextLocation
						++CurrentLocation;
					}

				}//end check if the current location is the depot
				else{
					//The current location is the depot, updating it should terminate the while loop
					//Update NextLocation
					++CurrentLocation;
				}

			}//end go over all locations on the p-step

			//Check whether a forbidden cycle is found in the current p-step
			if (CurrentForbiddenCycleFound){
				//A forbidden cycle is found.

				//Update ToAdd:
				//Obtain current locationIndex
				short int CycleLocationIndex = *CurrentLocation;
				short int CycleLocationIndexMinusOne = CycleLocationIndex - 1;
				//Iterate CurrentLocation
				--CurrentLocation;
				//Go over all customers in the cycle
				while (*CurrentLocation != CycleLocationIndex){
					ToAdd[*CurrentLocation - 1][CycleLocationIndexMinusOne] = true;
					--CurrentLocation;
				}

				//Remove the current p-step from the pool
				AlgorithmMembers.PSteps.pop_back();
				AlgorithmMembers.CurrentPSteps.pop_back();
				--AlgorithmMembers.NumberOfCurrentPSteps;
			}
			else{
				//A forbidden cycle is not found, hence a feasible negative reduced cost p-step is found
				FeasiblePStepFound = true;
			}

			//Delete Locationresources
			for (; CurrentLocationCounter >= 0; --CurrentLocationCounter){
				delete[]LocationResource[CurrentLocationCounter];
			}
			delete[]LocationResource;

		}//end go over all candidate labels
		
	}//end go over all solved pricing problems

	
	//Process cycle checks:
	//-------------------------------------------------------------------------------------

	//Check whether a feasible p-steps has been found
	if (FeasiblePStepFound){
		//A feasible p-step is found

		//Update RerunRuired
		(*RerunRequired) = false;
	}
	//Otherwise, check whether p-steps with a forbidden cycle has been found
	else if (ForbiddenCycleFound){
		//A feasible p-step is not found, but a forbidden cycle was identified.

		//Go over all solved pricing problems
		for (auto CurrentSolvedPP = SolvedPricingProblems.begin(); CurrentSolvedPP != SolvedPricingProblems.end(); ++CurrentSolvedPP){
			//Check whether forbidden cycles have been found for this pricing problem
			if ((**CurrentSolvedPP).ForbiddenCycleFound){
				//Update neighborhoods:

				//Obtain current pricing problem
				PStep_PricingProblem &CurrentPricingProblem = **CurrentSolvedPP;

				//Obtain ToAdd
				bool** ToAdd = CurrentPricingProblem.ToAdd;

				//Go over all customer pairs
				for (short int i = 0; i < NumberOfCustomers; ++i){
					for (short int  j = 0; j < NumberOfCustomers; ++j){
						//Check whether j should be added to the neighborhood of i
						if (ToAdd[i][j]){
							//Add j to the neighborhood of i
							CurrentPricingProblem.CurrentDSSRNeighbourhoods[i].push_back(j);
							CurrentPricingProblem.CurrentDSSRNotInNeighbourhood[i][j] = false;
						}
					}
				}
			}
		}

		//Reinitialize RerunRuired
		(*RerunRequired) = true;
	}
	else{
		//No p-steps are found

		//Update RerunRuired
		(*RerunRequired) = false;
	}
	

	//clean
	//Go over all relevant pricing problems
	for (auto CurrentPricingProblem = SolvedPricingProblems.begin(); CurrentPricingProblem != SolvedPricingProblems.end(); ++CurrentPricingProblem){
		//Delete ToAdd
		for (short int i = 0; i < NumberOfCustomers; ++i){
			delete[](*CurrentPricingProblem)->ToAdd[i];
		}
		delete[](*CurrentPricingProblem)->ToAdd;
		(*CurrentPricingProblem)->ToAdd=0;
	}

}

//Create p-steps by merging and backtracking labels found in CandidateMergeLabels of
//AlgorithmMembers.PricingProblems.
//For these p-steps it is checked whether they are feasible ng-paths.
//If not, the neighborhoods of the corresponding pricing problem are updated and 
//RerunRequired of that pricing problem is set to true (otherwise false).
//When only negative reduced cost p-steps which are not feasible ng-paths are found.
//RerunRequired is set to true. Otherwise (so if at least one negative reduced cost feasible
//ng-path is found, or no CandidateMergeLabels were generated), it is set to false.
void PStep_AllPStepsAdder::DSSRAddMultiplePPCandidateMergeLabels(std::forward_list<PStep_PricingProblem*> &SolvedPricingProblems){

	//Obtain the number of customers
	short int NumberOfCustomers = AlgorithmMembers.Instance.NumberOfCustomers;
	//Obtain neighborhoods
	bool** (&NotInNeighbourhood) = AlgorithmMembers.NotInNeighbourhood;

	//Initialize indicator indicating whether a feasible p-step was found among all pricing problems
	bool FeasiblePStepFound = false;
	//Initialize indicator indicating whether a forbidden cycle is found among all pricing problems
	bool ForbiddenCycleFound = false;

	//Go over all solved pricing problems
	for (auto CurrentSolvedPP = SolvedPricingProblems.begin(); CurrentSolvedPP != SolvedPricingProblems.end(); ++CurrentSolvedPP){

		//Obtain current pricing problem
		PStep_PricingProblem &CurrentPricingProblem = **CurrentSolvedPP;
		//Obtain maximum number of locations on a p-step for this pricing problem
		short int MaxNumberOfLocations = CurrentPricingProblem.MaxNumberOfArcs + 1;

		//Initialize ToAdd
		bool** ToAdd = new bool*[NumberOfCustomers];
		for (short int i = 0; i < NumberOfCustomers; ++i){
			ToAdd[i] = new bool[NumberOfCustomers];
			for (short int j = 0; j < NumberOfCustomers; ++j){
				ToAdd[i][j] = false;
			}
		}
		CurrentPricingProblem.ToAdd = ToAdd;

		//Initialize indicator indicating whether a forbidden cycle was found for this pricing problem.
		CurrentPricingProblem.ForbiddenCycleFound = false;

		//Go over all candidate labels
		for (auto CurrentLabel = CurrentPricingProblem.CandidateMergeLabels.begin(); CurrentLabel != CurrentPricingProblem.CandidateMergeLabels.end(); ++CurrentLabel){

			//Construct p-step
			Backtrack(*CurrentLabel);
			//Obtain p-step
			PStep& NewPStep = AlgorithmMembers.PSteps.back();

			//Check whether the NewPStep is a feasible ng-path according to the 'real'neighborhoods
			//(as oposed to being feasible for CurrentDSSRNeighborhoods):
			//-------------------------------------------------------------------------------------

			//Initialize indicator indicating whether a Forbidden Cycle is found for this p-step
			bool CurrentForbiddenCycleFound = false;

			//Initialize location resources
			//LocationResource[i][j] indicates whether the (i+1)'th location on the p-step 'remembers' visiting location j.
			//Here remembering is meant in the ng-sense, and j=0 is the first customer.
			bool** LocationResource = new bool*[MaxNumberOfLocations];
			//Initialize the information of the first location on the p-step:
			//Initialize current location
			auto CurrentLocation = NewPStep.Locations.begin();
			//Initialize location resources
			LocationResource[0] = new bool[NumberOfCustomers];
			for (short int j = 0; j < NumberOfCustomers; ++j){
				LocationResource[0][j] = false;
			}
			//Check whether the CurrentLocation is not the depot
			if (*CurrentLocation > 0){
				//The current location is not the depot, update the corresponding location resource
				LocationResource[0][(*CurrentLocation) - 1] = true;
			}
			//Initialize counter for the current location
			short int CurrentLocationCounter = 0;
			//Initialize next location
			++CurrentLocation;

			//Go over all locations on the p-step
			while (CurrentLocation != NewPStep.Locations.end() && !(CurrentForbiddenCycleFound)){
				//Check whether the next location is not the depot
				if (*CurrentLocation > 0){
					//The next location is not the depot

					//Obtain the current location index
					short int CurrentLocationIndex = *CurrentLocation - 1;

					//Check whether the next location constitutes a forbidden cycle
					if (LocationResource[CurrentLocationCounter][CurrentLocationIndex]){
						//A cycle has been found
						//Update indicator over all pricing problems
						ForbiddenCycleFound = true;
						//Update indicator for this specific pricing problem
						CurrentPricingProblem.ForbiddenCycleFound = true;
						//Update indicator for this specific p-step
						CurrentForbiddenCycleFound = true;
					}
					else{
						//Update location resources:
						//Update counters
						short int PreviousLocationCounter = CurrentLocationCounter;
						++CurrentLocationCounter;

						//Initialize resources
						LocationResource[CurrentLocationCounter] = new bool[NumberOfCustomers];
						//Go over all customers
						for (short int j = 0; j < NumberOfCustomers; ++j){
							//Check whether j is in the ng-neighborhood and the resource is used
							if (LocationResource[PreviousLocationCounter][j] && !(NotInNeighbourhood[CurrentLocationIndex][j])){
								LocationResource[CurrentLocationCounter][j] = true;
							}
							else{
								LocationResource[CurrentLocationCounter][j] = false;
							}
						}
						//Set the location resource of the current location
						LocationResource[CurrentLocationCounter][CurrentLocationIndex] = true;

						//Update NextLocation
						++CurrentLocation;
					}

				}//end check if the current location is the depot
				else{
					//The current location is the depot, updating it should terminate the while loop
					//Update NextLocation
					++CurrentLocation;
				}

			}//end go over all locations on the p-step

			//Check whether a forbidden cycle is found in the current p-step
			if (CurrentForbiddenCycleFound){
				//A forbidden cycle is found.

				//Update ToAdd:
				//Obtain current locationIndex
				short int CycleLocationIndex = *CurrentLocation;
				short int CycleLocationIndexMinusOne = CycleLocationIndex - 1;
				//Iterate CurrentLocation
				--CurrentLocation;
				//Go over all customers in the cycle
				while (*CurrentLocation != CycleLocationIndex){
					ToAdd[*CurrentLocation - 1][CycleLocationIndexMinusOne] = true;
					--CurrentLocation;
				}

				//Remove the current p-step from the pool
				AlgorithmMembers.PSteps.pop_back();
				AlgorithmMembers.CurrentPSteps.pop_back();
				--AlgorithmMembers.NumberOfCurrentPSteps;
			}
			else{
				//A forbidden cycle is not found, hence a feasible negative reduced cost p-step is found
				FeasiblePStepFound = true;
			}

			//Delete Locationresources
			for (; CurrentLocationCounter >= 0; --CurrentLocationCounter){
				delete[]LocationResource[CurrentLocationCounter];
			}
			delete[]LocationResource;

		}//end go over all candidate labels

		//Set RerunRequired for this pricing problem
		CurrentPricingProblem.RerunRequired = CurrentPricingProblem.ForbiddenCycleFound;

	}//end go over all solved pricing problems


	//Process cycle checks:
	//-------------------------------------------------------------------------------------

	//Check whether a feasible p-steps has been found
	if (FeasiblePStepFound){
		//A feasible p-step is found

		//Update RerunRuired
		(*RerunRequired) = false;
	}
	//Otherwise, check whether p-steps with a forbidden cycle has been found
	else if (ForbiddenCycleFound){
		//A feasible p-step is not found, but a forbidden cycle was identified.

		//Go over all solved pricing problems
		for (auto CurrentSolvedPP = SolvedPricingProblems.begin(); CurrentSolvedPP != SolvedPricingProblems.end(); ++CurrentSolvedPP){
			//Check whether forbidden cycles have been found for this pricing problem
			if ((**CurrentSolvedPP).ForbiddenCycleFound){
				//Update neighborhoods:

				//Obtain current pricing problem
				PStep_PricingProblem &CurrentPricingProblem = **CurrentSolvedPP;

				//Obtain ToAdd
				bool** ToAdd = CurrentPricingProblem.ToAdd;

				//Go over all customer pairs
				for (short int i = 0; i < NumberOfCustomers; ++i){
					for (short int  j = 0; j < NumberOfCustomers; ++j){
						//Check whether j should be added to the neighborhood of i
						if (ToAdd[i][j]){
							//Add j to the neighborhood of i
							CurrentPricingProblem.CurrentDSSRNeighbourhoods[i].push_back(j);
							CurrentPricingProblem.CurrentDSSRNotInNeighbourhood[i][j] = false;
						}
					}
				}
			}
		}

		//Reinitialize RerunRuired
		(*RerunRequired) = true;
	}
	else{
		//No p-steps are found

		//Update RerunRuired
		(*RerunRequired) = false;
	}


	//clean
	//Go over all relevant pricing problems
	for (auto CurrentPricingProblem = SolvedPricingProblems.begin(); CurrentPricingProblem != SolvedPricingProblems.end(); ++CurrentPricingProblem){
		//Delete ToAdd
		for (short int i = 0; i < NumberOfCustomers; ++i){
			delete[](*CurrentPricingProblem)->ToAdd[i];
		}
		delete[](*CurrentPricingProblem)->ToAdd;
		(*CurrentPricingProblem)->ToAdd = 0;
	}

}