/*Header file of the PStep_SeparationAlgorithm class

This file also includes derived classes of PStep_SeparationAlgorithm.

Implementation of PStep_SeparationAlgorithmX can be found in PStep_SeparationAlgorithm.cpp.

This class represents a separation algorithm.

*/

#ifndef _PSTEP_PSTEPSEPARATIONALGORITHM_H
#define _PSTEP_PSTEPSEPARATIONALGORITHM_H

#include "PStep_AlgorithmMembers.h"

//Class used to represent a separation algorithm.
class PStep_SeparationAlgorithm{
public:

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

	//Separate
	virtual void Separate() = 0;

};

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Separator 0:
//Do not separate any inequalities.
class PStep_SeparationAlgorithm0 : public PStep_SeparationAlgorithm{
public:

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

	//Separate
	void Separate(){};

};

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Separator 1:
//Separate capacity cuts.
class PStep_SeparationAlgorithm1 : public PStep_SeparationAlgorithm{
public:

	//Algorithm members
	PStep_AlgorithmMembers& AlgorithmMembers;

	//Demand as required by Lysgaard
	//Lysgaard requires a 0 as first entry, and Demand[i] to correspond to customer i.
	//Also demand is required to be integer.
	int* LysgaardDemand;

	//Separation members:
	//------------------------------------------------------------------------------------
	//The current number of selected edges, plus one
	//Lysgaard requires a bogus first edge in the array.
	int NumberOfEdgesPlusOne;
	//Initialize arrays with edge information.
	int *EdgeTail;
	int *EdgeHead;
	double *EdgeX;

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

	//Basic constructor
	PStep_SeparationAlgorithm1(PStep_AlgorithmMembers& InitAlgorithmMembers);

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

	//Separate capacity cuts using the algorithm of Lysgaard.
	//The cuts are stored in AlgorithmMembers.CapacityCuts, new cuts are appended to the list.
	virtual void Separate();

	//Capacity constraint separation functions:
	//------------------------------------------------------------------------------------

	//Separate capacity constraints using the package of Lysgaard.
	//The cuts are stored in AlgorithmMembers.CapacityCuts, new cuts are appended to the list.
	void SeparateCCLysgaard();

	//Other functions:
	//------------------------------------------------------------------------------------

	//Set the separation members pertaining to the used edges in the current solution,
	//i.e., NumberOfEdgesPlusOne, EdgeHead, EdgeTail, EdgeX.
	void SetCurrentEdges();

	//Compute the amount by which a constraint is violated.
	//The output is non-positive if there is no violation.
	//The values of the edge selection are taken from AlgorithmMembers.CurrentSolution.EdgeFraction.
	//If the bound of the cut acts as upper bound, set UpperBound to true, otherwise false
	double ComputeViolation(PStep_EdgeFlowCut &CurrentEdgeFlowCut, bool UpperBound);
	double ComputeViolation(PStep_EdgeAndCoefficientCut &CurrentEdgeAndCoefficientCut, bool UpperBound);

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

	//Default destructor
	virtual ~PStep_SeparationAlgorithm1();
};

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Separator 2:
//Separate capacity cuts. If it fails separate 2 edge hypotour cuts (2EH a.k.a. hypotours)
class PStep_SeparationAlgorithm2 : public PStep_SeparationAlgorithm1{
public:

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

	//Basic constructor
	PStep_SeparationAlgorithm2(PStep_AlgorithmMembers& InitAlgorithmMembers)
		:PStep_SeparationAlgorithm1(InitAlgorithmMembers)
	{};

	//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.
	virtual void Separate();

	//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 Separate2EHLysgaard();

};

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Separator 3:
//Separate capacity cuts. If it fails separate strengthened comb cuts.
//If that also fails separate 2 edge hypotour cuts (2EH a.k.a. hypotours).
class PStep_SeparationAlgorithm3 : public PStep_SeparationAlgorithm2{
public:

	//Lower bound on the demand that must be delivered on any route
	//in a feasible CVRP solution, as used by Lysgaard
	short int QMin;

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

	//Basic constructor
	PStep_SeparationAlgorithm3(PStep_AlgorithmMembers& InitAlgorithmMembers);

	//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 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.
	virtual void Separate();

	//Strengthened comb separation functions:
	//------------------------------------------------------------------------------------

	//Separate strengthened comb cuts using the algorithm of Lysgaard.
	//These cuts are stored in AlgorithmMembers.StrengthenedCombCuts, new cuts are appended to the list.
	void SeparateSCombLysgaard();

};

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Separator 4:
//Separate capacity cuts. If it fails separate framed capacity cuts cuts.
//If that fails separate strengthened comb cuts.
//If that also fails separate 2 edge hypotour cuts (2EH a.k.a. hypotours).
class PStep_SeparationAlgorithm4 : public PStep_SeparationAlgorithm3{
public:

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

	//Basic constructor
	PStep_SeparationAlgorithm4(PStep_AlgorithmMembers& InitAlgorithmMembers)
		:PStep_SeparationAlgorithm3(InitAlgorithmMembers)
	{};

	//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.
	virtual void Separate();

	//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 SeparateFCCLysgaard();

};

//Separator 5:
//Separate capacity cuts. If it fails separate framed capacity cuts cuts.
//I that fails separate homogeneous hypotour cuts.
//If that fails separate strengthened comb cuts.
//If that also fails separate 2 edge hypotour cuts (2EH a.k.a. hypotours).
class PStep_SeparationAlgorithm5 : public PStep_SeparationAlgorithm4{
public:

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

	//Basic constructor
	PStep_SeparationAlgorithm5(PStep_AlgorithmMembers& InitAlgorithmMembers)
		:PStep_SeparationAlgorithm4(InitAlgorithmMembers)
	{};

	//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 homogeneous multistar cuts using the algorithm of Lysgaard.
	//These cuts are stored in AlgorithmMembers.HomogeneousMultistarCuts, 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.
	virtual void Separate();

	//Homogeneous multistar cut separation functions:
	//------------------------------------------------------------------------------------

	//Separate homogeneus multistar cuts using the algorithm of Lysgaard.
	//These cuts are stored in AlgorithmMembers.HomogeneousMultistar, new cuts are appended to the list.
	void SeparateHMCLysgaard();

};

//Separator 6:
//Simultaneously separate capacity, framed capacity, homogenous multistar,
//strengthened comb and 2 edge hypotour cuts uing the algorithm of Lysgaard.
class PStep_SeparationAlgorithm6 : public PStep_SeparationAlgorithm5{
public:

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

	//Basic constructor
	PStep_SeparationAlgorithm6(PStep_AlgorithmMembers& InitAlgorithmMembers)
		:PStep_SeparationAlgorithm5(InitAlgorithmMembers)
	{};

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

	//Simultaneously separate capacity, framed capacity, homogenous multistar,
	//strengthened comb and 2 edge hypotour cuts uing the algorithm of Lysgaard.
	virtual void Separate();

};

//Separator 7:
//Separate cuts using the package of Lysgaard. Separate capacity cuts, if it fails
//separate framed capacity cuts. Then separate in revolving order (until one is succesful
//or all have failed) homogenous multistar, strengthened comb and 2 edge hypotour cuts.
class PStep_SeparationAlgorithm7 : public PStep_SeparationAlgorithm6{
public:

	//Index indicating which revolving strategy is used.
	//1: homogenous multistar, strengthened comb and 2 edge hypotour cuts
	//2: strengthened comb, 2 edge hypotour cuts and homogenous multistar
	//3: 2 edge hypotour cuts, homogenous multistar and strengthened comb
	short int RevolvingIndex;

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

	//Basic constructor
	PStep_SeparationAlgorithm7(PStep_AlgorithmMembers& InitAlgorithmMembers)
		:PStep_SeparationAlgorithm6(InitAlgorithmMembers)
	{
		RevolvingIndex = 1;
	};

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

	//Separate cuts using the package of Lysgaard. Separate capacity cuts, if it fails
	//separate framed capacity cuts. Then separate in revolving order (until one is succesful
	//or all have failed) homogenous multistar, strengthened comb and 2 edge hypotour cuts.
	virtual void Separate();

	//Revolving separationg routines:
	//------------------------------------------------------------------------------------

	//Separate cuts of multiple types using the package of Lysgaard. If the separation of one
	//type fails, move to the next type. The types are in order: 
	//homogenous multistar, strengthened comb and 2 edge hypotour cuts
	void RevolvingSeparation1();
		
	//Separate cuts of multiple types using the package of Lysgaard. If the separation of one
	//type fails, move to the next type. The types are in order: 
	//strengthened comb, 2 edge hypotour cuts and homogenous multistar
	void RevolvingSeparation2();
	
	//Separate cuts of multiple types using the package of Lysgaard. If the separation of one
	//type fails, move to the next type. The types are in order: 
	//2 edge hypotour cuts, homogenous multistar and strengthened comb
	void RevolvingSeparation3();

};

//Separator 9:
//Separate capacity cuts. If it fails separate framed capacity cuts cuts.
//I that fails separate homogeneous hypotour cuts.
//If that fails separate strengthened comb cuts.
class PStep_SeparationAlgorithm9 : public PStep_SeparationAlgorithm7{
public:

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

	//Basic constructor
	PStep_SeparationAlgorithm9(PStep_AlgorithmMembers& InitAlgorithmMembers)
		:PStep_SeparationAlgorithm7(InitAlgorithmMembers)
	{};

	//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 homogeneous multistar cuts using the algorithm of Lysgaard.
	//These cuts are stored in AlgorithmMembers.HomogeneousMultistarCuts, 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.
	virtual void Separate();

};

#endif