/*****************************************************************//**
 * \file   BranchAndPrice.h
 * \brief  The generic branch and price class.
 * 
 * \author talmefta
 * \date   May 2022
 *********************************************************************/
#ifndef BRANCHANDPRICE_H
#define BRANCHANDPRICE_H

#include "Header.h"
#include "Node.h"
#include "BranchingStrategy.h"
#include "SearchStrategy.h"
#include "BranchingRule.h"
#include "CutGenerator.h"
#include "RMPBaPObserver.h"

 /**
  * \class BranchAndPrice
  * \brief The backbone of the branch and price algorithm. 
  * Contains the while loop on the node list that solves the linear relaxation on each node with column generation.
  * \details This class is generic whatever are the restricted master problem, procing subproblem, column (and row) generation.
  */

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
class BranchAndPrice : public RMPBaPObserver {

protected:
	RestrictedMasterProblem*								  restricted_master_problem; /**< Pointer to the restricted master problem.*/
	PricingSubProblem*												 pricing_subproblem; /**< Pointer to the pricing sub-problem.*/
	ColumnGeneration*												  column_generation; /**< Pointer to the column_generation algorithm.*/
	list<Node<RestrictedMasterProblem, PricingSubProblem,
		ColumnGeneration, ConstraintType>>									  node_list; /**< The list containing the nodes to explore.*/
	Node<RestrictedMasterProblem, PricingSubProblem,
		ColumnGeneration, ConstraintType>*								   current_node; /**< The current node the algorithm is solving.*/
	Node<RestrictedMasterProblem, PricingSubProblem,
		ColumnGeneration, ConstraintType>*									  next_node; /**< The next node to explore depending on the search strategy.*/
	SearchStrategy<RestrictedMasterProblem, PricingSubProblem,
		ColumnGeneration, ConstraintType>*								search_strategy; /**< Searching algorithm.*/
	BranchingRule<RestrictedMasterProblem, PricingSubProblem,
		ColumnGeneration, ConstraintType>*							 branching_rule; /**< Branching algorithm.*/
	CutGenerator< RestrictedMasterProblem, PricingSubProblem,
		ColumnGeneration, ConstraintType>*								   cut_generator; /**< Cut strategy.*/
	double															   best_bound; /**< The best lower bound among all the nodes' lowers bounds.*/
	double															   best_incumbent_value; /**< The best lower bound among all the nodes' lowers bounds.*/
	double															   incumbent_value_after_root; /**< The best lower bound among all the nodes' lowers bounds.*/
	unordered_set<int> best_columns_int;
	list<Node<RestrictedMasterProblem, PricingSubProblem,
		ColumnGeneration, ConstraintType>>									   children; /**< The nodes generated after branching the current_node.*/

	int																  nb_explored_nodes;
	double																			gap;
	bool																 is_sol_integer;
	bool																 is_maximisation;			/**< Boolean to detect if is maximisation, by default is minimisation.*/
	bool																 is_objective_integer;			/**< Boolean to detect if is maximisation, by default is minimisation.*/
	int columns_counter_RM_heuristic;
	double dual_bound_root_before_cuts;
	double dual_bound_root_after_cuts;
	/**
	 * Branches the current_node into children depending on the branching strategy used and store them in children.
	 * 
	 */
	void branch();

	/**
	 * Cuts the current_node (builds and/ or lifts the appropriate cuts) depending on the cut strategy used and store them in children.
	 *
	 */
	bool cut();

	/**
	 * Solves the current node by the generation of new columns on the generation of new cuts till both generation sar not possible.
	 * 
	 * \param time_limit_column_generation
	 */
	void solve_current_node(const double time_limit_column_generation);

	/**
	 * Add children to the node_list depending on the search strategy and updates the next_node to explore if necessary always depending on the search strategy.
	 * 
	 */
	void add_children_nodes();


	/**
	 * Checks if the node list is empty.
	 * 
	 * \return true if node list is empty, false otherwise.
	 */
	bool is_node_list_empty() const;

	/**
	 * Checks if all the variables of the restricted master problem are binary.
	 *
	 * \return false if there is at least one fractional variable, true otherwise.
	 */
	bool are_all_variables_binary() const;

	/**
	 * Checks if the dual_bound in current_node is better than the stored best_incumbent_value.
	 * lower than the stored best_incumbent_value, in case of minimisation
	 * higher than the stored best_incumbent_value, in case of maximisation
	 * 
	 * \return true if the node has to be pruned, false otherwise.
	 */
	bool is_pruned_by_current_node_bound() const;

	/**
	 * Check if the current node is worthy to be processed, i.e., if it the dual_bound associated to it (the one of the parent) is 
	 * lower than the stored best_incumbent_value, in case of minimisation
	 * higher than the stored best_incumbent_value, in case of maximisation
	 *
	 * \return true if the node has to be pruned, false otherwise.
	 */
	bool is_pruned_by_parent_bound() const;

	/**
	 * Updates best_lower_bound with the lower bound of current_node.
	 *
	 */
	void update_best_bound();

	/**
	 * Updates best_upper_bound with the lower bound of current_node when the variables are integer.
	 *
	 */
	void update_best_incumbent_value();

	/**
	 * Set method of best_upper_bound.
	 * 
	 * \param new_upper_bound: double
	 */
	void set_best_incumbent_value(double new_incumbent_value);

	/**
	 * Updates gap.
	 *
	 */
	void update_gap();

	/**
	 * Removes the current_node from the node_list by removing it from the list front.
	 *
	 */
	void remove_current_node_from_node_list();

	/**
	 * Updates the current_node if node_list is non empty. 
	 * \details Adds the branching constraints of the current_node to the restricted master problem and removes the branching constraints of the restrcted master problem if we switch the branch of the tree.
	 * 
	 */
	void update_current_node();

	/**
	 * Prints the header of console output that is similar to Gurobi's output.
	 * 
	 */
	string print_header_output() const;

	/**
	 * Prints the row of console output representing the current_node, that is similar to Gurobi's output.
	 *
	 */
	string print_current_node_output() const;

public:
	/**
	 * Constructor with pointers to the restricted master problem, the pricing problem and to the column generation algorithm.
	 * \details Creates and initializes the current node with the root node.
	 * \param restricted_master_problem: RestrictedMasterProblem*
	 * \param pricing_subproblem: PricingSubProblem*
	 * \param column_generation: ColumnGeneration*
	 */
	BranchAndPrice(RestrictedMasterProblem* restricted_master_problem, PricingSubProblem* pricing_subproblem, ColumnGeneration* column_generation, bool isMaximisation = false, bool isObjectiveInteger = false);

	/**
	 * Destructor.
	 *
	 */
	~BranchAndPrice();

	/**
	* primal heuristic: restricted master heuristic
	*/
	void call_restricted_master_heuristic_new_MIP(const double& time_limit);

	/**
	 * Set method of branching_rule.
	 */
	void set_branching_rule(BranchingRule<RestrictedMasterProblem, PricingSubProblem,
		ColumnGeneration, ConstraintType>* new_branching_rule);

	/**
	 * Set method of search_strategy.
	 */
	void set_search_strategy(SearchStrategy<RestrictedMasterProblem, PricingSubProblem,
		ColumnGeneration, ConstraintType>* new_search_strategy);

	/**
	 * Set method of cut_strategy.
	 */
	void set_cut_generator(CutGenerator<RestrictedMasterProblem, PricingSubProblem,
		ColumnGeneration, ConstraintType>* new_cut_strategy);

	/**
	 * If a best bound is known a priori, set it
	 *
	 */
	void set_best_bound(const double& bb);

	/**
	 * Get method of best_lower_bound.
	 * 
	 * \return best_lower_bound: const double&
	 */
	const double& get_best_bound() const;
	const double& get_best_incumbent_value() const;
	const double& get_gap() const;
	const int& get_nb_explored_nodes() const;
	const int& get_nb_columns() const;
	const double& get_dual_bound_root_before_cuts() const;
	const double& get_dual_bound_root_after_cuts() const;
	const double& get_incumbent_value_after_root() const;
	const unordered_set<int>& get_best_columns_int() const;

	Json::Value to_json(const string& file_name, const int& id);

	/**
	 * The main loop of branch and price algorithm.
	 *
	 */
	void run(const double time_limit_branch_and_price, const double time_limit_column_generation);

	/**
	 * Displays the output of the algorithm.
	 * 
	 */
	void display() const;
	void sanity_check() const;
	void solution_print(const string& path_instance_name) const;
	void checker_solution_print(const string& path_instance_name) const;

	bool are_cuts_to_perform() {
		bool res = false;
		if (this->is_maximisation) {
			if (::strictly_less(this->best_incumbent_value, this->current_node->get_dual_bound())) {
				res = true;
			}
		}
		else {
			if (::strictly_greater(this->best_incumbent_value, this->current_node->get_dual_bound())) {
				res = true;
			}
		}
		return res;
	}

	void update_best_incumbent() override {

		this->best_incumbent_value = this->restricted_master_problem->get_objective_value_int();
		this->best_columns_int = this->restricted_master_problem->get_solution_columns_int();

	}

	void free_memory();

	/*void notify_best_incumbent_value() {
		this->cgObserver->update_best_incumbent_value(this->best_incumbent_value);
	}*/


};

#endif //BRANCHANDPRICE_H

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::BranchAndPrice(RestrictedMasterProblem* restricted_master_problem, PricingSubProblem* pricing_subproblem, ColumnGeneration* column_generation, bool isMaximisation, bool isObjectiveInteger) :
	restricted_master_problem(restricted_master_problem), pricing_subproblem(pricing_subproblem), column_generation(column_generation), current_node(nullptr), 
	is_maximisation(isMaximisation), is_objective_integer(isObjectiveInteger) {
	
	::global_id = 0;
	//best_lower_bound =  numeric_limits<double>::max();
	//best_upper_bound =  numeric_limits<double>::max();
	//create_root_node();
	this->dual_bound_root_after_cuts = -1.0;
	this->dual_bound_root_before_cuts = -1.0;
	this->incumbent_value_after_root = -1.0;
	set_best_incumbent_value(restricted_master_problem->get_objective_value());
	/*set_best_solution(restricted_master_problem->get_solution());
	set_best_columns(restricted_master_problem->get_columns());*/
	this->node_list.push_back(Node<RestrictedMasterProblem, PricingSubProblem,
		ColumnGeneration, ConstraintType>(restricted_master_problem, pricing_subproblem, column_generation, this->best_incumbent_value));
	if (this->is_maximisation) {
		this->node_list.begin()->set_parent_bound(::OMEGA);
	}
	else {
		this->node_list.begin()->set_parent_bound(-::OMEGA);
	}
	if (this->is_maximisation) {
		this->best_bound = ::OMEGA;
	}
	else {
		this->best_bound = -::OMEGA;
	}
	this->gap = 1e15;
	this->columns_counter_RM_heuristic = 0;
	//update_gap();
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::~BranchAndPrice() {
}


template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline void BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::branch() {
	this->children = branching_rule->branch(*this->current_node);
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline bool BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::cut() {
	return this->cut_generator->cut(*this->current_node);
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline void BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::solve_current_node(const double time_limit_column_generation) {
	//Normally, we solve with column generation untill no column with negative reduced cost is found
	//Then, we generate all the cuts untill no violated cut is found
	//And we loop on this till no favorably priced columns neither new violated cuts are generated
	clock_t start = clock();
	clock_t end = clock();
	int iterationCuts = 0;
	this->cut_generator->reset_found_inequality();
	double duration = (float)(end - start) / CLOCKS_PER_SEC;
	do {

		this->current_node->solve(time_limit_column_generation, this->is_maximisation, this->is_objective_integer, this->best_incumbent_value);
		end = clock();
		duration = (float)(end - start) / CLOCKS_PER_SEC;

		if (this->current_node->get_id() == 0) {
			//store dual bound before cuts
			if (this->dual_bound_root_before_cuts < -::EPSILON) {
				this->dual_bound_root_before_cuts = this->current_node->get_dual_bound();
				//cout << "DB " << this->dual_bound_root_before_cuts << endl;
			}

			//run primal heuristic
			if (iterationCuts == 0) {
				//cout << "MIP bef " << this->best_incumbent_value << "\t" << this->restricted_master_problem->get_columns().size()<<"\n";
				call_restricted_master_heuristic_new_MIP(60.0);
				this->current_node->set_best_integer_value(this->best_incumbent_value);
				//cout << "MIP aft " << this->best_incumbent_value << endl;
			}

		}

		bool is_cg_time_consuming = (this->current_node->get_column_generation_time_spent() > time_limit_column_generation);
		if (!are_cuts_to_perform() || is_cg_time_consuming) {
			break;
		}

		iterationCuts++;

		//this->current_node->get_restricted_master_problem()->export_model();
	} while (cut());

	if (this->current_node->get_id() == 0) {
		if (this->dual_bound_root_after_cuts < -::EPSILON) {
			this->dual_bound_root_after_cuts = this->current_node->get_dual_bound();
		}
		if (this->incumbent_value_after_root < -::EPSILON) {
			this->incumbent_value_after_root = this->best_incumbent_value;
		}
	}
	
	/*current_node->solve(time_limit_column_generation);
	do {
		restricted_master_problem->solve();
	} while (cut());*/

	/*for (auto cut : restricted_master_problem->get_cut_constraints())
		cout << *cut << endl;*/
	
	this->restricted_master_problem->notify_nodes_for_ineffective_cuts();
	this->current_node->set_total_time_spent(this->current_node->get_column_generation_time_spent() + this->current_node->get_cut_generation_time_spent());
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline void BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::add_children_nodes() {
	typename list<Node<RestrictedMasterProblem, PricingSubProblem,
		ColumnGeneration, ConstraintType>>::iterator child;
	for (child = this->children.begin(); child != this->children.end(); child++) {
		this->search_strategy->add_node(this->node_list, *child);
	}
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline void BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::run(const double time_limit_branch_and_price, const double time_limit_column_generation) {
	string header = print_header_output();
	cout << header;
	::appendToFile(::instanceName + "_console.txt", header);
	clock_t start = clock();
	clock_t end = clock();
	double duration = (float)(end - start) / CLOCKS_PER_SEC;
	bool first_time = true;

	//attach observer to RMP
	this->restricted_master_problem->attach(this);

	while (!is_node_list_empty() && duration < time_limit_branch_and_price) {
		update_current_node();
		remove_current_node_from_node_list();

		/*if (this->current_node->get_id() == 1074 || this->current_node->get_id() == 1945) {
			::isToPrint = true;
			
		}
		else {
			::isToPrint = false;
		}*/

		//this->restricted_master_problem->export_model(this->current_node->get_id());

		//cout << "PARENT BOUND \t" << this->current_node->get_parent_bound() << "\n";

		if (is_pruned_by_parent_bound()) { //CHANGE
			cout << "Pruned by suboptimality1" << endl;
			this->node_list.clear();
			update_best_bound();
			update_gap();
			end = clock();
			duration = (float)(end - start) / CLOCKS_PER_SEC;
			return;
		}
		else {
			/*if (restricted_master_problem->detect_conflicting_branching_rules())
				;
			else*/
			{
				/*if (restricted_master_problem->detect_conflicting_branching_rules())
					cout << "Infeasibility Detected " << endl;*/
				/*if (this->current_node->get_id() == 12) {
					::isToPrint = true;
					cout << "STOP\n";
				}
				else {
					::isToPrint = false;
				}*/

				/*::appendToFile("branching.log", "NODE " + to_string(this->current_node->get_id()) + "\tPARENT NODE " + to_string(this->current_node->get_parent_id())+"\n");
				for (int j = 0; j < this->current_node->get_branching_constraints().size(); j++) {
					const ArcBranchConstraint<GRBConstr>* ssi = dynamic_cast<ArcBranchConstraint<GRBConstr>*>(this->current_node->get_branching_constraints().at(j));
					::appendToFile("branching.log", "\t" + ssi->toString());
				}
				::appendToFile("branching.log", "\n\n\n");*/
				//Compute allowed time for CG as the min of the time given as input and the remaining time for the BPC
				clock_t end_cg = clock();
				double duration_cg = (float)(end_cg - start) / CLOCKS_PER_SEC;
				double time_limit_cg = min(time_limit_column_generation, abs(time_limit_branch_and_price - duration_cg));
				solve_current_node(time_limit_cg);

				/*if (::isToPrint) {
					this->restricted_master_problem->export_model(this->current_node->get_id() + 1);
					::appendToFile("fileCheck.log", "NODE FINISHED\n\n\n");
					this->restricted_master_problem->write_solution_value_into_text(this->current_node->get_id());
				}*/

				//this->restricted_master_problem->write_solution_value_into_text(this->current_node->get_id());

				/*if (::isToPrint) {
					this->restricted_master_problem->export_model(this->current_node->get_id());
					
					if (!this->restricted_master_problem->check_solution()) {
						cout << "wrong solf\n";
					}
				}*/
				//this->restricted_master_problem->export_model(this->current_node->get_id());
				this->restricted_master_problem->remove_branching_constraints();
				/*if (!this->restricted_master_problem->check_opt_sol_violation()) {
					cout << "stop\n";
				}*/
				bool isError = false;
				if (this->is_maximisation) {
					isError = ::strictly_greater(this->current_node->get_dual_bound(), this->current_node->get_parent_bound());
				}
				else {
					isError = ::strictly_less(this->current_node->get_dual_bound(), this->current_node->get_parent_bound());
				}
				if (isError) {
					string streamName = ::solutionPath + "ERRORS_Solutions.txt";
					ofstream mystream;
					mystream.open(streamName, ios::app);
					mystream << ::instanceName << "\t" << this->is_maximisation << endl;
					mystream << "CHILD " << this->current_node->get_id() << " PARENT " << this->current_node->get_parent_id() << endl;
					mystream << "DB " << this->current_node->get_dual_bound() << " PARENT " << this->current_node->get_parent_bound() << endl;
					mystream << "\n\n\n";
					mystream.close();
				}
				
				//Pay attention here to be sure that infeasibility come only from the branching constraints 
				//and not ONLY BECAUSE we do not have enough columns to satisfy the branching constraints
				//The infeasibility information has to come after column generation where even with artificial variable
				//the model can not satisfy the branching constraints
				if (this->current_node->is_infeasible() || this->restricted_master_problem->is_infeasible_dummy_variable()) {
					cout << "Pruned by infeasibility" << endl;
					/*			for (auto& branching : restricted_master_problem->get_branching_constraints())
									cout << *dynamic_cast<RyanFosterConstraint<GRBConstr>*>(branching) << endl;*/
				}
				else {
					if (is_pruned_by_current_node_bound()) {
						cout << "Pruned by suboptimality2" << endl;
					}
					else {
						if (this->is_sol_integer = are_all_variables_binary()) {
							//cout << "variables are integer\t" << current_node->get_rmp_value() << "\n";
							this->restricted_master_problem->update_integer_solution();
							update_best_incumbent();
							//cout << "updated " << this->best_incumbent_value << endl;

							//notify_best_incumbent_value();
							//this->mip_value = this->restricted_master_problem->get_objective_value();
						}
						else {
							branch();
							add_children_nodes();

							//int currentColumnsNumber = this->restricted_master_problem->get_columns().size();
							//if (this->current_node->get_id() != 0 && abs(currentColumnsNumber - this->columns_counter_RM_heuristic) >= ::MIN_COLUMNS_FOR_RM_HEURISTIC) {
							//	call_restricted_master_heuristic_new_MIP(60.0);					//MUST BE DONE AFTER THE BRANCHING STRATEGIES ARE DETECTED
							//}

						}
					}
				}
			}
		}
		//TO DO
		update_best_bound();//best parent's lower bounds //best_lower_bound is the worst lower bound we can have at the end of the algorithm
		update_gap();
		this->nb_explored_nodes++;
		string node_output = print_current_node_output();
		cout << node_output;
		::appendToFile(::instanceName + "_console.txt", node_output);
		//print_current_node_output();
		end = clock();
		duration = (float)(end - start) / CLOCKS_PER_SEC;

		//add if for example a best_bound is known a priopri and given, it could be better to assign such boud to the root node but need time to fix everything
		if (this->gap < ::EPSILON) {
			break;
		}

		if (duration >= time_limit_branch_and_price) {
			::LB_before_final_MIP = this->best_incumbent_value;
			call_restricted_master_heuristic_new_MIP(1800.0);
			update_gap();
		}

		//break;
	}


	/*::LB_before_final_MIP = this->best_incumbent_value;
	call_restricted_master_heuristic_new_MIP(60.0);
	update_gap();*/
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline void BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::display() const {
	cout << this->restricted_master_problem->to_string_integer_solution() << "\n";
}



template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline void BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::sanity_check() const {
	this->restricted_master_problem->sanity_check_integer_solution();
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline void BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::checker_solution_print(const string& path_instance_name) const {
	ofstream mystream;
	mystream.open(path_instance_name, ios::trunc);
	mystream << this->best_incumbent_value << "\n";
	for (const auto& col_id : this->best_columns_int) {
		for (int k = 1; k < this->restricted_master_problem->get_columns().at(col_id).getSequence().size(); k++) {
			mystream << this->restricted_master_problem->get_columns().at(col_id).getSequence().at(k) << "\t";
		}
		mystream << "\n";
	}
	mystream.close();
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline void BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::solution_print(const string& path_instance_name) const {

	ofstream mystream;
	mystream.open(path_instance_name, ios::trunc);
	mystream << this->best_incumbent_value << "\n";
	double rec_val = 0.0;
	for (const auto& col_id : this->best_columns_int) {
		mystream << this->restricted_master_problem->get_columns().at(col_id).toString() << "\n";
		rec_val += this->restricted_master_problem->get_columns().at(col_id).getWeight();
	}
	mystream << rec_val << "\n";
	mystream.close();

}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline void BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::free_memory() {
	//for (auto& node : node_list)
	//{
	//	for (auto& constraint : node.get_branching_constraints())
	//	{
	//		delete constraint->get_real_constraint();
	//		delete constraint;
	//		constraint = nullptr;
	//	}

	//	for (auto& constraint : node.get_cut_constraints())
	//	{
	//		delete constraint->get_real_constraint();
	//		delete constraint;
	//		constraint = nullptr;
	//	}
	//}
	/*if (current_node)
	{
		for (auto& constraint : current_node->get_branching_constraints())
		{
			delete constraint->get_real_constraint();
			delete constraint;
		}

		for (auto& constraint : current_node->get_cut_constraints())
		{
			delete constraint->get_real_constraint();
			delete constraint;
		}
		delete current_node;
	}*/
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline bool BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::is_node_list_empty() const {
	return this->node_list.empty();
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline bool BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::are_all_variables_binary() const {
	//TO DO
	return this->restricted_master_problem->are_all_variables_binary();
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline bool BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::is_pruned_by_current_node_bound() const {
	if (this->is_maximisation) {
		return ::less(this->current_node->get_dual_bound(), this->best_incumbent_value);
	}
	return ::greater(this->current_node->get_dual_bound(), this->best_incumbent_value); //CHANGE
	//return current_node->get_lower_bound() <= best_upper_bound;
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline bool BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::is_pruned_by_parent_bound() const {
	if (this->is_maximisation) {
		return ::less(this->current_node->get_parent_bound(), this->best_incumbent_value);
	}
	return ::greater(this->current_node->get_parent_bound(), this->best_incumbent_value); //CHANGE
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline void BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::update_best_bound() {
	//cout << this->current_node->get_dual_bound() << " " << this->node_list.front().get_parent_bound() << "\n";
	if (this->node_list.empty()) {
		this->best_bound = this->best_incumbent_value;
	}
	else {
		if (this->is_maximisation) {
			this->best_bound = min(this->best_bound, this->node_list.front().get_parent_bound());
		}
		else {
			this->best_bound = max(this->best_bound, this->node_list.front().get_parent_bound());
		}
	}
	//if (this->current_node->get_id() == 0)
	//	this->best_bound = this->current_node->get_dual_bound(); //CHANGE
	////else if (is_node_list_empty())
	////	best_lower_bound = best_upper_bound;
	//else if (!this->node_list.empty())
	//	this->best_bound = this->node_list.front().get_parent_bound();
	//else
	//	this->best_bound = this->best_incumbent_value;
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline void BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::set_best_bound(const double& bb) {
	this->best_bound = bb;
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline void BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::update_best_incumbent_value() {
	this->best_incumbent_value = current_node->get_rmp_value();
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline void BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::set_best_incumbent_value(double new_incumbent_value) {
	this->best_incumbent_value = new_incumbent_value;
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline void BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::update_gap() {
	double diff = fabs(this->best_incumbent_value - this->best_bound);
	if (diff < EPSILON) {
		this->gap = 0.0;
	}
	else if (this->best_incumbent_value != 0) {
		if (this->is_maximisation) {
			this->gap = (diff / this->best_bound) * 100;
		}
		else {
			this->gap = (diff / this->best_incumbent_value) * 100;
		}
	}
	else {
		this->gap = 1e15/*numeric_limits<double>::max()*/;
	}
		
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline void BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::remove_current_node_from_node_list() {
	this->node_list.front().remove_me_from_the_list_observers();
	this->node_list.pop_front();
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline void BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::update_current_node() {
	if (this->current_node) {
		this->current_node->remove_me_from_the_list_observers();
		delete this->current_node;
	}
	this->current_node = new Node<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType>(this->node_list.front());
	this->current_node->add_me_to_the_list_observers();
	/*if (!this->restricted_master_problem->get_branching_constraints().empty())
		this->restricted_master_problem->remove_branching_constraints();*/

	if (!this->current_node->get_branching_constraints().empty())
		this->restricted_master_problem->add_branching_constraints(this->current_node->get_branching_constraints());
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline string BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::print_header_output() const {

	stringstream mystream;
	mystream << setw(18) << "Nodes | ";
	mystream << setw(45) << "Current Node | ";
	mystream << setw(30) << "Objective Bounds | ";
	mystream << setw(30) << "Work" << endl;

	mystream << setw(8) << "Expl";
	mystream << setw(8) << " Unexpl |";
	mystream << setw(8) << " Id ";
	mystream << setw(8) << " Dual bound ";
	mystream << setw(8) << " Obj ";
	mystream << setw(8) << "Depth";
	mystream << setw(8) << " IntInf |";

	mystream << setw(10) << "Incumbent ";
	mystream << setw(10) << "BestBd";
	mystream << setw(10) << "Gap |";

	mystream << setw(10) << "#Columns ";
	mystream << setw(10) << "#Cuts  ";
	mystream << setw(13) << "ColGenTime";
	mystream << setw(13) << "CutGenTime";
	mystream << setw(13) << "TotalTime" << endl;
	return mystream.str();

}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline string BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::print_current_node_output() const {
	
	stringstream mystream;
	mystream << setw(6) << this->nb_explored_nodes;
	mystream << setw(10) << this->node_list.size();
	mystream << setw(8) << this->current_node->get_id();
	mystream << setw(10) << setprecision(6) << this->current_node->get_dual_bound();
	mystream << setw(10) << setprecision(6) << this->current_node->get_rmp_value();
	mystream << setw(6) << this->current_node->get_depth();
	mystream << setw(8) << "-";

	mystream << setw(10) << this->best_incumbent_value;
	mystream << setw(10) << this->best_bound;
	mystream << setw(10) << setprecision(3) << this->gap;

	mystream << setw(10) << this->current_node->get_nb_columns_added();
	mystream << setw(10) << this->current_node->get_nb_cuts_added();
	mystream << setw(13) << setprecision(2) << this->current_node->get_column_generation_time_spent();
	mystream << setw(13) << setprecision(2) << this->current_node->get_cut_generation_time_spent();
	mystream << setw(13) << setprecision(2) << this->current_node->get_total_time_spent() << endl;
	return mystream.str();

}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline void BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::call_restricted_master_heuristic_new_MIP(const double& time_limit) {

	this->restricted_master_problem->call_restricted_master_heuristic_new_MIP(time_limit, this->best_columns_int);

	this->columns_counter_RM_heuristic = this->restricted_master_problem->get_columns().size();

	update_best_incumbent();
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline void BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::set_branching_rule(BranchingRule<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType>* new_branching_rule) {
	this->branching_rule = new_branching_rule;
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline void BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::set_search_strategy(SearchStrategy<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType>* new_search_strategy) {
	this->search_strategy = new_search_strategy;
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline void BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::set_cut_generator(CutGenerator<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType>* new_cut_generator) {
	this->cut_generator = new_cut_generator;
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline const double& BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::get_best_bound() const {
	return this->best_bound;
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline const double& BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::get_best_incumbent_value() const {
	return this->best_incumbent_value;
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline const double& BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::get_gap() const {
	return this->gap;
}


template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline const int& BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::get_nb_explored_nodes() const {
	return this->nb_explored_nodes;
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline const int& BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::get_nb_columns() const {
	return this->restricted_master_problem->get_number_columns();
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline const double& BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::get_dual_bound_root_before_cuts() const {
	return this->dual_bound_root_before_cuts;
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline const double& BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::get_dual_bound_root_after_cuts() const {
	return this->dual_bound_root_after_cuts;
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline const double& BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::get_incumbent_value_after_root() const {
	return this->incumbent_value_after_root;
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>
inline const unordered_set<int>& BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::get_best_columns_int() const {
	return this->best_columns_int;
}

template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType, class ColumnsType>

Json::Value BranchAndPrice<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType, ColumnsType>::to_json(const string& file_name, const int& id) {
	Json::Value instance;
	instance["L"] = this->restricted_master_problem->get_instance().get_maximum_size_of_group();
	instance["summary"]["numberColumns"] = this->current_node->get_nb_columns_added();
	instance["summary"]["numberCuts"] = this->current_node->get_nb_cuts_added();
	instance["summary"]["lowerBound"] = this->current_node->get_bound();
	instance["summary"]["upperBound"] = this->best_incumbent_value;
	instance["summary"]["finalGap"]   = this->gap;
	instance["summary"]["initialGap"] = this->gap;
	instance["summary"]["solInteger"] = this->is_sol_integer;
	instance["summary"]["timeColGen"] = this->current_node->get_column_generation_time_spent();
	instance["summary"]["timeCutGen"] = this->current_node->get_cut_generation_time_spent();
	instance["summary"]["totalTime"]  = this->current_node->get_total_time_spent();
	instance["summary"]["initialSolValue"]  = this->restricted_master_problem->get_initial_solution_value();
	instance["summary"]["mip_Value"]  = this->mip_value;

	auto cutter = this->cut_generator;
	while (cutter != nullptr) {
		Json::Value iterations(Json::arrayValue);
		for (auto& cut_family_info : cutter->get_information()) {
			if (cut_family_info->get_cut_iteration() == 1) {
				if (this->restricted_master_problem->get_initial_solution_value() != 0) {
					double initialGap = fabs((this->restricted_master_problem->get_initial_solution_value() - cut_family_info->get_bound_before_adding_cuts()) / this->restricted_master_problem->get_initial_solution_value()) * 100;
					instance["summary"]["initialGap"] = initialGap;
				}
			}

			Json::Value iteration(Json::objectValue);
			Json::Value information(Json::arrayValue);
			information.append(Json::Value(cut_family_info->get_name_cutter()));
			information.append(Json::Value(cut_family_info->get_cut_iteration()));
			information.append(Json::Value(cut_family_info->get_number_violated_cuts()));
			information.append(Json::Value(round_to_three_point(cut_family_info->get_time())));
			information.append(Json::Value(cut_family_info->get_minimum_violation()));
			information.append(Json::Value(cut_family_info->get_maximum_violation()));
			information.append(Json::Value(cut_family_info->get_is_solution_integer_after_adding_cuts()));
			information.append(Json::Value(cut_family_info->get_bound_before_adding_cuts()));
			information.append(Json::Value(cut_family_info->get_bound_after_adding_cuts()));
			information.append(Json::Value(round_to_three_point(cut_family_info->get_solving_rmp_time())));
			information.append(Json::Value(cut_family_info->get_number_columns_before_adding_cuts()));
			information.append(Json::Value(cut_family_info->get_number_columns_after_adding_cuts()));

			vector<string> my_keys;
			my_keys.push_back("name");
			my_keys.push_back("cutIteration");
			my_keys.push_back("numberCuts");
			my_keys.push_back("time");
			my_keys.push_back("minViolation");
			my_keys.push_back("maxViolation");
			my_keys.push_back("solInteger");
			my_keys.push_back("boundBefore");
			my_keys.push_back("boundAfter");
			my_keys.push_back("solvingRmpTime");
			my_keys.push_back("numberColumnsBefore");
			my_keys.push_back("numberColumnsAfter");

			for (int i = 0; i < my_keys.size(); i++) {
				iteration[my_keys[i]] = information[i];
			}
			instance["CutGenDetails"].append(iteration);
		}
		cutter = cutter->get_next_cutter();
	}

	//ColGenIterations
	vector<vector<ColGenIterationInfo>> col_gen_iteration_info = column_generation->get_col_gen_interation_info();
	for (auto& col_gen_round : col_gen_iteration_info) {
		Json::Value iterations(Json::arrayValue);
		for (auto& col_gen_iter :col_gen_round) {
			Json::Value iteration(Json::objectValue);
			Json::Value information(Json::arrayValue);
			information.append(Json::Value(col_gen_iter.get_col_gen_iteration()));
			information.append(Json::Value(col_gen_iter.get_name_psp_algorithm()));
			information.append(Json::Value(col_gen_iter.get_bound_before()));
			information.append(Json::Value(col_gen_iter.get_bound_after()));
			information.append(Json::Value(col_gen_iter.get_total_time()));
			information.append(Json::Value(col_gen_iter.get_solving_rmp_time()));
			information.append(Json::Value(col_gen_iter.get_solving_psp_time()));
			information.append(Json::Value(col_gen_iter.get_is_solution_integer_before()));
			information.append(Json::Value(col_gen_iter.get_is_solution_integer_after()));
			information.append(Json::Value(col_gen_iter.get_number_columns_before()));
			information.append(Json::Value(col_gen_iter.get_number_columns_added()));

			vector<string> my_keys;
			my_keys.push_back("colGenIteration");
			my_keys.push_back("pspName");
			my_keys.push_back("boundBefore");
			my_keys.push_back("boundAfter");
			my_keys.push_back("totalTime");
			my_keys.push_back("solvingRmpTime");
			my_keys.push_back("solvingPspTime");
			my_keys.push_back("solIntegerBefore");
			my_keys.push_back("solIntegerAfter");
			my_keys.push_back("numberColumnsBefore");
			my_keys.push_back("numberColumnsAdded");

			for (int i = 0; i < my_keys.size(); i++) {
				iteration[my_keys[i]] = information[i];
			}
			instance["ColGenDetails"].append(iteration);
		}
	}


	cout << instance << endl;
	/*std::ofstream file_id;
	file_id.open(file_name, ios::app);


	Json::StyledWriter styledWriter;
	file_id << styledWriter.write(instance);

	file_id.close();*/
	return instance;
}


