/*Implementation of PStep_ColumnManager.h

It contains the member functions of PStep_ColumnManager2

*/

#include "PStep_ColumnManager.h"

//PStep_ColumnManager2:
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Remove functions
//------------------------------------------------------------------------------------

//Remove p-steps included in x from the formulation in PStepLP.
//All columns with reduced costs higher than Threshold are removed, as long as there are more than NumberOfColumnsLimit columns.
//Only CurrentPSteps are considered from (and including) FirstCurrentPStep up to (and excluding) LastCurrentPStep.
//ReducedCosts[CurrentPStepsxIndex[i]] should correspond to CurrentPSteps[i] and x[CurrentPSteps[i]].
void PStep_ColumnManager2::Remove(std::list<std::list<PStep>::iterator>::iterator FirstCurrentPStep, std::list<std::list<PStep>::iterator>::iterator LastCurrentPStep, IloNumVarArray& x, IloNumArray& ReducedCosts, IloEnv& env){

	//Obtain CurrentPSteps, -xIndices, the ShortList and their counters.
	std::list<std::list<PStep>::iterator>& CurrentPSteps = AlgorithmMembers.CurrentPSteps;
	std::list<int>& CurrentPStepsxIndices = AlgorithmMembers.CurrentPStepsxIndices;
	int& NumberOfCurrentPSteps = AlgorithmMembers.NumberOfCurrentPSteps;
	std::list<std::list<PStep>::iterator>& PStepShortList = AlgorithmMembers.PStepShortList;
	int& NumberOfPStepsInShortList = AlgorithmMembers.NumberOfPStepsInShortList;

	//Initialize index
	auto CurrentPStepxIndex = CurrentPStepsxIndices.begin();
	int Counter = 0;
	//Initialize array of x variables to delete
	IloNumVarArray Deletex(env);
	//Initialize the current p-step
	auto CurrentPStep = FirstCurrentPStep;
	//Go over all current p-steps
	while (CurrentPStep != LastCurrentPStep && NumberOfCurrentPSteps > NumberOfColumnsLimit){

		//Check whether the current p-step has reduced costs higher than the threshold
		if (ReducedCosts[Counter]>Threshold){
			//Remove the current p-step from the formulation and place it on the shortlist:

			//Place the current p-step on the shortlist
			PStepShortList.push_back(*CurrentPStep);
			++NumberOfPStepsInShortList;

			//Mark the p-step variable for removal from the formulation
			Deletex.add(x[*CurrentPStepxIndex]);

			//Remove the current p-step and x index from the lists.
			CurrentPStep = CurrentPSteps.erase(CurrentPStep);
			CurrentPStepxIndex = CurrentPStepsxIndices.erase(CurrentPStepxIndex);
			--NumberOfCurrentPSteps;

		}
		else{
			//The current p-step is not removed, update p-step and index
			++CurrentPStep;
			++CurrentPStepxIndex;
		}

		//Update counter
		++Counter;

	}

	//Remove all marked p-step variables from the formulation
	Deletex.endElements();

}

//Search Shortlist functions
//------------------------------------------------------------------------------------

//Search the shortlist for p-steps with negative reduced costs.
//All p-steps with negative reduced costs are added.
//It outputs true if negative reduced cost p-steps have been identified,
//NOTE: The column generator is not really needed, but that is where currently the duals are stored.
//		At the time of coding this I did not feel like reorganizing.
bool PStep_ColumnManager2::SearchShortList(PStep_ColumnGenerator& CurrentColumnGenerator){

	//Obtain Tolerance
	double MinusTolerance = -AlgorithmMembers.Tolerance;
	//Obtain CurrentPSteps, -xIndices, the ShortList and their counters.
	std::list<std::list<PStep>::iterator>& CurrentPSteps = AlgorithmMembers.CurrentPSteps;
	std::list<int>& CurrentPStepsxIndices = AlgorithmMembers.CurrentPStepsxIndices;
	int& NumberOfCurrentPSteps = AlgorithmMembers.NumberOfCurrentPSteps;
	std::list<std::list<PStep>::iterator>& PStepShortList = AlgorithmMembers.PStepShortList;
	int& NumberOfPStepsInShortList = AlgorithmMembers.NumberOfPStepsInShortList;
	//Obtain duals
	Lambda = CurrentColumnGenerator.Lambda;
	Mu = CurrentColumnGenerator.Mu;
	Nu = CurrentColumnGenerator.Nu;
	Pi = CurrentColumnGenerator.Pi;

	//Initialize output
	bool NegativeReducedCostPStepFound = false;
	//Store the number of CurrentPSteps
	int NumberOfCurrentPStepsBeforeTheSearch = NumberOfCurrentPSteps;

	//Initialize the first p-step in the short list shortlist
	auto CurrentPStep = PStepShortList.begin();
	//Go over all p-steps in the shortlist
	while (CurrentPStep != PStepShortList.end()){
		//Check whether the current p-step has negative reduced costs
		if (ComputeReducedCosts(**CurrentPStep) < MinusTolerance){
			//The current p-step has negative reduced costs.

			//Place the current p-step on the list CurrentPSteps
			CurrentPSteps.push_back(*CurrentPStep);
			++NumberOfCurrentPSteps;

			//Remove the current p-step from the shortlist.
			CurrentPStep = PStepShortList.erase(CurrentPStep);
			--NumberOfPStepsInShortList;
			
		}
		else{
			//The current p-step does not have negative reduced costs

			//Update the current p-step
			++CurrentPStep;
		}
	}
	
	//Check whether p-steps with negative reduced costs were identified.
	if (NumberOfCurrentPStepsBeforeTheSearch < NumberOfCurrentPSteps){
		//p-steps with negative reduced costs were identified.
		NegativeReducedCostPStepFound = true;
	}

	//Output
	return NegativeReducedCostPStepFound;

}

//Compute the reduced costs of a p-step.
double PStep_ColumnManager2::ComputeReducedCosts(PStep& CurrentPStep){

	//Obtain Arcs
	std::vector<std::vector<PStep_Arc>>& Arcs = AlgorithmMembers.Arcs;

	//Initialize reduced costs
	double ReducedCosts = CurrentPStep.Cost;

	//Obtain start, next and end location
	auto CurrentLocation=CurrentPStep.Locations.begin();
	short int CurrentIndex = *CurrentLocation;
	short int CurrentIndexMinusOne = CurrentIndex - 1;
	auto NextLocation = CurrentLocation;
	++NextLocation;
	auto EndLocation = CurrentPStep.Locations.end();
	//Check whether the current location is the depot
	if (CurrentIndex != 0){
		//Add the reduced costs corresponding to lambda, mu and nu for the starting location.
		ReducedCosts -= Lambda[CurrentIndexMinusOne];
		ReducedCosts -= Mu[CurrentIndexMinusOne];
		ReducedCosts -= Nu[CurrentIndexMinusOne] * CurrentPStep.StartingLoad;
	}
	//Go over all locations and add the reduced costs corresponding to lambda and pi.
	for (; NextLocation != EndLocation; ++NextLocation){
		//Update the next location index
		short int NextIndex = *NextLocation;
		//Update reduced costs by subtracting Pi
		ReducedCosts -= Pi[Arcs[CurrentIndex][NextIndex].Index];
		//Check whether the next location is not the depot
		if (NextIndex != 0){
			//Update the reduced costs by subtracting lambda
			ReducedCosts -= 2 * Lambda[NextIndex - 1];
		}
		//Update current index
		CurrentIndex = NextIndex;
	}
	//Check whether the last location is the depot
	if (CurrentIndex != 0){
		//Compute support
		CurrentIndexMinusOne = CurrentIndex - 1;
		//Add the reduced costs corresponding to lambda, mu and nu for the ending location.
		ReducedCosts += Lambda[CurrentIndexMinusOne];
		ReducedCosts += Mu[CurrentIndexMinusOne];
		ReducedCosts += Nu[CurrentIndexMinusOne] * CurrentPStep.TotalLoad;
	}

	//Output
	return ReducedCosts;

}