/*Header file of the PStep_Algorithm class

This class contains members and functions that allow solving the symmetric CVRP using a
Branch-Price-and-Cut algorithm based on p-steps.

Implementation of the initialization functions can be found in PStep_Algorithm_Initialization.cpp.
Implementation of the function PStep_Algorithm::SolveRootNode can be found in PStep_Algorithm_SolveRootNode.cpp.
Implementation of the function PStep_Algorithm::BranchePriceAndCut can be found in PStep_Algorithm_BranchPriceAndCut.cpp.
Implementation of the function PStep_Algorithm::ColumnGeneration can be found in PStep_Algorithm_ColumnGeneration.cpp.
Implementation of the p-step functions can be found in PStep_Algorithm_PStepFunctions.cpp.
Implementation of the arc functions can be found in PStep_Algorithm_ArcFunctions.cpp.
Implementation of the cut functions can be found in PStep_Algorithm_CutFunctions.cpp.
Implementation of the branching functions can be found in PStep_Algorithm_BranchingFunctions.cpp.
Implementation of the other functions can be found in PStep_Algorithm_OtherFunctions.cpp.

//NOTES:
- We assume travel costs are symmetric.
- We assume that p-steps cannot have the depot in the middle (i.e., only the first and last location can be the depot).

*/

#ifndef _PSTEP_ALGORITHM_H
#define _PSTEP_ALGORITHM_H

#include "PStep_AlgorithmMembers.h"
#include "PStep_ColumnGenerator.h"
#include "PStep_ColumnManager.h"
#include "PStep_SeparationManager.h"
#include "PStep_TreeNodeSelecter.h"
#include "PStep_Brancher.h"
#include <ilcplex/ilocplex.h>

//Class used to represent the Branch-Price-and-Cut algorithm based on p-steps
class PStep_Algorithm{

public:
	PStep_AlgorithmMembers AlgorithmMembers;

private:
	//p-step adder:
	//-------------
	//List of PStep_AllPStepsAdders
	std::list<PStep_AllPStepsAdder> ListOfAllPStepAdders;
	//Pointer to a selected PStep_Adder
	PStep_Adder* CurrentPStepAdder;

	//Pricing problem solver:
	//-----------------------
	//List of PStep_AllPricingProblemSequentialSolvers
	std::list<PStep_AllPricingProblemSequentialSolver> ListOfAllPricingProblemSequentialSolvers;
	//List of PStep_AllPricingProblemSequentialSolverSavingsTimer
	std::list<PStep_AllPricingProblemSequentialSolverSavingsTimer> ListOfAllPricingProblemSequentialSolverSavingsTimers;
	//List of PStep_AllPricingProblemParallelSolvers
	std::list<PStep_AllPricingProblemParallelSolver> ListOfAllPricingProblemParallelSolvers;
	//Pointer to selected PStep_PricingProblemSolver
	PStep_PricingProblemSolver* CurrentPricingProblemSolver;

	//Column generator:
	//-----------------
	//List of PStep_ColumnGenerator1s
	std::list<PStep_ColumnGenerator1> ListOfColumnGenerator1s;
	//List of PStep_ColumnGenerator2s
	std::list<PStep_ColumnGenerator2> ListOfColumnGenerator2s;
	//List of PStep_ColumnGenerator3s
	std::list<PStep_ColumnGenerator3> ListOfColumnGenerator3s;
	//List of PStep_ColumnGenerator4s
	std::list<PStep_ColumnGenerator4> ListOfColumnGenerator4s;
	//List of PStep_ColumnGenerator5s
	std::list<PStep_ColumnGenerator5> ListOfColumnGenerator5s;
	//List of PStep_ColumnGenerator6s
	std::list<PStep_ColumnGenerator6> ListOfColumnGenerator6s;
	//List of PStep_ColumnGenerator7s
	std::list<PStep_ColumnGenerator7> ListOfColumnGenerator7s;
	//List of PStep_ColumnGenerator8s
	std::list<PStep_ColumnGenerator8> ListOfColumnGenerator8s;
	//List of PStep_ColumnGenerator9s
	std::list<PStep_ColumnGenerator9> ListOfColumnGenerator9s;
	//List of PStep_ColumnGenerator10s
	std::list<PStep_ColumnGenerator10> ListOfColumnGenerator10s;
	//List of PStep_ColumnGenerator11s
	std::list<PStep_ColumnGenerator11> ListOfColumnGenerator11s;
	//List of PStep_ColumnGenerator12s
	std::list<PStep_ColumnGenerator12> ListOfColumnGenerator12s;
	//List of PStep_ColumnGenerator13s
	std::list<PStep_ColumnGenerator13> ListOfColumnGenerator13s;
	//List of PStep_ColumnGenerator14s
	std::list<PStep_ColumnGenerator14> ListOfColumnGenerator14s;
	//List of PStep_ColumnGenerator15s
	std::list<PStep_ColumnGenerator15> ListOfColumnGenerator15s;
	//List of PStep_ColumnGenerator16s
	std::list<PStep_ColumnGenerator16> ListOfColumnGenerator16s;
	//List of PStep_ColumnGenerator17s
	std::list<PStep_ColumnGenerator17> ListOfColumnGenerator17s;
	//List of PStep_ColumnGenerator18s
	std::list<PStep_ColumnGenerator18> ListOfColumnGenerator18s;
	//List of PStep_ColumnGenerator19s
	std::list<PStep_ColumnGenerator19> ListOfColumnGenerator19s;
	//List of PStep_ColumnGenerator20s
	std::list<PStep_ColumnGenerator20> ListOfColumnGenerator20s;
	//List of PStep_ColumnGenerator21s
	std::list<PStep_ColumnGenerator21> ListOfColumnGenerator21s;
	//Pointer to selected PStep_ColumnGenerator
	PStep_ColumnGenerator* CurrentColumnGenerator;

	//Column managers:
	//----------------
	//List of PStep_ColumnManagers
	std::list<PStep_ColumnManager> ListOfColumnManagers;
	//List of PStep_ColumnManager1s
	std::list<PStep_ColumnManager1> ListOfColumnManager1s;
	//List of PStep_ColumnManager2s
	std::list<PStep_ColumnManager2> ListOfColumnManager2s;
	//List of PStep_ColumnManager3s
	std::list<PStep_ColumnManager3> ListOfColumnManager3s;
	//Pointer to selected column manager
	PStep_ColumnManager* CurrentColumnManager;

	//Separation Algorithm:
	//---------------------
	//Pointer to selected PStep_SeparationAlgorithm
	PStep_SeparationAlgorithm* CurrentSeparationAlgorithm;

	//Separation Managers:
	//--------------------
	//List of PStep_SeperationManager0s:
	std::list<PStep_SeparationManager0> ListOfSeperationManager0s;
	//List of PStep_SeperationManager1s:
	std::list<PStep_SeparationManager1> ListOfSeperationManager1s;
	//List of PStep_SeperationManager2s:
	std::list<PStep_SeparationManager2> ListOfSeperationManager2s;
	//List of PStep_SeperationManager3s:
	std::list<PStep_SeparationManager3> ListOfSeperationManager3s;
	//List of PStep_SeperationManager4s:
	std::list<PStep_SeparationManager4> ListOfSeperationManager4s;
	//List of PStep_SeperationManager5s:
	std::list<PStep_SeparationManager5> ListOfSeperationManager5s;
	//List of PStep_SeperationManager6s:
	std::list<PStep_SeparationManager6> ListOfSeperationManager6s;
	//List of PStep_SeperationManager7s:
	std::list<PStep_SeparationManager7> ListOfSeperationManager7s;
	//List of PStep_SeperationManager8s:
	std::list<PStep_SeparationManager8> ListOfSeperationManager8s;
	//List of PStep_SeperationManager9s:
	std::list<PStep_SeparationManager9> ListOfSeperationManager9s;
	//List of PStep_SeperationManager10s:
	std::list<PStep_SeparationManager10> ListOfSeperationManager10s;
	//Pointer to selected PStep_SeparationManager
	PStep_SeparationManager* CurrentSeparationManager;

	//Initialization functions
//------------------------------------------------------------------------------------

	//Initialize the algorithm corresponding to an instance of the CVRP.
	//Initialize the branch-and-bound tree, i.e., the root node, arcs of the network and the algorithm settings.
	void Initialize(const CVRPInstance &NewInstance, const PStep_AlgorithmSettings &NewAlgorithmSettings);

	//Initialize arcs
	void InitializeArcs();

	//Initialize p-steps
	void InitializePSteps();

	//Add all return trips (0,i,0) to AlgorithmMembers.PSteps
	void AddAllReturnTrips();

	//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 to AlgorithmMembers.PSteps.
	//NOTE: in case the number of vehicles is fixed, we assume the number of customers
	//      is at least the number of vehicles.
	//		When no feasible initial routes are found, no p-steps are initialized.
	void AddGreedyInsertionRoutes();

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

	//Copy CustomerLocations to UpdatedCustomerLocations, while not copying the list
	//that are not reachable or are the source or sink of the current pricing problem.
	//The first customer is coded as 1.
	void RemoveUnreachableLocationsAndSourceAndSink(std::list<short int>& CustomerLocations, std::list<short int>& UpdatedCustomerLocations, PStep_PricingProblem& CurrentPP);

	//Given the CurrentPStep consisting of CurrentNumberOfArcs, extend it by greedy inserts
	//until it contains exactly TargetNumberOfArcs. If succesful, the output is true and 
	//the identified p-step is added to AlgorithmMembers.PSteps. Otherwise the output is false.
	//The pricing problem CurrentPP should correspond to the p-step. InsertionCosts[i][k][j]
	//should be the costs of inserting customer k in between location i and j, where 0 is the depot.
	//InsertableCustomers should contain all customer that might be inserted.
	//NOTE: It is assumed that the members starting load and total load of the current p-step only include
	//		the source demand and total demand respectively, such that the real starting load component
	//		is 0. This will be set accordingly by this function.
	bool GreedyInsertFillPStepAndAdd(PStep& CurrentPStep, short int& CurrentNumberOfArcs, short int TargetNumberOfArcs, PStep_PricingProblem& CurrentPP, double*** InsertionCosts, std::list<short int>& InsertableCustomers);

	//Initialize Neighbourhoods
	//NOTE: it is assumed that InArcs are sorted per location from cheap to expensive.
	void InitializeNeighbourhoods();

	//Determine the n closest neighbours of each customer with respect to a certain
	//distance matrix. The inward distance is considered.
	//It sets AlgorithmMembers.Neighbourhoods and AlgorithmMembers.NotInNeighbourhood.
	//The distances should be nonnegative.
	void GenerateNeighbourhoods(short int n, double **Distance);
	//The following version of GenerateNeighbourhoods, uses AlgorithmMembers.InArcs, 
	//under the assumption they are sorted.
	void GenerateNeighbourhoods(short int n);

	//Initialize the pricing problems
	void InitializePricingProblems();

	//Initialize PStep_Adders
	void InitializePStep_Adders();

	//Initialize PStep_PricingProblemSolvers
	void InitializePStep_PricingProblemSolvers();

	//Initialize PStep_ColumnGenerators
	void InitializePStep_ColumnGenerators();

	//Initialize PStep_ColumnManagers
	void InitializePStep_ColumnManagers();

	//Initialize PStep_SeparationAlgorithms
	void InitializePStep_SeparationAlgorithms();

	//Demand functions:
//------------------------------------------------------------------------------------

	//Compute the vehicle capacity minus the demand of the NumberOfInclusions first other customers
	//excluding all customers in the list of ExclusiveCustomers.
	//Customer 0 is the first customer.
	//The CustomerIndex is updated to refer to the next smallest candidate to be considered is returned.
	double ComputeCapacity(double Vehiclecapacity, double* DemandList, double* DemandCustomerList, short int NumberOfInclusions, std::vector<short int>& ExclusiveCustomers, short int NumberOfCustomers, short int& CustomerIndex);

	//Same as above, in case you don't care about CustomerIndex
	double ComputeCapacity(double Vehiclecapacity, double* DemandList, double* DemandCustomerList, short int NumberOfInclusions, std::vector<short int>& ExclusiveCustomers, short int NumberOfCustomers);


	//Solvers
//------------------------------------------------------------------------------------

public:
	//Solve the rootnode
	//This function initializes the algorithm and applies column generation to solve the
	//LP-relaxation of the p-step formulation.
	void SolveRootNode(const CVRPInstance &NewInstance, const PStep_AlgorithmSettings &NewAlgorithmSettings);

	//Solve the CVRP to integer optimality.
	//This function executes a branch-price-and-cut algorithm to solve the CVRP.
	//If an integer solution is found AlgorithmMembers.IntegerSolutionFound=true. In that case
	//the best integer solution can be found in AlgorithmMembers.BestIntegerSolution.
	//Statistics are stored in AlgorithmMembers.CurrentBPCStatistics.
	void BranchPriceAndCut(const CVRPInstance &NewInstance, const PStep_AlgorithmSettings &NewAlgorithmSettings);

private:
	//Column generation
	//Solve the LP relaxation of the problem corresponding to AlgorithmMembers.CurrentTreeNode.
	//New p-steps are added to AlgorithmMembers.PSteps, the solution is stored at
	//AlgorithmMembers.CurrentSolution and statistics are stored in AlgorithmMembers.CurrentCGStatistics.
	void ColumnGeneration();

	//p-step functions
//------------------------------------------------------------------------------------

	//Select all p-steps from AlgorithmMembers.PSteps that are feasible in the current node,
	//based on CurrentTreeNode->EdgeInUse, and put pointers to them into CurrentRoutes.
	//CurrentRoutes is emptied at the start of this function
	void SelectCurrentPSteps();

	//Check whether a p-pstep is feasible in the current node
	bool PStepIsFeasible(std::list<PStep>::iterator CurrentPStep);

	//Create an IloNumColumn representing a variable corresponding to a p-step.
	//It takes care of the values in the
	//-Objective
	//-CustomerAssignmentConstraints
	//-DegreeConstraints
	//-DemandFlowConstraints
	//-EdgeFlowConstraints
	//The resulting column is stored in Column.
	void CreatePStepColumn(PStep &CurrentPStep, IloObjective &Objective, IloRangeArray &CustomerAssignmentConstraints, IloRangeArray &DegreeConstraints, IloRangeArray &DemandFlowConstraints, IloRangeArray &EdgeFlowConstraints, IloNumColumn &Column);

	//Arc functions
//------------------------------------------------------------------------------------

	//Set available arcs.
	//This function updates the arc members of all relevant PricingProblems to reflect
	//which arcs are available in AlgorithmMembersCurrentTreeNode. In particular it updates
	//CurrentTreeNodeOutArcs, CurrentTreeNodeInArcs, CurrentTreeNodeArcIsRelevant,
	//and potentially CurrentTreeNodeLimitedOutArcs and CurrentTreeNodeLimitedInArcs.
	void SetAvailableArcs();

	//Filter arcs by EdgeInUse
	//It copies all InputArcs and stores them in OutputArcs, while filtering out all arcs
	//that are not in use as indicated by EdgeInUse.
	//EdgeInUse[(j-1)(j)/2+i] indicates whether edge (i,j), i<j, is still in use.
	void FilterArcsByEdgeInUse(std::list<std::list<PStep_Arc>>& InputArcs, std::list<std::list<PStep_Arc>>& OutputArcs, bool* (&EdgeInUse));

	//Filter ArcIsRelevant by EdgeInUse
	//It copies InputArcIsRelevant, where InputArcIsRelevant[i][j] indicates whether arc (i,j) is relevant,
	//and stores it in OutputArcs, while filtering out all arcs that are not in use as indicated by EdgeInUse.
	//EdgeInUse[(j-1)(j)/2+i] indicates whether edge (i,j), i<j, is still in use.
	void FilterArcIsRelevantByEdgeInUse(bool** (&InputArcIsRelevant), bool** &(OutputArcIsRelevant), bool* (&EdgeInUse));

	//Select first arcs
	//It selects up to the first AlgorithmMember.AlgorithmSettings.CG3NeighbourhoodSize from each list in InputArcs,
	//and copies them into OutputArcs
	void SelectFirstArcs(std::list<std::list<PStep_Arc>>& InputArcs, std::list<std::list<PStep_Arc>>& OutputArcs);

	//Cut functions
//------------------------------------------------------------------------------------

	//Create an IloExpr representing a cut.
	//The indices of EdgeFlowCut represent nodes.
	//The expression sums all edges between these nodes.
	//The IloNumVarArray theta is such that theta[(j-1)j/2+i] provides the edge flow on (i,j) for i<j.
	//The expression is stored in Cut.
	void CreateCutExpression_ByNodes(PStep_EdgeFlowCut &CurrentEdgeFlowCut, IloNumVarArray &theta, IloExpr &Cut);

	//Create an IloExpr representing a cut.
	//The indices of EdgeFlowCut are the indices of edges in the cut.
	//The expression sums all these edges.
	//The expression is stored in Cut.
	void CreateCutExpression_ByEdges(PStep_EdgeFlowCut &CurrentEdgeFlowCut, IloNumVarArray &theta, IloExpr &Cut);

	//Create an IloExpr representing a cut.
	//The indices of TwoEdgeHypotourCut are the indices of edges in the cut.
	//The expression sums all these edges multiplied with their corresponding coefficients.
	//The expression is stored in Cut.
	void CreateCutExpression_ByEdgesAndCoefficients(PStep_EdgeAndCoefficientCut &CurrentEdgeAndCoefficientCut, IloNumVarArray &theta, IloExpr &Cut);

	//Create branching cuts on the number of vehicles and add them to the TreeNode 
	void CreateFixedNumberOfVehiclesCut(PStep_TreeNode& TreeNode);

	//Branching functions
//------------------------------------------------------------------------------------

	//Delete AlgorithmMembers.CurrentTreeNode from AlgorithmMembers.Nodes, and reduce
	//AlgorithmMembers.CurrentNumberOfNodes by 1.
	//NOTE: be carefull, make sure that ALgorithmMembers.CurrentTreeNode refers to a node in AlgorithmMembers.Nodes.
	void DeleteCurrentTreeNode();

	//Find the lowest lower bound.
	//It is obtained by considering the ParentLB of each node in AlgorithmMembers.Nodes.
	//The lowest lower bound is returned.
	double FindLowestLB();

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

public:

	//Get the potential column generation time
	//It uses ListOfAllPricingProblemSequentialSolverSavingsTimers.front(0).TotalPotentialTimeSavings
	//as total savings.
	//It reports the total time taken by column generation minus these savings.
	//NOTE: It reports zero if AlgorithmSettings.PricingProblemSelection is not 2.
	double GetPotentialColumnGenerationTime();

	//Get the potential branch-price-and-cut generation time
	//It uses ListOfAllPricingProblemSequentialSolverSavingsTimers.front(0).TotalPotentialTimeSavings
	//as total savings.
	//It reports the total time taken by branch-price-and-cut minus these savings.
	//NOTE: It reports zero if AlgorithmSettings.PricingProblemSelection is not 2.
	double GetPotentialBranchPriceAndCutTime();

};

#endif