/*Implementation of PStep_SeparationAlgorithm.h

It contains the member functions of PStep_SeparationAlgorithm2

*/

#include "PStep_SeparationAlgorithm.h"

//PStep_SeparationAlgorithm2:
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//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 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_SeparationAlgorithm2::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){
			//No violated capacity cuts were identified, separate 2 edge hypotour cuts

			//Separate 2 edge hypotour cuts
			Separate2EHLysgaard();

		}

	}

}

//2 edge hypotour separation functions:
//------------------------------------------------------------------------------------

//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_SeparationAlgorithm2::Separate2EHLysgaard(){

	//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.Minimum2EHViolation;

	//Obtain the maximum number of 2 edge hypotour cuts added per iteration
	int MaxCuts = AlgorithmMembers.AlgorithmSettings.Max2EHPerIteration;

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

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

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

		//Initialize 2 edge hypotour cut
		AlgorithmMembers.TwoEdgeHypotourCuts.emplace_back();
		//Obtain new cut
		PStep_EdgeAndCoefficientCut &New2EHCut = AlgorithmMembers.TwoEdgeHypotourCuts.back();
		//Update counter
		++AlgorithmMembers.NumberOf2EHCuts;
		
		//Add edges and coefficients to the cut
		for (int j = 1; j <= MyCutsCMP->CPL[i]->IntListSize; j++){
			
			//Add new edge to the list
			New2EHCut.EdgeAndCoefficients.emplace_back();
			//Obtain locations of the arc
			short int Tail = MyCutsCMP->CPL[i]->IntList[j];
			short int Head = MyCutsCMP->CPL[i]->ExtList[j];
			
			//Check whether the head is the depot
			if (Head == NumberOfLocations){
				//Lysgaard codes the depot as NumberOfLocations, we code it as 0.

				//Set edge index
				New2EHCut.EdgeAndCoefficients.back().EdgeIndex = Arcs[0][Tail].Index;
			}
			else{
				//Set edge index
				New2EHCut.EdgeAndCoefficients.back().EdgeIndex = Arcs[Tail][Head].Index;
			}

			//Set coefficient
			New2EHCut.EdgeAndCoefficients.back().Coefficient = MyCutsCMP->CPL[i]->CoeffList[j];

		}

		//Add bound to the 2 edge hypotour cut
		New2EHCut.Bound = MyCutsCMP->CPL[i]->RHS;

		//Check whether the violation of the cut is large enough
		if (ComputeViolation(New2EHCut, true) >= 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.TwoEdgeHypotourCuts.pop_back();
			--AlgorithmMembers.NumberOf2EHCuts;
		}

	}

	//clean
	CMGR_FreeMemCMgr(&MyCutsCMP);

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

}