/*Implementation of PStep_SeparationAlgorithm.h

It contains the member functions of PStep_SeparationAlgorithm4

*/

#include "PStep_SeparationAlgorithm.h"

//PStep_SeparationAlgorithm4:
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Separate
//------------------------------------------------------------------------------------

//Separate capacity cuts using the algorithm of Lysgaard.
//These cuts are stored in AlgorithmMembers.CapacityCuts, new cuts are appended to the list.
//If it fails, separate framed capacity cuts using the algorithm of Lysgaard.
//These cuts are stored in AlgorithmMembers.FramedCapacityCuts, new cuts are appended to the list.
//If that fails, separate strengthened comb cuts using the algorithm of Lysgaard.
//These cuts are stored in AlgorithmMembers.StrengthenedCombCuts, new cuts are appended to the list.
//If that also fails, separate 2 edge hypotour cuts using the algorithm of Lysgaard.
//These cuts are stored in AlgorithmMembers.TwoEdgeHypotourCuts, new cuts are appended to the list.
void PStep_SeparationAlgorithm4::Separate(){

	//Prepare the selected edges
	SetCurrentEdges();

	//Check whether there are any positively selected edges
	if (NumberOfEdgesPlusOne > 1){

		//Obtain current number of capacity cuts
		int NumberOfCCBeforeSeparation = AlgorithmMembers.NumberOfCapacityCuts;

		//Separate capacity cuts
		SeparateCCLysgaard();

		//Check whether new capacity cuts were added
		if (NumberOfCCBeforeSeparation == AlgorithmMembers.NumberOfCapacityCuts){

			//Obtain current number of framed capacity cuts
			int NumberOfFCCBeforeSeparation = AlgorithmMembers.NumberOfFramedCapacityCuts;

			//Separate framed capacity cuts
			SeparateFCCLysgaard();

			//Check whether new capacity cuts were added
			if (NumberOfFCCBeforeSeparation == AlgorithmMembers.NumberOfFramedCapacityCuts){
				//No violated capacity cuts were identified, separate strengthened comb cuts

				//Obtain current number of strentghened comb cuts
				int NumberOfSCombBeforeSeparation = AlgorithmMembers.NumberOfSCombCuts;

				//Separate strengthened comb cuts
				SeparateSCombLysgaard();

				//Check whether new strengthened comb cuts were added
				if (NumberOfSCombBeforeSeparation == AlgorithmMembers.NumberOfSCombCuts){
					//No violated strengthened comb cuts were identified, separate 2 edge hypotour cuts

					//Separate 2 edge hypotour cuts
					Separate2EHLysgaard();

				}

			}

		}

	}

}

//Framed Capacity Cut separation functions:
//------------------------------------------------------------------------------------

//Separate framed capacity cuts using the algorithm of Lysgaard.
//These cuts are stored in AlgorithmMembers.FramedCapacityCuts, new cuts are appended to the list.
void PStep_SeparationAlgorithm4::SeparateFCCLysgaard(){

	//Obtain start time of the separation algorithm
	timePoint tic = HomeMadeclock::now();

	//Initialize
	//-------------------------------------------------

	//Initialize support variables
	short int NumberOfCustomers = AlgorithmMembers.Instance.NumberOfCustomers;
	short int NumberOfLocations = NumberOfCustomers + 1;
	double Tolerance = AlgorithmMembers.Tolerance;
	std::vector < std::vector < PStep_Arc >> &Arcs = AlgorithmMembers.Arcs;
	double MinimumViolation = AlgorithmMembers.AlgorithmSettings.MinimumFCCViolation;

	//Obtain the maximum number of nodes explored by the separation algorithm
	int MaxNoTreeNodes = AlgorithmMembers.AlgorithmSettings.MaxFCCNoTreeNodes;
	//Obtain the maximum number of framed capacity cuts added per iteration
	int MaxCuts = AlgorithmMembers.AlgorithmSettings.MaxSCombPerIteration;

	//Initalize double
	double MaxViolation;
	//Initialize CnstrMgrPointer to contain the generated cuts
	CnstrMgrPointer MyCutsCMP;
	CMGR_CreateCMgr(&MyCutsCMP, MaxCuts);

	//Use Lysgaard's algorithm:
	//-------------------------------------------------
	FCISEP_SeparateFCIs(NumberOfCustomers, LysgaardDemand, int(AlgorithmMembers.Instance.VehicleCapacity), NumberOfEdgesPlusOne - 1, EdgeTail, EdgeHead, EdgeX, AlgorithmMembers.LysgaardCuts, MaxNoTreeNodes, MaxCuts, &MaxViolation, MyCutsCMP);

	//Process new cuts
	//-------------------------------------------------

	//Initialize indicators, indicating whether a location is not in the frame
	bool* LocationNotInFrame = new bool[NumberOfLocations];

	//Go over all new cuts
	for (int i = 0; i<MyCutsCMP->Size; i++){

		//Reinitialize LocationNotInFrame
		for (short int j = 0; j < NumberOfLocations; ++j){
			LocationNotInFrame[j] = true;
		}

		//Initialize framed capacity cut
		AlgorithmMembers.FramedCapacityCuts.emplace_back();
		//Obtain new cut
		PStep_EdgeFlowCut &NewFramedCapacityCut = AlgorithmMembers.FramedCapacityCuts.back();
		//Update counter
		++AlgorithmMembers.NumberOfFramedCapacityCuts;

		//Initialize list of lists providing the partition of the frame
		//Partition[i][j] is the j'th location in the i'th partition, Partition[i][j]=0 is the depot.
		std::list < std::list<short int>> Partition;

		//Go over all partitions
		short int MinIdx;
		short int MaxIdx = 0;
		for (int SubsetNr = 1; SubsetNr <= MyCutsCMP->CPL[i]->ExtListSize; SubsetNr++){
			
			//Initialize partition
			Partition.emplace_back();
			//Obtain current partition
			std::list<short int> &CurrentPartition = Partition.back();

			//Go over all locations in the partition
			MinIdx = MaxIdx + 1;
			MaxIdx = MinIdx + MyCutsCMP->CPL[i]->ExtList[SubsetNr] - 1;
			for (short int j = MinIdx; j <= MaxIdx; j++){
				//Obtain current location
				short int k = MyCutsCMP->CPL[i]->IntList[j];
				if (k == NumberOfLocations){
					//Recode the depot
					k = 0;
				}
				//Add location to the partition and frame
				CurrentPartition.push_back(k);
				LocationNotInFrame[k] = false;
			}
		}

		//Create list of locations that are not in the frame
		std::list<short int> NotInFrame;
		//Go over all locations
		for (short int j = 0; j < NumberOfLocations; ++j){
			//Check whether the current location is not in the frame
			if (LocationNotInFrame[j]){
				//Add the location to the NotInFrame list
				NotInFrame.push_back(j);
			}
		}

		//Go over all partitions and build the cut
		for (auto CurrentPartition = Partition.begin(); CurrentPartition != Partition.end(); ++CurrentPartition){

			//Add edges that go out of the frame:
			//Go over all locations in the partition
			for (auto k = CurrentPartition->begin(); k != CurrentPartition->end(); ++k){
				//Go over all locations not in the frame
				for (auto j = NotInFrame.begin(); j != NotInFrame.end(); ++j){
					//Add the edge
					NewFramedCapacityCut.Indices.emplace_back(Arcs[*k][*j].Index);
				}
			}

			//Add edges that do not go out of the frame
			//Obtain next partition
			auto NextPartition = CurrentPartition;
			++NextPartition;
			//Go over all other partitions
			for (auto OtherPartition = NextPartition; OtherPartition != Partition.end(); ++OtherPartition){
				//Add edges:
				//Go over all locations in the current partition
				for (auto k = CurrentPartition->begin(); k != CurrentPartition->end(); ++k){
					//Go over all locations in the other partition
					for (auto j = OtherPartition->begin(); j != OtherPartition->end(); ++j){
						//Add the edge
						NewFramedCapacityCut.Indices.emplace_back(Arcs[*k][*j].Index);
					}
				}
			}

		}//end go over all partitions and build the cut

		//Add bound to the strengthened comb cut
		NewFramedCapacityCut.Bound = (MyCutsCMP->CPL[i]->RHS)/2;

		//Check whether the violation of the cut is large enough
		if (ComputeViolation(NewFramedCapacityCut, false) >= MinimumViolation){
			//The violation is large enough, so add the cut:
			
			//Move the current cut to LysgaardCuts
			CMGR_MoveCnstr(MyCutsCMP, AlgorithmMembers.LysgaardCuts, i, 0);
		}
		else{
			//Remove cut again
			AlgorithmMembers.FramedCapacityCuts.pop_back();
			--AlgorithmMembers.NumberOfFramedCapacityCuts;
		}

	}

	//clean
	delete[]LocationNotInFrame;
	CMGR_FreeMemCMgr(&MyCutsCMP);

	//Terminate:
	//-------------------------------------------------
	//Obtain end time of the separation algorithm
	timePoint toc = HomeMadeclock::now();
	//Update framed capacity cut separation time
	AlgorithmMembers.CurrentCGStatistics.TotalSeparateFCCTime += HomeMadeclock::seconds(tic, toc);

}