/*Header file of the PStep_AlgorithmSettings class

*/

#ifndef _PSTEP_ALGORITHMSETTINGS_H
#define _PSTEP_ALGORITHMSETTINGS_H

//Class used to represent the PStep_AlgorithmSettings
class PStep_AlgorithmSettings{
public:

	//p
	short int p;

	//General settings:
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
	//Tolerance
	double Tolerance;

	//Time limit in seconds:
	int TimeLimit;

	//Branch and Price settings:
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
	//Relative optimality gap.
	//If (UB-LB)/UB <= RelativeOptGAP, the algorithm terminates
	double RelativeOptGap;

	//Absolute optimality gap
	//If (UB-LB) <= AbsoluteOptGAP, the algorithm terminates
	//Tip: If the travel costs have d significant decimal places, you might choose 0.1^x.
	double AbsoluteOptGap;

	//Initial routes
	//1: Add all return trips.
	//2: Create a solution by applying a greedy insertion heuristic.
	//   In case the number of vehicles is fixed, this is satisfied by the solution.
	//   The solution is decomposed into p-steps which are added.
	//3: Apply initialization 2 and additionally generate a p-step for every
	//	 relevant pricing problem by applying a greedy insertion heuristic.
	//	 For the pricing problems from the depot to the depot, add p-steps with a number
	//	 of arcs from 2 to p with starting load zero.
	//	 For the pricing problems from the depot to a customer, add p-steps with a number
	//	 of arcs from 1 to p with starting load zero.
	//	 For the pricing problems from a customer to a customer, add both a p-step with
	//	 zero starting load and maximal starting load.
	//	 For the pricing problems from a customer to the depot, add a p-step with maximal
	//	 starting load.
	int InitialPSteps;

	//Node selection strategy
	//1: Depth first
	//2: Lowest lower bound first
	//3: Depth first until an integer solution is found, then switch to lowest lower bound first
	short int NodeSelectionStrategy;

	//Branching strategy
	//1: Branch on most fractionally selected edge
	//2: Branch using the Lysgaard package
	short int BranchingStrategy;

	//Lysgaard target
	//A target value between 2 and 4 for selecting a set of edges to branch on
	//using the Lysgaard package
	double LysgaardTarget;

	//Column generation algorithm settings:
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

	//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.
	//	  If the capacity doe snot allow it, p-steps from i to j are never generated, or nodes and arcs that 
	//	  can not be visited on an i j p-step are removed from the network when generating these.
	//	  Finally, we do not consider all pricing problems, in case p >= {maximum number of arcs on a route}/2.
	//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.
	//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.
	//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
	//5:  Apply column generator 1. However, apply decremental state-space relaxation. Initially, all cycles are
	//	  allowed for each pricing problem, next they are solved. If for any of the pricing problems a negative
	//	  reduced cost column is found that do not contain forbidden cycles, add these to the column pool and iterate.
	//	  Also, if no negative reduced cost column is found at all, the current solution is optimal. Otherwise, for
	//	  each pricing problem, go over all generated p-steps with negative reduced costs and identify all forbidden
	//	  cycles that are used. Next, decrement the state-space relaxation as follows. All locations that are part of
	//	  the forbidden cycle get the start and end node of the cycle added to their neighborhood. Next, all pricing
	// 	  problems are resolved, applying ng-path relaxation with the updated neighborhoods. This procedure is applied
	//	  both in the case that ng-path relaxation is applied, or elementary paths are sought.
	//6:  First solve the pricing problem heuristically as in column generator 2, only if no negative reduced cost p-step
	//	  is found, run column generator 5.
	//7:  First solve the pricing problem heuristically as in column generator 2, only if it fails apply decremental
	//	  state-space relaxation, first with heuristic labeling as in column generator 3, then exactly using column
	//	  generator 1.
	//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.
	//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.
	//10: Apply local search first, if it fails, apply column generator 9.
	//11: 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.
	//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!
	//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!
	//14: The same as column generator 1, but using bi-directional labeling.
	//15: First solve the pricing problem heuristically using local search. If it fails use
	//	  the bi-directional layered labeling algorithm, column generator 14.
	//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 14.
	//	  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.
	//17: 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 bi-directional labeling.
	//18: Apply local search first, if it fails apply heuristic labeling while not
	//	  considering reachability when checking dominance. If that fails apply exact bi-directional labeling.
	//19: Apply bi-directional labeling with completion bounds in a decremental state-space setting.
	//20: The same column generator as 17 but now using completion bounds.
	//21: The same as 20 but exact column generation is done only in Phase Two.
	short int ColumnGenerator;

	//Pricing problem selection
	//1: Solve all pricing problems
	//2: Solve all pricing problems and store total potential savings of parallelisation
	//3: Solve all pricing problems in parallel
	short int PricingProblemSelection;

	//Route addition settings:
	//Type of addition of p-steps
	//1: Add all p-steps with negative reduced costs
	//NOTE: there are special cases for which there are settings that work in tandem with which p-steps are added:
	//- MaxMergeLabels
	short int AddPStepsSetting;

	//The bi-directional labeling algorithm stops after succesfully merging the first MaxMergeLabels
	//for a specific pricing problem.
	//It should be set greater or equal to 1.
	int MaxMergeLabels;

	//NG-path relaxation setting
	//If UseNGPathRelaxation=true, ng-path relaxation is applied.
	bool UseNGPathRelaxation;

	//The size of the neighbourhouds.
	//It is used in case ng-path relaxation is applied.
	short int NeighbourhoodSize;

	//The size of the neighbourhoods of column generator 3
	short int CG3NeighbourhoodSize;

	//Use adjusted capacity.
	//For pricing problems from i to j, j not the depot, the demand of the p-1 smallest
	//customers (excluding i and j) are subtracted from the vehicle capacity and used as
	//capacity in the pricing problem.
	bool UseAdjustedCapacity;

	//Point of reseting the decremental state-space relaxation
	//1: The neighborhoods are initialized at the start of the algorithm and never reset.
	//2: The neighborhoods are reset every time a new node in the search tree is considered.
	//3: The neighborhoods are reset every time a new pricing problem needs to be solved.
	short int DSSRReset;

	//Column management settings
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

	//Column manager:
	//0: No column management is applied.
	//1: All columns with reduced costs higher than CMThreshold are removed from the 
	//	 formulation and put in a shortlist.
	//2: All columns with reduced costs higher than CMThreshold are removed from the 
	//	 formulation and put in a shortlist, as long as the number of p-steps is greater
	//	 than CMNumberOfColumnsLimit.
	//	 When generating columns, first the short list is processed to search for negative
	// 	 reduced cost columns.
	//3: All columns are sorted in terms of reduced costs and the CMNumberOfColumnsLimit
	//	 columns with the lowest reduced costs are maintained. All other columns with
	//	 positive reduced costs are removed.
	//	 When generating columns, first the short list is processed to search for negative
	// 	 reduced cost columns.
	short int ColumnManager;

	//Threshold used by the column manager for removing p-steps
	double CMThreshold;

	//Columns are only removed if the total number is more than CMNumberOfColumnsLimit.
	int CMNumberOfColumnsLimit;

	//Valid inequality settings:
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

	//Number of vehicles lower bound:
	//If UseNumberOfVehiclesLowerBound is true, and the number of vehicles is not fixed,
	//a lower bound on the number of vehicles used is added to the formulation.
	//The lower bound is the total demand  divided by the vehicle capacity rounded up.
	//The inequality is added at each node of the branching tree as a branching cuts.
	bool UseNumberOfVehiclesLowerBound;

	//Separation strategy
	//0: No valid inequalities are separated.
	//1: Separate capacity constraints at every node in the branching tree.
	//	 Lysgaard's algorithm is used, it makes use of MaxCCPerIteration,
	//	 however it is not guaranteed to satisfy this maximum.
	//	 Demand and capacity should be integer.
	//2: Apply separation strategy 1. If it fails, apply the same strategy for separating
	//	 2 edge hypotour cuts.
	//3: Separate cuts using the package of Lysgaard, if separation of one type fails
	//	 continue with the following until succesful. They are in order: capacity,
	//	 strengthened comb, 2 edge hypotour.
	//4: Separate cuts using the package of Lysgaard, if separation of one type fails
	//	 continue with the following until succesful. They are in order: capacity,
	//	 framed capacity, strengthened comb, 2 edge hypotour.
	//5: Separate cuts using the package of Lysgaard, if separation of one type fails
	//	 continue with the following until succesful. They are in order: capacity,
	//	 framed capacity, homogenous multistar, strengthened comb, 2 edge hypotour.
	//6: Simultaneously separate capacity, framed capacity, homogenous multistar,
	//	 strengthened comb and 2 edge hypotour cuts.
	//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.
	//8: Use separation algorithm 7 in the rootnode and separation algorithm 1 for all other nodes.
	//9: Separate cuts using the package of Lysgaard, if separation of one type fails
	//	 continue with the following until succesful. They are in order: capacity,
	//	 framed capacity, homogenous multistar, strengthened comb.
	//10: Use separation algorithm 9 in the rootnode and separation algorithm 1 for all other nodes.
	short int SeparationStrategy;

	//Capacity constraint settings:
	//Maximum number of capacity cuts per iteration.
	int MaxCCPerIteration;
	//Minimum violation of a capacity cut when separating
	double MinimumCCViolation;

	//2 edge hypotour settings:
	//Maximum number of 2 edge hypotour cuts per iteration.
	int Max2EHPerIteration;
	//Minimum violation of a 2 edge hyptour cut when separating
	double Minimum2EHViolation;

	//Strengthened comb settings:
	//Maximum number of strengthened comb cuts per iteration.
	int MaxSCombPerIteration;
	//Minimum violation of a strengthened comb cut when separating
	double MinimumSCombViolation;

	//Framed capacity constraint settings:
	//Maximum number of tree nodes explored by the Lysgaard separation algorithm
	int MaxFCCNoTreeNodes;
	//Maximum number of framed capacity cuts per iteration.
	int MaxFCCPerIteration;
	//Minimum violation of a framed capacity cut when separating
	double MinimumFCCViolation;

	//Homogeneous multistar settings:
	//Maximum number of homogeneous multistar cuts per iteration.
	int MaxHMCPerIteration;
	//Minimum violation of a homogeneous multistar cut when separating
	double MinimumHMCViolation;

	//Print settings:
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

	//Print column generation progress at each iteration
	bool PrintCGProgress;

	//Print branch and price progress at each iteration
	bool PrintBPProgress;

	//The number of branching iterations in between printing progress.
	int PrintBPPeriod;

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

	//Default Constructor
	PStep_AlgorithmSettings(){};

	//Basic Constructor
	PStep_AlgorithmSettings(short int Initp, int InitTimeLimit, bool InitPrintCGProgress, bool InitPrintBPProgress)	{

		p = Initp;
		Tolerance = 0.00001;
		TimeLimit = InitTimeLimit;
		RelativeOptGap = 0.00001;
		AbsoluteOptGap = 0.00001;
		InitialPSteps = 2;
		NodeSelectionStrategy = 2;
		BranchingStrategy = 1;
		LysgaardTarget = 3;
		ColumnGenerator = 1;
		PricingProblemSelection = 1;
		AddPStepsSetting = 1;
		MaxMergeLabels = 100;
		UseNGPathRelaxation = false;
		NeighbourhoodSize = 5;
		CG3NeighbourhoodSize = 10;
		UseAdjustedCapacity = true;
		DSSRReset = 1;
		ColumnManager = 0;
		CMThreshold = 10;
		CMNumberOfColumnsLimit = 1000;
		UseNumberOfVehiclesLowerBound = false;
		SeparationStrategy = 0;
		MaxCCPerIteration = 1000;
		MinimumCCViolation = 0.1;
		Max2EHPerIteration = 1000;
		Minimum2EHViolation = 0.1;
		MaxSCombPerIteration = 1000;
		MinimumSCombViolation = 0.1; /*0.25*/
		MaxFCCNoTreeNodes = 20000;
		MaxFCCPerIteration = 1000;
		MinimumFCCViolation = 0.1;
		MaxHMCPerIteration = 1000;
		MinimumHMCViolation = 0.1;
		PrintCGProgress = InitPrintCGProgress;
		PrintBPProgress = InitPrintBPProgress;
		PrintBPPeriod = 1;

	};

};

#endif