/*Implementation of PStep_ColumnGenerator.h

It contains the member functions of PStep_ColumnGenerator12

*/

#include "PStep_ColumnGenerator.h"

//PStep_ColumnGenerator12:
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

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

//The same as column generator 1, but now labels are only compared for dominance if they
//not only have visited the same number of arcs, but also have exactly the same load.
//NOTE: Column generator 12 only applies if the demand and capacity are integer!
void PStep_ColumnGenerator12::GenerateColumns(){

	GenerateColumns12();

}

//Solve pricing problem seperately for every(non - redundant) start and end node combination.
//The pricing problems are solved heuristically using column generator 1 where Reachability 
//is not considered in the Dominance check.
void PStep_ColumnGenerator12::GenerateColumns12(){

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

	//Obtain p
	short int p = AlgorithmMembers.AlgorithmSettings.p;
	//Obtain Tolerance
	double Tolerance = AlgorithmMembers.Tolerance;
	//Obtain indicator indicating whether ng-path relaxation is used
	bool UseNGPathRelaxation = AlgorithmMembers.AlgorithmSettings.UseNGPathRelaxation;
	//Obtain neighbourhoods
	std::vector<std::vector<short int >>& Neighbourhoods = AlgorithmMembers.Neighbourhoods;
	//Obtain NotInNeighbourhood
	bool** (&NotInNeighbourhood) = AlgorithmMembers.NotInNeighbourhood;
	//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;

	//SetReducedCostTemplate
	SetReducedCostTemplate();

	//Initialize list of double layered labeling algorithms
	std::forward_list<PStep_DoubleLayeredLabelingAlgorithm> LabelingAlgorithms;

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

	//Initialize reachability setters:
	//********************************
	//Initialize Container for PStep_ReachabilitySetter
	std::forward_list<PStep_ReachabilitySetter> ReachabilitySetters;
	//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 Container for PStep_ZeroLoadDepotFinalExtender
	std::forward_list<PStep_ZeroLoadDepotFinalExtender> ZeroLoadDepotFinalExtenders;
	//Initialize Container for PStep_ZeroLoadFinalExtender
	std::forward_list<PStep_ZeroLoadFinalExtender> ZeroLoadFinalExtenders;
	//Initialize Container for PStep_MaxLoadDepotFinalExtender
	std::forward_list<PStep_MaxLoadDepotFinalExtender> MaxLoadDepotFinalExtenders;
	//Initialize Container for PStep_MaxLoadFinalExtender
	std::forward_list<PStep_MaxLoadFinalExtender> MaxLoadFinalExtenders;

	//Initialize dominators:
	//**********************
	//Initialize Dominator
	PStep_ReachabilityOnlyDominator Dominator(Tolerance);
	//Initialize load dominator
	PStep_TrueDominator TrueDominator(Tolerance);
	//Initialize ng-path dominator
	PStep_NGReachabilityOnlyDominator NGDominator(Tolerance, Neighbourhoods);
	//Initialize pointer to the current dominator
	PStep_Dominator* CurrentDominator;
	//Check which dominator should be used
	if (DoNotCheckReachability){
		CurrentDominator = &TrueDominator;
	}
	else if (UseNGPathRelaxation){
		CurrentDominator = &NGDominator;
	}
	else{
		CurrentDominator = &Dominator;
	}
	//Initialize Container for PStep_NGReachabilityOnlyDominator, to be used
	//if dynamic state space relaxation is applied.
	std::forward_list<PStep_NGReachabilityOnlyDominator> 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];
		//Obtain demand
		double* Demand = CurrentPricingProblem.Demand;
		//Obtain capacity plus tolerance
		double CapacityPlusTolerance = CurrentPricingProblem.Capacity + Tolerance;

		//Set reduced costs
		SetReducedCosts(CurrentPricingProblem, 0, 0);

		//Check whether dynamic state-space relaxation is applied
		if (ApplyDSSR){
			//Create Reachability setter
			NGReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance, CurrentPricingProblem.CurrentDSSRNotInNeighbourhood);
			//Set current reachability setter
			CurrentReachabilitySetter = &(NGReachabilitySetters.front());
			//Create dominator
			DSSRNGReachabilityDominators.emplace_front(Tolerance, CurrentPricingProblem.CurrentDSSRNeighbourhoods);
			//Set current dominator
			CurrentDominator = &(DSSRNGReachabilityDominators.front());
		}
		else if (UseNGPathRelaxation){
			//Create Reachability setter
			NGReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance, NotInNeighbourhood);
			//Set current reachability setter
			CurrentReachabilitySetter = &(NGReachabilitySetters.front());
		}
		else{
			//Create Reachability setter
			ReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance);
			//Set current reachability setter
			CurrentReachabilitySetter = &(ReachabilitySetters.front());
		}

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

		//Create Layered Labeling Algorithm
		LabelingAlgorithms.emplace_front(CurrentPricingProblem, StandardExtenders.front(), ZeroLoadDepotFinalExtenders.front(), *CurrentDominator, UseLimitedArcs, 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);
		//Obtain current sink
		short int jMinusOne = CurrentPricingProblem.Sink - 1;
		//Obtain demand
		double* Demand = CurrentPricingProblem.Demand;
		//Obtain capacity plus tolerance
		double CapacityPlusTolerance = CurrentPricingProblem.Capacity + Tolerance;

		//Set reduced costs
		double ReducedCostConstant = Lambda[jMinusOne] + Mu[jMinusOne];
		SetReducedCosts(CurrentPricingProblem, Nu[jMinusOne], ReducedCostConstant);

		//Check which reachability setter should be used
		if (ApplyDSSR){
			//Create Reachability setter
			NGReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance, CurrentPricingProblem.CurrentDSSRNotInNeighbourhood);
			//Set current reachability setter
			CurrentReachabilitySetter = &(NGReachabilitySetters.front());
			//Create dominator
			DSSRNGReachabilityDominators.emplace_front(Tolerance, CurrentPricingProblem.CurrentDSSRNeighbourhoods);
			//Set current dominator
			CurrentDominator = &(DSSRNGReachabilityDominators.front());
		}
		else if (UseNGPathRelaxation){
			//Create NGReachabilitySetter
			NGReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance, NotInNeighbourhood);
			//Set current reachability setter
			CurrentReachabilitySetter = &(NGReachabilitySetters.front());
		}
		else{
			//Create ReachabilitySetter
			ReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance);
			//Set current reachability setter
			CurrentReachabilitySetter = &(ReachabilitySetters.front());
		}
		//Create standard extender
		StandardExtenders.emplace_front(Demand, CurrentPricingProblem.ReducedArcCosts, *CurrentReachabilitySetter);
		//Create Final extender
		ZeroLoadFinalExtenders.emplace_front(Demand, CurrentPricingProblem.ReducedArcCosts, Tolerance);

		//Create Layered Labeling Algorithm
		LabelingAlgorithms.emplace_front(CurrentPricingProblem, StandardExtenders.front(), ZeroLoadFinalExtenders.front(), *CurrentDominator, UseLimitedArcs, 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);
		//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;

		//Set reduced costs
		double ReducedCostConstant = -Lambda[iMinusOne] - Mu[iMinusOne] - Nu[iMinusOne] * Capacity;
		SetReducedCosts(CurrentPricingProblem, Nu[iMinusOne], ReducedCostConstant);

		//Check whether dynamic state-space relaxation is applied
		if (ApplyDSSR){
			//Create Reachability setter
			NGReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance, CurrentPricingProblem.CurrentDSSRNotInNeighbourhood);
			//Set current reachability setter
			CurrentReachabilitySetter = &(NGReachabilitySetters.front());
			//Create dominator
			DSSRNGReachabilityDominators.emplace_front(Tolerance, CurrentPricingProblem.CurrentDSSRNeighbourhoods);
			//Set current dominator
			CurrentDominator = &(DSSRNGReachabilityDominators.front());
		}
		else if (UseNGPathRelaxation){
			//Create NGReachabilitySetter
			NGReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance, NotInNeighbourhood);
			//Set current reachability setter
			CurrentReachabilitySetter = &(NGReachabilitySetters.front());
		}
		else{
			//Create ReachabilitySetter
			ReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance);
			//Set current reachability setter
			CurrentReachabilitySetter = &(ReachabilitySetters.front());
		}
		//Create standard extender
		StandardExtenders.emplace_front(Demand, CurrentPricingProblem.ReducedArcCosts, *CurrentReachabilitySetter);
		//Create Final extender
		MaxLoadDepotFinalExtenders.emplace_front(Demand, CurrentPricingProblem.ReducedArcCosts, Tolerance, Capacity);

		//Create Layered Labeling Algorithm
		LabelingAlgorithms.emplace_front(CurrentPricingProblem, StandardExtenders.front(), MaxLoadDepotFinalExtenders.front(), *CurrentDominator, UseLimitedArcs, 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;
		//Obtain demand
		double* Demand = (*RelevantPricingProblem)->Demand;
		//Obtain capacity
		double Capacity = (*RelevantPricingProblem)->Capacity;
		//Obtain capacity plus tolerance
		double CapacityPlusTolerance = Capacity + Tolerance;

		//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] * (Capacity + Demand[LargeNuCustomer]) + Nu[SmallNuCustomer] * (Capacity + 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;

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

			//Set reduced costs
			double ReducedCostConstant = Lambda[SmallNuCustomer] - Lambda[LargeNuCustomer] + Mu[SmallNuCustomer] - Mu[LargeNuCustomer] + (Nu[SmallNuCustomer] - Nu[LargeNuCustomer]) * Capacity;
			SetReducedCosts(CurrentPricingProblem, Nu[LargeNuCustomer], ReducedCostConstant);

			//Check which reachability setter should be used
			if (ApplyDSSR){
				//Create Reachability setter
				NGReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance, CurrentPricingProblem.CurrentDSSRNotInNeighbourhood);
				//Set current reachability setter
				CurrentReachabilitySetter = &(NGReachabilitySetters.front());
				//Create dominator
				DSSRNGReachabilityDominators.emplace_front(Tolerance, CurrentPricingProblem.CurrentDSSRNeighbourhoods);
				//Set current dominator
				CurrentDominator = &(DSSRNGReachabilityDominators.front());
			}
			else if (UseNGPathRelaxation){
				//Create NGReachabilitySetter
				NGReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance, NotInNeighbourhood);
				//Set current reachability setter
				CurrentReachabilitySetter = &(NGReachabilitySetters.front());
			}
			else{
				//Create ReachabilitySetter
				ReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance);
				//Set current reachability setter
				CurrentReachabilitySetter = &(ReachabilitySetters.front());
			}
			//Create standard extender
			StandardExtenders.emplace_front(Demand, CurrentPricingProblem.ReducedArcCosts, *CurrentReachabilitySetter);
			//Create Final extender
			MaxLoadFinalExtenders.emplace_front(Demand, CurrentPricingProblem.ReducedArcCosts, Tolerance, Capacity);

			//Create Layered Labeling Algorithm
			LabelingAlgorithms.emplace_front(CurrentPricingProblem, StandardExtenders.front(), MaxLoadFinalExtenders.front(), *CurrentDominator, UseLimitedArcs, 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;

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

			//Set reduced costs
			double ReducedCostConstant = Lambda[LargeNuCustomer] - Lambda[SmallNuCustomer] + Mu[LargeNuCustomer] - Mu[SmallNuCustomer] + (Nu[LargeNuCustomer] - Nu[SmallNuCustomer])*Demand[SmallNuCustomer];
			SetReducedCosts(CurrentPricingProblem, Nu[LargeNuCustomer], ReducedCostConstant);

			//Check which reachability setter should be used
			if (ApplyDSSR){
				//Create Reachability setter
				NGReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance, CurrentPricingProblem.CurrentDSSRNotInNeighbourhood);
				//Set current reachability setter
				CurrentReachabilitySetter = &(NGReachabilitySetters.front());
				//Create dominator
				DSSRNGReachabilityDominators.emplace_front(Tolerance, CurrentPricingProblem.CurrentDSSRNeighbourhoods);
				//Set current dominator
				CurrentDominator = &(DSSRNGReachabilityDominators.front());
			}
			else if (UseNGPathRelaxation){
				//Create NGReachabilitySetter
				NGReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance, NotInNeighbourhood);
				//Set current reachability setter
				CurrentReachabilitySetter = &(NGReachabilitySetters.front());
			}
			else{
				//Create ReachabilitySetter
				ReachabilitySetters.emplace_front(Demand, CapacityPlusTolerance);
				//Set current reachability setter
				CurrentReachabilitySetter = &(ReachabilitySetters.front());
			}
			//Create standard extender
			StandardExtenders.emplace_front(Demand, CurrentPricingProblem.ReducedArcCosts, *CurrentReachabilitySetter);
			//Create Final extender
			ZeroLoadFinalExtenders.emplace_front(Demand, CurrentPricingProblem.ReducedArcCosts, Tolerance);

			//Create Layered Labeling Algorithm
			LabelingAlgorithms.emplace_front(CurrentPricingProblem, StandardExtenders.front(), ZeroLoadFinalExtenders.front(), *CurrentDominator, UseLimitedArcs, 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.AddMultiplePPCandidateLabels(SolvedPricingProblems);

}