/*Header file of the PStep_ColumnGenerator class

This file also includes derived classes of PStep_ColumnGenerator.

Implementation can be found in PStep_ColumnGenerator.cpp.
Implementation of PStep_ColumnGeneratorX can be found in PStep_ColumnGeneratorX.cpp.

This class represents a column generator for the p-step formulation of the CVRP.

*/

#ifndef _PSTEP_COLUMNGENERATOR_H
#define _PSTEP_COLUMNGENERATOR_H

#include "PStep_PricingProblem.h"
#include "PStep_TreeNode.h"
#include "PStep_AlgorithmMembers.h"
#include "PStep_CG1PreprocessedPricingInfo.h"
#include "PStep_Adder.h"
#include "PStep_PricingProblemSolver.h"
#include "PStep_CG1_DSSRPricingProblemProgress.h"

//Class used to represent a column generator for the p-step formulation of the CVRP.
class PStep_ColumnGenerator{
public:

	//Algorithm members
	PStep_AlgorithmMembers& AlgorithmMembers;

	//Duals:
	//Duals corresponding to CustomerAssignmentConstraints
	double* Lambda;
	//Duals corresponding to DegreeConstraints
	double* Mu;
	//Duals corresponding to DemandFlowConstraints
	double* Nu;
	//Duals corresponding to EdgeFlowConstraints
	double* Pi;

	//p-step adder
	PStep_Adder& Adder;

	//p-step adder
	PStep_PricingProblemSolver& Solver;

	//Decremental state-space relaxation members:
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

	//Indicator, indicating whether dynamic state-space relaxation is applied
	//NOTE: it is supposed to be coupled to PStep_Adder.ApplyDSSR.
	bool ApplyDSSR;

	//Indicator indicating whether it is necessary to rerun the pricing algorithms.
	bool RerunRequired;

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

	//Basic constructor
	//Initializes the arrays of the duals to the appropriate sizes
	PStep_ColumnGenerator(PStep_AlgorithmMembers& InitAlgorithmMembers, PStep_Adder& InitAdder, PStep_PricingProblemSolver& InitSolver);

	//Generate columns
	//------------------------------------------------------------------------------------
	
	//Generate columns
	virtual void GenerateColumns() = 0;

	//Column generator intended to be called after GenerateColumns failed to generate
	//columns and no cuts were generated as well.
	virtual void GenerateColumnsPhaseTwo(){};

	//Print functions
	//------------------------------------------------------------------------------------

	//Print Lambda
	void PrintLambda();

	//Print Mu
	void PrintMu();

	//Print Nu
	void PrintNu();

	//Print Pi
	void PrintPi();

	//Decremental state-space relaxation functions:
	//------------------------------------------------------------------------------------

	//Reset DSSN neighborhoods.
	virtual void ResetDSSRNeighbourhoods(){};

	//Set RerunRequired of all relevant pricing problems to NewRerunRequired.
	virtual void SetRerunRequiredPerPricingProblem(bool NewRerunRequired){};

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

	//Default destructor
	virtual ~PStep_ColumnGenerator();

};

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

//Column generator 1:
//Solve pricing problem seperately for every(non - redundant) start and end node combination.
//The pricing problems are solved in a layered style, meaning dominance is only applied for labels
//corresponding to partial paths containg the same amount of locations and finishing at the same node.
//The capacity of a p-step that does not finish at the depot is the vehicle capacity minus the minimal
//load of a p-step, taking into account the start and end location of the p-step. The maximum starting
//load is set accordingly.
//On top of that, the unreachability setter takes in to account the demand of the location to which
//the extender is currently extending. In layer l (start counting at 1) of a p-step not ending at the 
//depot the minimal load of 2p-l locations is taken into account. While for a p-step ending at the depot,
//the minimal load of p-l locations is taken into account.
//Finally, we do not consider all pricing problems, in case p >= {maximum number of arcs on a route}/2.
class PStep_ColumnGenerator1 : public PStep_ColumnGenerator{
protected:

	//A template used for creating reduced costs.
	double** ReducedCostTemplate;

	//Layered labeling heuristic members:
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

	//Indicator indicating whether a limited set of arcs should be used
	bool UseLimitedArcs;

	//Indicator indicating whether Reachability should not be checked when performing a dominance check.
	bool DoNotCheckReachability;

public:

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

	//Basic constructor
	//Initializes the arrays of the duals to the appropriate sizes
	PStep_ColumnGenerator1(PStep_AlgorithmMembers& InitAlgorithmMembers, PStep_Adder& InitAdder, PStep_PricingProblemSolver& InitSolver);

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

	//Solve pricing problem seperately for every(non - redundant) start and end node combination.
	//The pricing problems are solved in layered style, meaning dominance is only applied for labels
	//corresponding to partial paths containg the same amount of locations and finishing at the same node.
	void GenerateColumns();

	//Solve pricing problem seperately for every(non - redundant) start and end node combination.
	//The pricing problems are solved in layered style, meaning dominance is only applied for labels
	//corresponding to partial paths containg the same amount of locations and finishing at the same node.
	void GenerateColumns1();

	//Decremental state space relaxation functions:
	//------------------------------------------------------------------------------------

	//Reset DSSR attributes, for all pricing problems.
	virtual void ResetDSSRNeighbourhoods();

	//Set RerunRequired of all relevant pricing problems to NewRerunRequired.
	virtual void SetRerunRequiredPerPricingProblem(bool NewRerunRequired);

protected:
	//Reduced cost functions:
	//------------------------------------------------------------------------------------

	//Set the reduced costs template.
	//The costs will be set to TravelCosts-Pi-2*lambda.
	//It is assumed that ReducedCostTemplate is empty when calling this function.
	void SetReducedCostTemplate();

	//Set the reduced costs of a pricing problem, in particular ReducedArcCosts and ReducedCostConstant.
	//It is assumed that PricingProblem.ReducedArcCosts is already initialized when calling
	//this function.
	//Furthermore, it is assumed that ReducedCostTemplate is initialized to TravelCost-Pi.
	//Note for use:
	//- In the case of zero starting load: Dual = -Nu[StartLocation]
	//- In the case of maximum starting load: Dual = +Nu[EndLocation]
	void SetReducedCosts(PStep_PricingProblem &PricingProblem, double Dual, double ReducedCostConstant);

public:

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

	//Default destructor
	virtual ~PStep_ColumnGenerator1();

};

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

//Column generator 2:
//First solve the pricing problem heuristically, only if no negative reduced cost p - step is found, run
//column generator 1.
//When solving the pricing problem heuristically, apply the heuristic to every (non-redundant) start and
//end node combination, exactly like column generator 1.
//The pricing heuristic is a local search algorithm. Only accepting improving moves. The start and end
//nodes remain fixed troughout the search. Swap is used. For p-steps that start at the depot, also use
//insert and remove. To initialize the pricing problems use greedy insert, or the p-step depot-sink.
//Additionaly, apply the heuristic with as strating point the p-steps that are selected in the current
//solution of the column generation algorithm.
//The heuristic per start and end node combination terminates when a negative reduced cost p-step is found,
//no improvement is found or a maximum number of iterations is reached.
class PStep_ColumnGenerator2: public PStep_ColumnGenerator1{
protected:

	//DemandIncrease[i][j] gives the increase in demand when adding
	//customer i to the p-step and removing j from the p-step (Demand[i]-Demand[j]).
	//i=0 is the first customer.
	double** DemandIncrease;

public:

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

	//Basic constructor
	//Initializes the arrays of the duals to the appropriate sizes
	//Preprocessing for the local search.
	PStep_ColumnGenerator2(PStep_AlgorithmMembers& InitAlgorithmMembers, PStep_Adder& InitAdder, PStep_PricingProblemSolver& InitSolver);

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

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

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

	//Default destructor
	virtual ~PStep_ColumnGenerator2();

};

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

//Column generator 3:
//First use a heuristic labeling algorithm, in which only a limited number of arcs is used. Only if no
//negative reduced cost p-step is found, run column generator 1.
//Per customer intialize a limited set of out arcs. Select the cheapest arcs in use, always include all 
//arcs connected to the depot. Next apply the labeling algorithm as in column generator 1 using only these
//arcs.
class PStep_ColumnGenerator3 : public PStep_ColumnGenerator2{
public:

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

	//Basic constructor
	PStep_ColumnGenerator3(PStep_AlgorithmMembers& InitAlgorithmMembers, PStep_Adder& InitAdder, PStep_PricingProblemSolver& InitSolver)
	:PStep_ColumnGenerator2(InitAlgorithmMembers, InitAdder, InitSolver)
	{};

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

	//First use a heuristic labeling algorithm, in which only a limited number of arcs is used.Only if no
	//negative reduced cost p-step is found, run column generator 1.
	void GenerateColumns();

	//Solve pricing problem seperately for every(non - redundant) start and end node combination.
	//The pricing problems are solved heuristically using column generator 1 where only a limited number
	//of arcs are considered.
	void GenerateColumns3();

};

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

//Column generator 4:
//Apply the local search heuristic of ColumnGenerator2, if it fails apply ColumnGenerator1 with a limited
//number of arcs like in ColumnGenerator3, if that fails as well apply ColumnGenerator1
class PStep_ColumnGenerator4 : public PStep_ColumnGenerator3{
public:

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

	//Basic constructor
	PStep_ColumnGenerator4(PStep_AlgorithmMembers& InitAlgorithmMembers, PStep_Adder& InitAdder, PStep_PricingProblemSolver& InitSolver)
		:PStep_ColumnGenerator3(InitAlgorithmMembers, InitAdder, InitSolver)
	{};

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

	//Apply the local search heuristic of ColumnGenerator2, if it fails apply ColumnGenerator1 with a limited
	//number of arcs like in ColumnGenerator3, if that fails as well apply ColumnGenerator1
	void GenerateColumns();

};

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

//Column generator 5:
//Use column generator 1, but apply decremental state-space relaxation.
class PStep_ColumnGenerator5 : public PStep_ColumnGenerator4{
public:

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

	//Basic constructor
	PStep_ColumnGenerator5(PStep_AlgorithmMembers& InitAlgorithmMembers, PStep_Adder& InitAdder, PStep_PricingProblemSolver& InitSolver)
		:PStep_ColumnGenerator4(InitAlgorithmMembers, InitAdder, InitSolver)
	{
		ApplyDSSR = true;
		RerunRequired = true;
		InitAdder.RerunRequired = &RerunRequired;
	};

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

	//Use column generator 1, but apply decremental state-space relaxation.
	void GenerateColumns();

	//Use column generator 1, but apply decremental state-space relaxation.
	void GenerateColumns5();

};

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

//Column generator 6:
//Use neighborhood search heuristic, if it fails apply decremental state-space relaxation, column generator 5.
class PStep_ColumnGenerator6 : public PStep_ColumnGenerator5{
public:

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

	//Basic constructor
	PStep_ColumnGenerator6(PStep_AlgorithmMembers& InitAlgorithmMembers, PStep_Adder& InitAdder, PStep_PricingProblemSolver& InitSolver)
		: PStep_ColumnGenerator5(InitAlgorithmMembers, InitAdder, InitSolver)
	{};

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

	//Use neighborhood search heuristic, column generator 2, if it fails apply decremental
	//state-space relaxation, column generator 5.
	void GenerateColumns();

};

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

//Column generator 7:
//Use neighborhood search heuristic, if it fails apply decremental state-space relaxation, first a labeling heuristic 
//as in column generator 3, then an exact labeling algorithm, column generator 5.
class PStep_ColumnGenerator7 : public PStep_ColumnGenerator6{
public:

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

	//Basic constructor
	PStep_ColumnGenerator7(PStep_AlgorithmMembers& InitAlgorithmMembers, PStep_Adder& InitAdder, PStep_PricingProblemSolver& InitSolver)
		: PStep_ColumnGenerator6(InitAlgorithmMembers, InitAdder, InitSolver)
	{};

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

	//Use neighborhood search heuristic, if it fails apply decremental state-space relaxation, first a labeling heuristic 
	//as in column generator 3, then an exact labeling algorithm, column generator 5.
	void GenerateColumns();

};

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

//Column generator 8:
//First use a heuristic labeling algorithm, in which Reachability is not considered in the
//dominance check. Only if no negative reduced cost p-step is found, run column generator 1.
class PStep_ColumnGenerator8 : public PStep_ColumnGenerator7{
public:

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

	//Basic constructor
	PStep_ColumnGenerator8(PStep_AlgorithmMembers& InitAlgorithmMembers, PStep_Adder& InitAdder, PStep_PricingProblemSolver& InitSolver)
		: PStep_ColumnGenerator7(InitAlgorithmMembers, InitAdder, InitSolver)
	{
		ApplyDSSR = false;
	};

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

	//First use a heuristic labeling algorithm, in which Reachability is not considered in the
	//dominance check. Only if no negative reduced cost p-step is found, run column generator 1.
	void GenerateColumns();

	//Solve pricing problem seperately for every(non - redundant) start and end node combination.
	//The pricing problems are solved heuristically using column generator 1 where Reachability 
	//is not considered in the Dominance check.
	void GenerateColumns8();

};

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

//Column generator 9:
//First use a heuristic labeling algorithm, in which Reachability is not considered in the
//dominance check and only limited arcs are used. Only if no negative reduced cost p-step
//is found, apply exact labeling column generator 1.
class PStep_ColumnGenerator9 : public PStep_ColumnGenerator8{
public:

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

	//Basic constructor
	PStep_ColumnGenerator9(PStep_AlgorithmMembers& InitAlgorithmMembers, PStep_Adder& InitAdder, PStep_PricingProblemSolver& InitSolver)
		: PStep_ColumnGenerator8(InitAlgorithmMembers, InitAdder, InitSolver)
	{};

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

	//First use a heuristic labeling algorithm, in which Reachability is not considered in the
	//dominance check and only limited arcs are used. Only if no negative reduced cost p-step
	//is found, apply exact labeling column generator 1.
	void GenerateColumns();

};

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

//Column generator 10:
//Apply local search first, if it fails, apply column generator 9.
class PStep_ColumnGenerator10 : public PStep_ColumnGenerator9{
public:

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

	//Basic constructor
	PStep_ColumnGenerator10(PStep_AlgorithmMembers& InitAlgorithmMembers, PStep_Adder& InitAdder, PStep_PricingProblemSolver& InitSolver)
		: PStep_ColumnGenerator9(InitAlgorithmMembers, InitAdder, InitSolver)
	{};

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

	//Apply local search first, if it fails, apply column generator 9.
	void GenerateColumns();

};

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

//Column generator 11:
//Apply local search first, if it fails apply decremetal state-space relaxation.
//In this case, first apply heuristic labeling with a limited number of arcs and not
//considering reachability when checking dominance. If that fails apply exact labeling.
class PStep_ColumnGenerator11 : public PStep_ColumnGenerator5{
public:

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

	//Basic constructor
	PStep_ColumnGenerator11(PStep_AlgorithmMembers& InitAlgorithmMembers, PStep_Adder& InitAdder, PStep_PricingProblemSolver& InitSolver)
		: PStep_ColumnGenerator5(InitAlgorithmMembers, InitAdder, InitSolver)
	{};

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

	//Apply local search first, if it fails apply decremetal state-space relaxation.
	//In this case, first aply heuristic labeling with a limited number of arcs and not
	//considering reachability when checking dominance. If that fails apply exact labeling.
	void GenerateColumns();

};

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

//Column generator 12:
//The same as column generator 1, but now labels are only compared for dominance if they not only have visited the
//same number of arcs, but also have exactly the same load.
//NOTE: Column generator 12 only applies if the demand and capacity are integer!
class PStep_ColumnGenerator12 : public PStep_ColumnGenerator2{
public:

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

	//Basic constructor
	PStep_ColumnGenerator12(PStep_AlgorithmMembers& InitAlgorithmMembers, PStep_Adder& InitAdder, PStep_PricingProblemSolver& InitSolver)
		: PStep_ColumnGenerator2(InitAlgorithmMembers, InitAdder, InitSolver)
	{};

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

	//The same as column generator 1, but now labels are only compared for dominance if they not only have visited the
	//same number of arcs, but also have exactly the same load.
	//NOTE: Column generator 12 only applies if the demand and capacity are integer!
	void GenerateColumns();

	//Solve pricing problem seperately for every(non - redundant) start and end node combination.
	//The pricing problems are solved in double layered style, meaning dominance is only applied for labels
	//corresponding to partial paths containg the same amount of locations, the same load and finishing at
	//the same node.
	void GenerateColumns12();

};

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

//Column generator 13:
//First solve the pricing problem heuristically using local search. If it fails use
//the double layered labeling algorithm, column generator 12.
//NOTE: Column generator 13 only applies if the demand and capacity are integer!
class PStep_ColumnGenerator13 : public PStep_ColumnGenerator12{
public:

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

	//Basic constructor
	PStep_ColumnGenerator13(PStep_AlgorithmMembers& InitAlgorithmMembers, PStep_Adder& InitAdder, PStep_PricingProblemSolver& InitSolver)
		: PStep_ColumnGenerator12(InitAlgorithmMembers, InitAdder, InitSolver)
	{};

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

	//First solve the pricing problem heuristically using local search. If it fails use
	//the double layered labeling algorithm, column generator 12.
	//NOTE: Column generator 13 only applies if the demand and capacity are integer!
	void GenerateColumns();


};

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

//Column generator 14:
//The same as column generator 1, but using bi-directional labeling.
class PStep_ColumnGenerator14 : public PStep_ColumnGenerator2{
public:

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

	//Basic constructor
	PStep_ColumnGenerator14(PStep_AlgorithmMembers& InitAlgorithmMembers, PStep_Adder& InitAdder, PStep_PricingProblemSolver& InitSolver)
		: PStep_ColumnGenerator2(InitAlgorithmMembers, InitAdder, InitSolver)
	{
		ApplyDSSR = false;
	};

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

	//The same as column generator 1, but using bi-directional labeling.
	void GenerateColumns();

	//The same as column generator 1, but using bi-directional labeling.
	void GenerateColumns14();

};

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

//Column generator 15:
//First solve the pricing problem heuristically using local search. If it fails use
//the bi-directional layered labeling algorithm, column generator 14.
class PStep_ColumnGenerator15 : public PStep_ColumnGenerator14{
public:

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

	//Basic constructor
	PStep_ColumnGenerator15(PStep_AlgorithmMembers& InitAlgorithmMembers, PStep_Adder& InitAdder, PStep_PricingProblemSolver& InitSolver)
		: PStep_ColumnGenerator14(InitAlgorithmMembers, InitAdder, InitSolver)
	{};

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

	//First solve the pricing problem heuristically using local search. If it fails use
	//the bi-directional layered labeling algorithm, column generator 14.	
	void GenerateColumns();


};

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

//Column generator 16:
//First use a heuristic labeling algorithm, in which only a limited number of arcs is used. Only if no
//negative reduced cost p-step is found, run column generator 1.
//Per customer intialize a limited set of out arcs. Select the cheapest arcs in use, always include all 
//arcs connected to the depot. Next apply the labeling algorithm as in column generator 14 using only these
//arcs.
class PStep_ColumnGenerator16 : public PStep_ColumnGenerator15{
public:

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

	//Basic constructor
	PStep_ColumnGenerator16(PStep_AlgorithmMembers& InitAlgorithmMembers, PStep_Adder& InitAdder, PStep_PricingProblemSolver& InitSolver)
		:PStep_ColumnGenerator15(InitAlgorithmMembers, InitAdder, InitSolver)
	{};

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

	//First use a heuristic labeling algorithm, in which only a limited number of arcs is used. Only if no
	//negative reduced cost p-step is found, run column generator 14.
	void GenerateColumns();

	//Solve pricing problem seperately for every(non - redundant) start and end node combination.
	//The pricing problems are solved heuristically using column generator 14 where only a limited number
	//of arcs are considered.
	void GenerateColumns16();

};

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

//Column generator 17:
//Apply local search first, if it fails apply decremetal state-space relaxation.
//In this case, first apply heuristic labeling with a limited number of arcs and not
//considering reachability when checking dominance. If that fails apply exact labeling.
//For exact labeling, bi-directional layered labeling is used.
class PStep_ColumnGenerator17 : public PStep_ColumnGenerator16{
public:

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

	//Basic constructor
	PStep_ColumnGenerator17(PStep_AlgorithmMembers& InitAlgorithmMembers, PStep_Adder& InitAdder, PStep_PricingProblemSolver& InitSolver)
		: PStep_ColumnGenerator16(InitAlgorithmMembers, InitAdder, InitSolver)
	{
		ApplyDSSR = true;
		RerunRequired = true;
		InitAdder.RerunRequired = &RerunRequired;
	};

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

	//Apply local search first, if it fails apply decremetal state-space relaxation.
	//In this case, first apply heuristic labeling with a limited number of arcs and not
	//considering reachability when checking dominance. If that fails apply exact labeling.
	//For exact labeling, bi-directional layered labeling is used.
	void GenerateColumns();

};

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

//Column generator 18:
//Apply local search first, if it fails apply heuristic labeling while not
//considering reachability when checking dominance. If that fails apply exact labeling.
//For exact labeling, bi-directional layered labeling is used.
class PStep_ColumnGenerator18 : public PStep_ColumnGenerator16{
public:

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

	//Basic constructor
	PStep_ColumnGenerator18(PStep_AlgorithmMembers& InitAlgorithmMembers, PStep_Adder& InitAdder, PStep_PricingProblemSolver& InitSolver)
		: PStep_ColumnGenerator16(InitAlgorithmMembers, InitAdder, InitSolver)
	{};

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

	//Apply local search first, if it fails apply heuristic labeling while not
	//considering reachability when checking dominance. If that fails apply exact labeling.
	//For exact labeling, bi-directional layered labeling is used.
	void GenerateColumns();

};

//Column generator 19:
//The same setup as column generator 1, but using bi-directional labeling with completion bounds and
//decremental state space relaxation.
//Initially a regular bi-directional search is performed, for an initial state space relaxation.
//For any subsequent decremented state space relaxation, completion bounds are computed based on the
//previous state space and used for bi-directional labeling.
class PStep_ColumnGenerator19 : public PStep_ColumnGenerator17{
public:

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

	//Basic constructor
	PStep_ColumnGenerator19(PStep_AlgorithmMembers& InitAlgorithmMembers, PStep_Adder& InitAdder, PStep_PricingProblemSolver& InitSolver)
		: PStep_ColumnGenerator17(InitAlgorithmMembers, InitAdder, InitSolver)
	{};

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

	//The same setup as column generator 1, but using bi-directional labeling with completion bounds and
	//decremental state space relaxation.
	//Initially a regular bi-directional search is performed, for an initial state space relaxation.
	//For any subsequent decremented state space relaxation, completion bounds are computed based on the
	//previous state space and used for bi-directional labeling.
	void GenerateColumns();

	//The same setup as column generator 1, but using bi-directional labeling with completion bounds and
	//decremental state space relaxation.
	//NOTE: It is assumed that the completion bounds are set as well as the reduced costs. Moreover, it assumes
	//		decremental state-space relaxation is applied.
	void GenerateColumns19();

	//Neighbourhood functions
	//------------------------------------------------------------------------------------

	//Copy the current DSSRNeighbourhoods to old DSSRNeighbourhoods for all relevant pricining problems
	//which require a rerun.
	void CopyCurrentDSSRNeighbourhoodsToOld();

	//Completion bound functions
	//------------------------------------------------------------------------------------

	//Obtain the "second" half of the completion bounds for every relevant pricing problem
	//that requires a rerun.
	//That is, obtain the values of ForwardCompletionBounds[l][i], for all customers i and
	//layers l such that MaxNumberOfForwardArcs < l < NumberOfForwardLayers.
	//Furthermore, obtain the values of BackwardCompletionBounds[l][i] for all customers i
	//and layers l such that MaxNumberOfBackwardArcs < l < NumberOfBackwardLayers.
	//NOTE: It is assumed that ForwardLabels and BackwardLabels are sorted from lowest reduced costs
	//		to highest.
	void ObtainEverySecondHalfOfCompletionBounds();

	//Obtain the "first" half of the completion bounds for every relevant pricing problem
	//that requires a rerun.
	//That is, obtain the values of ForwardCompletionBounds[l][i], for all customers i and
	//layers l such that 0 < l <= MaxNumberOfForwardArcs.
	//Furthermore, obtain the values of ForwardCompletionBounds[l][i] for all customers i
	//and layers l such that 0 < l <= MaxNumberOfBackwardArcs.
	//NOTE: It is assumed that ForwardLabels and BackwardLabels are sorted from lowest reduced costs
	//		to highest.
	void ObtainEveryFirstHalfOfCompletionBounds();

	//Continue forward and backward labeling after a bidirectional labeling run.
	//The forward and backward labeling will be "completed" and the results will be
	//used to obtain completion bounds for a next run of bidirectional labeling.
	//The labelng algorithm will make use of completion bounds (those found by 
	//ObtainEverySecondHalfOfCompletionBounds).
	void ContinueForwardAndBackwardLabeling();

};

//Column generator 20:
//Apply local search first, if it fails apply decremetal state-space relaxation.
//In this case, first apply heuristic labeling with a limited number of arcs and not
//considering reachability when checking dominance. If that fails apply exact labeling.
//For exact labeling, bi-directional layered labeling is used.
//When labeling, completion bounds are used as in column generator 19
class PStep_ColumnGenerator20 : public PStep_ColumnGenerator19{
public:

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

	//Basic constructor
	PStep_ColumnGenerator20(PStep_AlgorithmMembers& InitAlgorithmMembers, PStep_Adder& InitAdder, PStep_PricingProblemSolver& InitSolver)
		: PStep_ColumnGenerator19(InitAlgorithmMembers, InitAdder, InitSolver)
	{};

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

	//Apply local search first, if it fails apply decremetal state-space relaxation.
	//In this case, first apply heuristic labeling with a limited number of arcs and not
	//considering reachability when checking dominance. If that fails apply exact labeling.
	//For exact labeling, bi-directional layered labeling is used.
	//When labeling, completion bounds are used as in column generator 19
	void GenerateColumns();

};

//Column generator 21:
//Apply local search first, if it fails apply decremetal state-space relaxation.
//In this case, first apply heuristic labeling with a limited number of arcs and not
//considering reachability when checking dominance.
//Do not apply exact labeling. This is only done in GenerateColumnsPhaseTwo.
//For exact labeling, bi-directional layered labeling is used.
//When labeling, completion bounds are used as in column generator 19.
class PStep_ColumnGenerator21 : public PStep_ColumnGenerator20{
public:

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

	//Basic constructor
	PStep_ColumnGenerator21(PStep_AlgorithmMembers& InitAlgorithmMembers, PStep_Adder& InitAdder, PStep_PricingProblemSolver& InitSolver)
		: PStep_ColumnGenerator20(InitAlgorithmMembers, InitAdder, InitSolver)
	{};

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

	//Apply local search first, if it fails apply decremetal state-space relaxation.
	//In this case, first apply heuristic labeling with a limited number of arcs and not
	//considering reachability when checking dominance.
	//Do not apply exact labeling. This is only done in GenerateColumnsPhaseTwo.
	//When labeling, completion bounds are used as in column generator 19.
	void GenerateColumns();

	//Bi-directional layered labeling is used.
	//When labeling, completion bounds are used as in column generator 19.
	void GenerateColumnsPhaseTwo();

};

#endif