/*****************************************************************//**
 * \file   ExactGenerator.h
 * \brief  Defines our dynamic programming algorithm that solves our pricing subproblem.
 *
 * \author Matteo Petris
 * \date   February 2023
 *********************************************************************/
#ifndef EXACTGENERATORIKEP_H
#define EXACTGENERATORIKEP_H


#include "PricingSubProblemAlgorithmAbstract.h"
#include "PricingProblem.h"
#include "Label.h"
#include "ArcBranchConstraint.h"
#include "VisitBranchConstraint.h"
#include "SubsetRowConstraint.h"
#include "ExchangeIKEP.h"
#include "DualSolutionIKEP.h"

/**
 * \class ExactGenerator.
 * \brief  Defines our dynamic programming algorithm that solves our pricing subproblem.
 */
class ExactGeneratorIKEP :
	public PricingSubProblemAlgorithmAbstract<InstanceIKEP, vector<ExchangeIKEP>, DualSolutionIKEP, GRBConstr> {

protected:

	const vector<VertexIKEP>& vertices;
	vector<int> verticesToConsider;
	vector<vector<int>> outgoingArcsToConsider;
	int source;
	int chainsLength;
	int wordsNumber;
	vector<vector<double>> dualPrices;
	vector<int> active_non_robust_cuts;
	vector<double> active_non_robust_duals;

	/**********************************************
	**			Solution Related to the dynamic programming
	***********************************************/
	double time;
	Label optimalLabel;
	vector<ExchangeIKEP> solution_pool;

public:

	/**
	 * Constructor with pricing problem.
	 *
	 * \param instance: Instance&
	 * \param dual_variables: DualSolution*
	 */
	ExactGeneratorIKEP(InstanceIKEP& instance, DualSolutionIKEP* dual_variables, vector<ExchangeIKEP>* rmp_columns, vector<Constraint<GRBConstr>*>* branching_constraints, vector<Constraint<GRBConstr>*>* cut_constraints);

	/**
	 * \brief Destructor.
	 *
	 */
	~ExactGeneratorIKEP();

	/**
	* \brief Evaluates if the handler (the algorithm) can handle (solve) the pricing sub-problem based on the code of request.
	*
	* \param request : string
	* \return True if the concrete algorithm can solve the pricing sub-problem, false otherwise.
	*/
	bool can_solve(const string& request) const override;

	/**
	 * Checks and updates failed_to_find_favorably_priced_columns after solving the pricing subproblem.
	 * \details If no negative reduced cost found, then it updates failed_to_find_favorably_priced_columns with true.
	 *
	 */
	void update_failed_to_find_favorably_priced_columns() override;

	void buildDualPrices();
	void buildVertices();
	void buildActiveNonRobustCuts();

	/**
	 * Solves the pricing subproblem with dynamic programming with the request "DYNAMICPROGRAMMING".
	 *
	 * \param request: const string&
	 */
	vector<ExchangeIKEP> solve(const string& request) override;

	vector<list<Label>> extendForward();
	bool dominationAndInsertion(list<Label>& labels, const Label& current, Label& extension);

	vector<list<Label>> extendForward_non_robust();
	void manage_extension_non_robust_cuts(Label& extension, const int& vertex_id, const int& vertex_word, const int& vertex_bit);
	bool dominationAndInsertion_non_robust(list<Label>& labels, const Label& current, Label& extension);

	void addExchanges(const Label& label, const bool& areSubpathsAdded);

	vector<list<Label>> extendForwardPrint();
	bool isDominated(list<Label>& labels, const Label& current, Label& extension);
	bool isDominatedPrint(list<Label>& labels, const Label& current, Label& extension, string& str);

	/**
	 * \brief Writes the value of the solution found by dynamic programming in a file.
	 *
	 */
	void write_value_solution();
	bool check_solution();
	bool check_labels_reduced_cost(const Label& label, const Exchange& exchange);
	double evaluate_reduced_cost(const Exchange& exchange);

};

#endif // !EXACTGENERATORIKEP_H
