/*Implementation of PStep_ColumnGenerator.h

It contains the member functions of PStep_ColumnGenerator2

*/

#include "PStep_ColumnGenerator.h"

//PStep_ColumnGenerator2:
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Constructor functions:
//------------------------------------------------------------------------------------

//Basic constructor
//Initializes the arrays of the duals to the appropriate sizes
//Preprocessing for the local search.
PStep_ColumnGenerator2::PStep_ColumnGenerator2(PStep_AlgorithmMembers& InitAlgorithmMembers, PStep_Adder& InitAdder, PStep_PricingProblemSolver& InitSolver)
	:PStep_ColumnGenerator1(InitAlgorithmMembers, InitAdder, InitSolver)
{
	
	//Obtain number of customers and locations
	short int NumberOfCustomers = AlgorithmMembers.Instance.NumberOfCustomers;
	//Obtain Demand
	double* Demand = AlgorithmMembers.Instance.Demand;

	//Compute demand increases:
	//****************************************************************************

	//Initialize DemandIncrease 
	DemandIncrease = new double*[NumberOfCustomers];
	//Go over all customers to remove from a p-step
	for (short int i = 0; i < NumberOfCustomers; ++i){
		//Initialize DemandIncrease[i]
		DemandIncrease[i] = new double[NumberOfCustomers];
		//Go over all customers to add to a p-step
		for (short int j = 0; j < NumberOfCustomers; ++j){
			DemandIncrease[i][j] = Demand[i]-Demand[j];
		}
	}

}

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

//Solve pricing problem seperately for every(non - redundant) start and end node combination.
//The pricing problems are solved heuristically using local search. If no negative reduced
//cost p-step is found, the exact solver ColumnGenerator1 is used.
void PStep_ColumnGenerator2::GenerateColumns(){

	//Obtain the number of p-steps currently added
	int NumberOfCurrentPStepsBefore = AlgorithmMembers.NumberOfCurrentPSteps;

	//Apply column generator2
	GenerateColumns2();

	//Check if p-steps are added
	if (AlgorithmMembers.NumberOfCurrentPSteps == NumberOfCurrentPStepsBefore){
		//The heuristic did not identify negative reduced cost p-steps,
		//use column generator 1
		GenerateColumns1();
	}
	
}

//Solve pricing problem seperately for every(non - redundant) start and end node combination.
//The pricing problems are solved heuristically using local search.
void PStep_ColumnGenerator2::GenerateColumns2(){

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

	//Obtain p
	short int p = AlgorithmMembers.AlgorithmSettings.p;
	//Obtain number of customers
	short int NumberOfCustomers = AlgorithmMembers.Instance.NumberOfCustomers;
	//Obtain number of locations
	short int NumberOfLocations = NumberOfCustomers + 1;
	//Obtain demand
	double* Demand = AlgorithmMembers.Instance.Demand;
	//Obtain TravelCosts
	double** TravelCosts = AlgorithmMembers.Instance.TravelCosts;
	//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;

	//SetReducedCostTemplate
	SetReducedCostTemplate();

	//Initialize list of Local Search algorithms with a fixed number of arcs
	std::forward_list<PStep_LocalSearchFixedArcs> LocalSearchesFixedArcs;
	//Initialize list of Local Search algorithms with a varying number of arcs
	std::forward_list<PStep_LocalSearchVaryingArcs> LocalSearchesVaryingArcs;

	//Initialize list of solved pricing problems
	//This list gets updated after a succesful run of PStep_LocalSearchFixedArcs or PStep_LocalSearchVaryingArcs
	std::forward_list<PStep_PricingProblem*> SolvedPricingProblems;
	
	//Create pricing problems:
	//*****************************************************************************************
	
	//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){
		//Set reduced costs
		SetReducedCosts(PricingProblems[0][0], 0, 0);
		//Reset output
		PricingProblems[0][0].CandidatePSteps.clear();
		//Create Local Search Algorithm
		LocalSearchesVaryingArcs.emplace_front(PricingProblems[0][0], DemandIncrease, TravelCosts, Tolerance, 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;
		
		//Set reduced costs
		double ReducedCostConstant = Lambda[jMinusOne] + Mu[jMinusOne];
		SetReducedCosts(CurrentPricingProblem, Nu[jMinusOne], ReducedCostConstant);

		//Reset output
		CurrentPricingProblem.CandidatePSteps.clear();

		//Create Local Search Algorithm
		LocalSearchesVaryingArcs.emplace_front(CurrentPricingProblem, DemandIncrease, TravelCosts, Tolerance, 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 capacity
		double Capacity = CurrentPricingProblem.Capacity;

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

		//Reset output
		CurrentPricingProblem.CandidatePSteps.clear();

		//Create Local Search Algorithm
		LocalSearchesFixedArcs.emplace_front(CurrentPricingProblem, DemandIncrease, TravelCosts, false, Tolerance, 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);

			//Reset output
			CurrentPricingProblem.CandidatePSteps.clear();

			//Create Local Search Algorithm
			LocalSearchesFixedArcs.emplace_front(CurrentPricingProblem, DemandIncrease, TravelCosts, false, Tolerance, 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);
			
			//Reset output
			CurrentPricingProblem.CandidatePSteps.clear();

			//Create Local Search Algorithm
			LocalSearchesFixedArcs.emplace_front(CurrentPricingProblem, DemandIncrease, TravelCosts, true, Tolerance, SolvedPricingProblems);

		}

	}//end go over all customers j

	//Create pricing problems for each p-step in the current solution:
	//****************************************************************
	
	//Go over all p-steps in the current solution
	for (auto CurrentPStep = AlgorithmMembers.CurrentSolution.PSteps.begin(); CurrentPStep != AlgorithmMembers.CurrentSolution.PSteps.end(); ++CurrentPStep){

		//Obtain Source and Sink
		short int Source = CurrentPStep->Locations.front();
		short int Sink = CurrentPStep->Locations.back();

		//Determine the type of pricing problem:
		//Check if the source is the depot
		if (Source == 0){
			//Check if the sink is the depot
			if (Sink == 0){
				//Obtain current pricing problem
				PStep_PricingProblem &CurrentPricingProblem = PricingProblems[0][0];
				//Set reduced costs
				SetReducedCosts(CurrentPricingProblem, 0, 0);
				//Reset output
				CurrentPricingProblem.CandidatePSteps.clear();
				//Create Local Search Algorithm
				LocalSearchesVaryingArcs.emplace_front(CurrentPricingProblem, DemandIncrease, TravelCosts, Tolerance, SolvedPricingProblems);
				//Initialize the p-step in the pricing problem
				LocalSearchesVaryingArcs.front().CurrentPStep = *CurrentPStep;
				LocalSearchesVaryingArcs.front().CurrentReducedCosts = 0;
				LocalSearchesVaryingArcs.front().CurrentDemand = CurrentPStep->TotalLoad - CurrentPStep->StartingLoad;
				LocalSearchesVaryingArcs.front().InitialPStepProvided = true;
				if (!LocalSearchesVaryingArcs.front().RemoveDoublesCurrentPStep()){
					//The current p-step could not be transformed into an elementary p-step
					LocalSearchesVaryingArcs.pop_front();
				}
			}
			//The sink is not the depot
			else{
				//Obtain current pricing problem
				PStep_PricingProblem &CurrentPricingProblem = PricingProblems[0][Sink];
				//Initialize support variable
				short int jMinusOne = Sink - 1;
				//Set reduced costs
				double ReducedCostConstant = Lambda[jMinusOne] + Mu[jMinusOne];
				SetReducedCosts(CurrentPricingProblem, Nu[jMinusOne], ReducedCostConstant);
				//Reset output
				CurrentPricingProblem.CandidatePSteps.clear();
				//Create Local Search Algorithm
				LocalSearchesVaryingArcs.emplace_front(CurrentPricingProblem, DemandIncrease, TravelCosts, Tolerance, SolvedPricingProblems);
				//Update current reduced costs, to account for any shift in starting load
				double CurrentReducedCosts = -(Nu[jMinusOne])*(CurrentPStep->StartingLoad);
				//Initialize the p-step in the pricing problem
				LocalSearchesVaryingArcs.front().CurrentPStep = *CurrentPStep;
				LocalSearchesVaryingArcs.front().CurrentReducedCosts = CurrentReducedCosts;
				LocalSearchesVaryingArcs.front().CurrentDemand = CurrentPStep->TotalLoad - CurrentPStep->StartingLoad;
				LocalSearchesVaryingArcs.front().InitialPStepProvided = true;
				if (!LocalSearchesVaryingArcs.front().RemoveDoublesCurrentPStep()){
					//The current p-step could not be transformed into an elementary p-step
					LocalSearchesVaryingArcs.pop_front();
				}
			}
		}
		//The source is a customer
		else{
			//Check if the sink is the depot
			if (Sink == 0){
				//Obtain current pricing problem
				PStep_PricingProblem &CurrentPricingProblem = PricingProblems[Source][0];
				//Initialize support variable
				short int iMinusOne = Source - 1;
				//Obtain capacity
				double Capacity = CurrentPricingProblem.Capacity;
				//Set reduced costs
				double ReducedCostConstant = -Lambda[iMinusOne] - Mu[iMinusOne] - Nu[iMinusOne] * Capacity;
				SetReducedCosts(CurrentPricingProblem, Nu[iMinusOne], ReducedCostConstant);
				//Reset output
				CurrentPricingProblem.CandidatePSteps.clear();
				//Create Local Search Algorithm
				LocalSearchesFixedArcs.emplace_front(CurrentPricingProblem, DemandIncrease, TravelCosts, false, Tolerance, SolvedPricingProblems);
				//Update current reduced costs, to account for any shift in starting load
				double CurrentReducedCosts = (Nu[iMinusOne])*(Capacity - CurrentPStep->TotalLoad);
				//Initialize the p-step in the pricing problem
				LocalSearchesFixedArcs.front().CurrentPStep = *CurrentPStep;
				LocalSearchesFixedArcs.front().CurrentReducedCosts = CurrentReducedCosts;
				LocalSearchesFixedArcs.front().CurrentDemand = CurrentPStep->TotalLoad - CurrentPStep->StartingLoad + Demand[Source - 1];
				LocalSearchesFixedArcs.front().InitialPStepProvided = true;
				if (!(LocalSearchesFixedArcs.front().SwapDoublesCurrentPStep())){
					//The current p-step could not be transformed into an elementary p-step
					LocalSearchesFixedArcs.pop_front();
				}
			}
			//The sink is a customer
			else{
				//Obtain current pricing problem
				PStep_PricingProblem &CurrentPricingProblem = PricingProblems[Source][Sink];
				//Initialize support variable
				short int SourceMinusOne = Source - 1;
				short int SinkMinusOne = Sink - 1;
				//Initialize reduced costs
				double ReducedCostConstant;
				//Reset output
				CurrentPricingProblem.CandidatePSteps.clear();
				//Initialize indicator indicating whether minimal starting load should be used.
				bool UseMinimalStartingLoad;
				//Initialize reduced costs of the current p-step, when changing to minimal or maximal starting load
				double CurrentReducedCosts = 0;
				//Check whether it is better to have minimal or maximal starting load
				if (Nu[SourceMinusOne]<Nu[SinkMinusOne]){
					//Use minimal starting load
					UseMinimalStartingLoad = true;
					//Update current reduced costs
					CurrentReducedCosts += (Nu[SourceMinusOne] - Nu[SinkMinusOne])*(CurrentPStep->StartingLoad - Demand[SourceMinusOne]);
					//Set reduced costs
					double ReducedCostConstant = Lambda[SinkMinusOne] - Lambda[SourceMinusOne] + Mu[SinkMinusOne] - Mu[SourceMinusOne] + (Nu[SinkMinusOne] - Nu[SourceMinusOne])*Demand[SourceMinusOne];
					SetReducedCosts(CurrentPricingProblem, Nu[SinkMinusOne], ReducedCostConstant);
				}
				else{
					//Use maximal starting load
					UseMinimalStartingLoad = false;
					//Update current reduced costs
					CurrentReducedCosts += (Nu[SourceMinusOne] - Nu[SinkMinusOne])*(CurrentPricingProblem.Capacity - CurrentPStep->TotalLoad);
					//Set reduced costs
					ReducedCostConstant = Lambda[SinkMinusOne] - Lambda[SourceMinusOne] + Mu[SinkMinusOne] - Mu[SourceMinusOne] + (Nu[SinkMinusOne] - Nu[SourceMinusOne]) * CurrentPricingProblem.Capacity;
					SetReducedCosts(CurrentPricingProblem, Nu[SourceMinusOne], ReducedCostConstant);
				}
				//Create Local Search Algorithm
				LocalSearchesFixedArcs.emplace_front(CurrentPricingProblem, DemandIncrease, TravelCosts, UseMinimalStartingLoad, Tolerance, SolvedPricingProblems);				
				//Initialize the p-step in the pricing problem
				LocalSearchesFixedArcs.front().CurrentPStep = *CurrentPStep;
				LocalSearchesFixedArcs.front().CurrentReducedCosts = CurrentReducedCosts;
				LocalSearchesFixedArcs.front().CurrentDemand = CurrentPStep->TotalLoad - CurrentPStep->StartingLoad + Demand[SourceMinusOne];
				LocalSearchesFixedArcs.front().InitialPStepProvided = true;
				if (!(LocalSearchesFixedArcs.front().SwapDoublesCurrentPStep())){
					//The current p-step could not be transformed into an elementary p-step
					LocalSearchesFixedArcs.pop_front();
				}
			}
		}

	}

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

	//Make a list of pointers to the pricing problems which refer to the Layered PricingProblems
	std::forward_list<PStep_ShortestPathAlgorithm*> TempList;
	//Add all FixedPricingProblems
	for (auto CurrentAlgorithm = LocalSearchesFixedArcs.begin(); CurrentAlgorithm != LocalSearchesFixedArcs.end(); ++CurrentAlgorithm){
		TempList.push_front(&(*CurrentAlgorithm));
	}
	//Add all VaryingPricingProblems
	for (auto CurrentAlgorithm = LocalSearchesVaryingArcs.begin(); CurrentAlgorithm != LocalSearchesVaryingArcs.end(); ++CurrentAlgorithm){
		TempList.push_front(&(*CurrentAlgorithm));
	}

	
	//Solve
	Solver.Solve(TempList);

	//Add p-steps:
	//*****************************************************************************************
	
	//Add
	Adder.AddMultiplePPCandidatePSteps(SolvedPricingProblems);

}

//Destructor functions
//------------------------------------------------------------------------------------

//Default destructor
PStep_ColumnGenerator2::~PStep_ColumnGenerator2(){

	//Obtain the number of customers
	short int NumberOfCustomers = AlgorithmMembers.Instance.NumberOfCustomers;

	//Delete DemandIncrease
	if (!(NumberOfCustomers == 0 || DemandIncrease == 0)){
		for (short int i = 0; i < NumberOfCustomers; ++i){
			delete[]DemandIncrease[i];
		}
		delete[]DemandIncrease;
	}
	else{
		DemandIncrease = 0;
	}

}