/*****************************************************************//**
 * \file   ColumnGeneration.h
 * \brief  The column (and row) generation algorithm.
 * 
 * \author talmefta
 * \date   May 2022
 *********************************************************************/
#ifndef COLUMNGENERATION_H
#define COLUMNGENERATION_H

#include "Header.h"
#include "ColGenIterationInfo.h"
/**
 * \class ColumnGeneration.
 * \brief The column (and row) generation algorithm. Contains the main loop of solving the restricted master problem and pricing subproblem until no negative reduced cost columns are found.
 */

template<class RestrictedMasterProblem, class PricingSubProblem>
class ColumnGeneration {

protected:
	RestrictedMasterProblem*	  restricted_master_problem; /**< Pointer to the restricted master problem.*/
	PricingSubProblem*					 pricing_subproblem; /**< Pointer to the pricing sub-problem.*/
	double										dual_bound;										 /**< COMPUTE DUAL BOUND.*/
	int									      nb_iterations; /**< Number of iterations the column generation did to solve the restricted master problem.*/
	int									   nb_columns_found; /**< Number of iterations the column generation did to solve the restricted master problem.*/
	double								  		 time_spent; /**< Time spent for the procedure.*/
	vector<vector<ColGenIterationInfo>>	col_gen_iterations_info;

public:
	/**
	 * Constructor with pointers to the restricted master problem and to the pricing problem.
	 * \param restricted_master_problem: RestrictedMasterProblem*
	 * \param pricing_subproblem: PricingSubProblem*
	 */
	ColumnGeneration(RestrictedMasterProblem* restricted_master_problem, PricingSubProblem* pricing_subproblem) :
		restricted_master_problem(restricted_master_problem), pricing_subproblem(pricing_subproblem), nb_iterations(), time_spent() {
	}

	/**
	 * Destructor.
	 * 
	 */
	~ColumnGeneration() {
	}

	/**
	 * The main loop of column generation that solves iteratively the restricted master problem, gets the dual variables, solves the pricing subproblem, and nurtures the restricted master problem with new columns when found.
	 * 
	 * \param max_time: double
	 */
	void run(const double max_time, const bool& isMaximisation, const bool& is_objective_integer, const double& best_incumbent_value) {
		bool finish = false;
		int iter = 0;
		clock_t start = clock();
		clock_t end = clock();
		double duration = (float)(end - start) / CLOCKS_PER_SEC;
		bool is_to_stop = false;

		/*if (isMaximisation) {
			this->dual_bound = ::OMEGA;
		}
		else {
			this->dual_bound = -::OMEGA;
		}*/
		//cout << "DUAL BOUND " << this->dual_bound << endl;

		this->nb_columns_found = 0;
		this->col_gen_iterations_info.push_back(vector<ColGenIterationInfo>());
		try {
			do {
				this->restricted_master_problem->solve();
				this->restricted_master_problem->increment_solving_rmp_iteration();
				/*if (iter == 62) {
					cout << "stp\n";
				}*/
				if (!this->col_gen_iterations_info.empty() && !this->col_gen_iterations_info.back().empty()) {
					this->col_gen_iterations_info.back().back().set_rmp_value(this->restricted_master_problem->get_objective_value());
					this->col_gen_iterations_info.back().back().set_is_solution_integer_after(this->restricted_master_problem->are_all_variables_binary());
				}
				this->col_gen_iterations_info.back().push_back(ColGenIterationInfo());
				this->col_gen_iterations_info.back().back().set_col_gen_iteration(this->restricted_master_problem->get_solving_rmp_iteration());
				this->col_gen_iterations_info.back().back().set_rmp_value(::rounderToNDecimals(this->restricted_master_problem->get_objective_value(), 10));
				this->col_gen_iterations_info.back().back().set_solving_rmp_time(::rounderToNDecimals(this->restricted_master_problem->get_solving_time(), 3));
				this->col_gen_iterations_info.back().back().set_number_columns_before(this->restricted_master_problem->get_columns().size());
				this->col_gen_iterations_info.back().back().set_is_solution_integer_before(this->restricted_master_problem->are_all_variables_binary());

				bool is_rmp_to_be_called = false;
				bool is_RMP_solution_integer = false;
				if (!this->restricted_master_problem->is_infeasible()) {
					this->restricted_master_problem->extract_solution_value();
					this->restricted_master_problem->extract_dual_solution_value();
					is_RMP_solution_integer = this->restricted_master_problem->are_all_variables_binary();
					
					if (is_RMP_solution_integer) {
						this->restricted_master_problem->update_integer_solution();
						this->restricted_master_problem->notify_BaP_for_new_incumbent();
					}
					this->restricted_master_problem->notify_mediator();
					this->restricted_master_problem->update_ineffective_cuts();
					this->pricing_subproblem->solve(max_time);
					this->nb_columns_found += static_cast<int>(this->pricing_subproblem->get_columns().size());
					this->restricted_master_problem->set_number_new_columns(static_cast<int>(this->pricing_subproblem->get_columns().size()));
					this->restricted_master_problem->notify_cut_information_observer();
					if (this->pricing_subproblem->is_algorithm_exact() && !this->pricing_subproblem->get_is_early_terminated()) {
						update_dual_bound(isMaximisation, is_objective_integer);
					}
					if (this->pricing_subproblem->at_least_one_favorably_priced_column_exists()) {
						this->pricing_subproblem->notify_mediator();
					}
					else
						finish = true;

					if (is_dual_bound_termination_condition_hit(isMaximisation, is_objective_integer, best_incumbent_value)) {
						//double tot = this->restricted_master_problem->get_objective_value() + ::EPSILON;
						/*cout << "DB " << setprecision(9) << this->dual_bound << " RMP " << setprecision(9) << this->restricted_master_problem->get_objective_value() <<
							" FLOOR " << setprecision(9) << floor(tot) << "\n";*/
						is_rmp_to_be_called = !finish;
						finish = true;
					}
					this->col_gen_iterations_info.back().back().set_dual_bound(::rounderToNDecimals(this->dual_bound, 10));
					this->col_gen_iterations_info.back().back().set_number_columns_added(static_cast<int>(this->pricing_subproblem->get_columns().size()));
					this->col_gen_iterations_info.back().back().set_name_psp_algorithm(this->pricing_subproblem->get_name_algorithm());
					this->col_gen_iterations_info.back().back().set_solving_psp_time(::rounderToNDecimals(this->pricing_subproblem->get_time_spent(), 3));
					this->col_gen_iterations_info.back().back().set_total_time(::rounderToNDecimals(this->restricted_master_problem->get_solving_time() + this->pricing_subproblem->get_time_spent(), 3));
				}
				else
					finish = true;

				iter++;

				
				//if (true) {
				//	/*string check;
				//	check.append("RMP: " +  to_string(this->restricted_master_problem->get_objective_value())+ "\t" + to_string(this->pricing_subproblem->get_value()) + "\t" + to_string(this->pricing_subproblem->get_columns().size())
				//		+ "\t" + to_string(this->restricted_master_problem->getUpperBoundExchanges()) + "\t" + to_string(this->dual_bound) +"\n");
				//	check.append("COL " + to_string(this->restricted_master_problem->get_solution().size()) + "\t" + to_string(this->restricted_master_problem->get_columns().size()) + "\n");
				//	check.append("IS SOLUTION INTEGER?? " + to_string(this->restricted_master_problem->are_all_variables_binary()) + "\n");
				//	check.append("ITERATIONS " + to_string(iter)+ "\n\n");
				//	::appendToFile("fileCheck.log", check);*/
				//	cout << "RMP: " << setprecision(9) << this->restricted_master_problem->get_objective_value() << setprecision(9) << "\t" << this->pricing_subproblem->get_value() 
				//		<< "\t" << this->pricing_subproblem->is_algorithm_exact() << "\t" << this->pricing_subproblem->get_is_early_terminated()
				//		<< "\t" << this->pricing_subproblem->get_columns().size() << "\t" << setprecision(9) << this->restricted_master_problem->getUpperBoundExchanges() 
				//		<< "\t" << setprecision(9) << this->dual_bound << endl;
				//	cout << "COL " << this->restricted_master_problem->get_solution().size() << "\t" << this->restricted_master_problem->get_columns().size() << endl;
				//	cout << "IS SOLUTION INTEGER?? " << this->restricted_master_problem->are_all_variables_binary() << "\n";
				//	cout << "ITERATIONS " << iter << "\n\n";
				//	//this->restricted_master_problem->write_solution_value();
				//	
				//	this->restricted_master_problem->export_model(-1);				
				//}
				
				end = clock();
				duration = (float)(end - start) / CLOCKS_PER_SEC;
				//If the column generation has not finished but the time has finished then we need to solve the restricted master problem for a last time
				//to have the solution value of the new inserted column, otherwise, there will be solution.size() < columns.size().
				if (is_rmp_to_be_called || (duration >= max_time)) {
					this->restricted_master_problem->solve();
					this->restricted_master_problem->extract_solution_value();
					this->restricted_master_problem->extract_dual_solution_value();
					//cout << "CALLED AGAIN " << setprecision(9) << this->restricted_master_problem->get_objective_value() << endl;
					end = clock();
					duration = (float)(end - start) / CLOCKS_PER_SEC;
				}
				is_to_stop = (duration >= max_time && !is_RMP_solution_integer);
			} while (!finish && !is_to_stop);
			if (!this->col_gen_iterations_info.empty() && !this->col_gen_iterations_info.back().empty()) {
				this->col_gen_iterations_info.back().back().set_rmp_value(this->restricted_master_problem->get_objective_value());
				this->col_gen_iterations_info.back().back().set_is_solution_integer_after(this->restricted_master_problem->are_all_variables_binary());
			}
			this->time_spent = duration;
			this->nb_iterations = iter;
		}
		catch (...) {
			cout << "[ColumnGeneration] - Error during execution..." << endl;
		}
	}

	bool is_dual_bound_termination_condition_hit(const bool& isMaximisation, const bool& is_objective_integer, const double& best_incumbent_value) {
		if (isMaximisation) {
			if (is_objective_integer) {
				double toFloor = this->restricted_master_problem->get_objective_value() + ::EPSILON;
				if (this->dual_bound == floor(toFloor)) {
					return true;
				}
			}
			if (::less(this->dual_bound, best_incumbent_value)) {
				return true;
			}
		}
		else {
			if (is_objective_integer) {
				double toCeil = this->restricted_master_problem->get_objective_value() - ::EPSILON;
				if (this->dual_bound == ceil(toCeil)) {
					return true;
				}
			}
			if (::less(best_incumbent_value, this->dual_bound)) {
				return true;
			}
		}
		return false;
	}

	void update_dual_bound(const bool& isMaximisation, const bool& is_objective_integer) {
		double new_dual_bound = this->restricted_master_problem->compute_lagrangian_bound_RMP_obj_term();
		bool isError = false;
		double rmp_val = this->restricted_master_problem->get_objective_value();
		//cout << "init " << new_dual_bound << " " << this->restricted_master_problem->get_objective_value() << "\n";
		if (isMaximisation) {
			new_dual_bound -= this->restricted_master_problem->getUpperBoundExchanges() * this->pricing_subproblem->get_value();
			//cout << "pricing " << this->pricing_subproblem->get_value() << " " << new_dual_bound << endl;
			if (is_objective_integer) {
				double toFloor = new_dual_bound + ::EPSILON;
				new_dual_bound = floor(toFloor);
				rmp_val += ::EPSILON;
				rmp_val = floor(rmp_val);
			}
			//cout << new_dual_bound << "\n";
			this->dual_bound = min(this->dual_bound, new_dual_bound);
			if (::strictly_less(this->dual_bound, rmp_val)) {
				isError = true;
			}
		}
		else {
			new_dual_bound += this->restricted_master_problem->getUpperBoundExchanges() * this->pricing_subproblem->get_value();
			if (is_objective_integer) {
				double toCeil = new_dual_bound - ::EPSILON;
				new_dual_bound = ceil(toCeil);
				rmp_val -= ::EPSILON;
				rmp_val = ceil(rmp_val);
			}
			this->dual_bound = max(this->dual_bound, new_dual_bound);
			if (::strictly_greater(this->dual_bound, rmp_val)) {
				isError = true;
			}
		}
		if (isError) {
			string str = "is_max "+to_string(isMaximisation) + " obj " + to_string(rmp_val) + " db " + to_string(this->dual_bound) + "\n";
			string streamName = ::solutionPath + "ERRORS_BOUNDS.txt";
			ofstream mystream;
			mystream.open(streamName, ios::app);
			mystream << ::instanceName << "\t" << str << endl;
			mystream << "\n\n\n";
			mystream.close();
		}
	}

	/**
	 * Get method of nb_terations.
	 * 
	 * \return nb_terations: const int&
	 */
	const int& get_nb_iterations() const {
		return this->nb_iterations;
	}

	/**
	 * Get method of nb_columns_found.
	 *
	 * \return nb_columns_found: const int&
	 */
	const int& get_nb_columns_found() const {
		return this->nb_columns_found;
	}

	/*void update_best_incumbent_value(const double& new_incumbent_value) override {
		this->best_incumbent_value = new_incumbent_value;
	}*/

	/**
	 * Get method of time_spent.
	 *
	 * \return time_spent: const double&
	 */
	const double& get_time_spent() const {
		return this->time_spent;
	}

	const double& get_dual_bound() const {
		return this->dual_bound;
	}

	vector<vector<ColGenIterationInfo>>& get_col_gen_interation_info() {
		return this->col_gen_iterations_info;
	}

	void set_dual_bound(const double& db) {
		this->dual_bound = db;
	}

};

#endif // COLUMNGENERATION_H