#include "ExactGeneratorCyclesChains.h"

ExactGeneratorCyclesChains::ExactGeneratorCyclesChains(Instance& instance, DualSolution* dual_variables, vector<Exchange>* rmp_columns, vector<Constraint<GRBConstr>*>* branching_constraints, vector<Constraint<GRBConstr>*>* cut_constraints)
	: PricingSubProblemAlgorithmAbstract(instance, dual_variables, rmp_columns, branching_constraints, cut_constraints), vertices(instance.getVertices()) {
	this->cyclesLength = instance.getCyclesLength();
	this->wordsNumber = instance.getWordsNumber();
	this->source = instance.getDummyNodeId();
	this->chainsLength = instance.getChainsLength();
	this->pairsAsSourcesToConsider = instance.getPairsToProcess();
	this->nodesPerPairToProcess = instance.getNodesPerPairToProcess();
	this->areCyclesToPrice = (this->cyclesLength > 1);
	this->areChainsToPrice = (this->chainsLength > 1) && (instance.getAltruisticDonorsNumber() > 0);
}

ExactGeneratorCyclesChains::~ExactGeneratorCyclesChains() {
}

bool ExactGeneratorCyclesChains::can_solve(const string& request) const {
	return request == "EXACTGENERATOR" || request == "WHATEVER";
}

vector<Exchange> ExactGeneratorCyclesChains::solve(const string& request, const double time_limit) {
	//clock_t ss, tt;

	if (can_solve(request)) {

		this->is_early_terminated = false;
		this->solution_pool.clear();
		this->value = ::OMEGA;
		this->favourablyPricedVariablesCounter = 0;
		this->optimalLabel_cycles = Label();
		this->optimalLabel_chains = Label();
		this->optimalLabel = Label();
		buildActiveNonRobustCuts();
		unordered_set<int> sourcesToAddToTabuList;	//when the tabu list is processed we don't want to process again 

		if (this->active_non_robust_cuts.empty()) {

			/*PRICE CYCLES*/
			this->value_cycles = 0.0;
			buildDualPrices_cycles();


			//dynamic programming cycles
			if (this->areCyclesToPrice) {

				for (int i = 0; i < this->pairsAsSourcesToConsider.size(); i++) {

					this->valuePerPricing = 0.0;
					int source = this->pairsAsSourcesToConsider.at(i);

					if (this->verticesToConsider.at(source) == 1 && this->tabuList.find(source) == this->tabuList.end()) {


						////////////////////////////////////////////////////////////////////////BELLMAN FORD///////////////////////////////////////////////////
						//ss = clock();
						list<Label> forwardLabels = BellmanFord_cycles(source, this->cyclesLength + 1, this->instance.getArcsPerPairToProcess().at(source));
						//tt = clock();
						//if (::isToPrint) {
						//	cout << "SOURCE " << source /*<< "DUR " << (float)(tt - ss) / CLOCKS_PER_SEC*/ << "\t" << this->valuePerPricing << "\n";
						//	cout << "\n";
						//}
						//::isToPrint = false;
						
						if (this->valuePerPricing < -EPSILON) {
							addExchanges_cycles(this->optimalLabel_cycles);
							//cout << this->solution_pool.back().toString() << "\n\n";
						}
						else {
							sourcesToAddToTabuList.insert(source);
						}

						if (::strictly_less(this->valuePerPricing, this->value_cycles)) {
							this->value_cycles = this->valuePerPricing;
							this->optimalLabel = this->optimalLabel_cycles;
						}

					}

				}

			}

			/*PRICE CHAINS*/
			if (this->value_cycles > -::EPSILON) {

				this->value_chains = 0.0;
				this->isOneNegativeChainElementary = false;
				list<Label> forwardLabels;

				if (this->areChainsToPrice) {

					buildVertices_chains();
					buildDualPrices_chains();
					compute_best_dual_price();

					//dynamic programming
					forwardLabels = BellmanFord_chains();

				}

				bool is_tabu_list_to_do = false;

				//exist path
				if (this->value_chains < -::EPSILON) {

					//the path is elementary -> RMP
					if (this->isOneNegativeChainElementary) {
						//build exchange object
						addExchanges_chains(this->optimalLabel_chains, true);
						for (list<Label>::const_iterator label = forwardLabels.begin(); label != forwardLabels.end(); label++) {
							/*if (::isToPrint) {
								cout << "LABEL " << label->toString() << "\n";
							}*/
							if (label->getCost() < -EPSILON && label->getLength() > 1) {
								addExchanges_chains(*label, false);

								if (this->solution_pool.size() > ::PROMISINGVARIABLESPERITERATION) {
									break;
								}

							}
						}

						if (!this->tabuList.empty()) {
							this->is_early_terminated = true;
						}

					}//the path is non-elementary -> check tabu list + optimality conditions
					else {
						is_tabu_list_to_do = true;
					}

				}//NO ELEMENTARY CHAINS FOUND -> PRICING OF GRAPHS IN THE TABU LIST
				else {
					is_tabu_list_to_do = true;
				}

				if (is_tabu_list_to_do) {

					this->value_cycles = 0.0;
					//vector<int> removeFromTabuList;
					buildDualPrices_cycles();

					if (this->areCyclesToPrice) {

						for (unordered_set<int>::const_iterator it = this->tabuList.begin(); it != this->tabuList.end(); it++) {

							int source = *it;
							this->valuePerPricing = 0.0;

							if (this->verticesToConsider.at(source) == 1) {

								////////////////////////////////////////////////////////////////////////BELLMAN FORD///////////////////////////////////////////////////
								//ss = clock();

								list<Label> forwardLabels = BellmanFord_cycles(source, this->cyclesLength + 1, this->instance.getArcsPerPairToProcess().at(source));
								//tt = clock();
								
								//if (::isToPrint) {
								//	cout << "TABU SOURCE " << source /*<< "DUR " << (float)(tt - ss) / CLOCKS_PER_SEC*/ << "\t" << this->valuePerPricing << "\n";
								//	cout << "\n";
								//}
								//::isToPrint = false;
								if (this->valuePerPricing < -EPSILON) {
									//removeFromTabuList.push_back(source);
									addExchanges_cycles(this->optimalLabel_cycles);
									//cout << this->solution_pool.back().toString() << endl;
								}

								if (::strictly_less(this->valuePerPricing, this->value_cycles)) {
									this->value_cycles = this->valuePerPricing;
									this->optimalLabel = this->optimalLabel_cycles;
								}

							}

						}

						/*for (int l = 0; l < removeFromTabuList.size(); l++) {
							this->tabuList.erase(removeFromTabuList.at(l));
						}*/
						this->tabuList.clear();

					}

				}

				bool isLabellingToCall = false;
				if (this->value_cycles > -::EPSILON && this->value_chains < -::EPSILON && !this->isOneNegativeChainElementary && this->chainsLength > this->cyclesLength + 1) {
					isLabellingToCall = true;
				}

				if (this->value_cycles > -::EPSILON && this->value_cycles < this->dual_variables->get_beta() + this->dual_exchange_number_branch - ::EPSILON
					&& this->value_chains < -::EPSILON && !this->isOneNegativeChainElementary && this->chainsLength <= this->cyclesLength + 1) {
					isLabellingToCall = true;
				}

				
				if (isLabellingToCall) {

					//CALL LABELLING ALGORITHM TO PROVE OPTIMALITY
					this->value_chains = 0.0;
					vector<list<Label>> forwardLabels;

					if (this->areChainsToPrice) {

						buildVertices_chains();
						buildDualPrices_chains();
						compute_best_dual_price();

						//dynamic programming
						forwardLabels = extendForward_chains();
						::labellingCalls++;

					}

					if (this->value_chains < -EPSILON) {
						//build exchange object
						addExchanges_chains(this->optimalLabel_chains, false);
						for (int i = 0; i < forwardLabels.size(); i++) {
							for (list<Label>::const_iterator label = forwardLabels.at(i).begin(); label != forwardLabels.at(i).end(); label++) {
								if (label->getCost() < -EPSILON && label->getLength() > 1) {
									addExchanges_chains(*label, false);
								}
							}
							if (this->solution_pool.size() > ::PROMISINGVARIABLESPERITERATION) {
								break;
							}
						}
					}

				}

			}

		}
		else {

			/*PRICE CYCLES*/
			this->value_cycles = 0.0;

			if (this->areCyclesToPrice) {

				//buildVertices_cycles();
				buildDualPrices_cycles();

				//dynamic programming cycles
				for (int i = 0; i < this->pairsAsSourcesToConsider.size(); i++) {

					this->valuePerPricing = 0.0;
					int source = this->pairsAsSourcesToConsider.at(i);

					if (this->verticesToConsider.at(source) == 1 && this->tabuList.find(source) == this->tabuList.end()) {

						////////////////////////////////////////////////////////////////////////BELLMAN FORD///////////////////////////////////////////////////
						vector<list<Label>> forwardLabels = extendForward_non_robust_cycles(source, this->nodesPerPairToProcess.at(source), this->instance.getArcsPerPairToProcess().at(source));
						if (this->valuePerPricing < -EPSILON) {
							addExchanges_cycles(this->optimalLabel_cycles);
							/*for (list<Label>::const_iterator label = forwardLabels.at(source).begin(); label != forwardLabels.at(source).end(); label++) {
								if (label->getCost() < -EPSILON && label->getLength() > 1) {
									addExchanges_cycles(*label);
								}
							}*/
						}
						else {
							sourcesToAddToTabuList.insert(source);
						}

						if (::strictly_less(this->valuePerPricing, this->value_cycles)) {
							this->value_cycles = this->valuePerPricing;
							this->optimalLabel = this->optimalLabel_cycles;
						}

					}

				}

			}

			/*PRICE CHAINS*/
			if (this->value_cycles > -::EPSILON) {

				this->value_chains = 0.0;
				vector<list<Label>> forwardLabels;

				if (this->areChainsToPrice) {

					buildVertices_chains();
					buildDualPrices_chains();

					//dynamic programming
					forwardLabels = extendForward_non_robust_chains();

				}

				if (this->value_chains < -EPSILON) {
					//build exchange object
					addExchanges_chains(this->optimalLabel_chains, false);
					for (int i = 0; i < forwardLabels.size(); i++) {
						for (list<Label>::const_iterator label = forwardLabels.at(i).begin(); label != forwardLabels.at(i).end(); label++) {
							if (label->getCost() < -EPSILON && label->getLength() > 1) {
								addExchanges_chains(*label, false);
							}
						}
						if (this->solution_pool.size() > ::PROMISINGVARIABLESPERITERATION) {
							break;
						}
					}

					if (!this->tabuList.empty()) {
						this->is_early_terminated = true;
					}

				}//NO CHAINS FOUND -> PRICING OF GRAPHS IN THE TABU LIST
				else {

					this->value_cycles = 0.0;

					if (this->areCyclesToPrice) {

						//vector<int> removeFromTabuList;
						buildDualPrices_cycles();

						for (unordered_set<int>::const_iterator it = this->tabuList.begin(); it != this->tabuList.end(); it++) {

							int source = *it;
							this->valuePerPricing = 0.0;

							if (this->verticesToConsider.at(source) == 1) {

								////////////////////////////////////////////////////////////////////////BELLMAN FORD///////////////////////////////////////////////////
								vector<list<Label>> forwardLabels = extendForward_non_robust_cycles(source, this->nodesPerPairToProcess.at(source), this->instance.getArcsPerPairToProcess().at(source));
								if (this->valuePerPricing < -EPSILON) {
									addExchanges_cycles(this->optimalLabel_cycles);
									//removeFromTabuList.push_back(source);
									/*for (list<Label>::const_iterator label = forwardLabels.at(source).begin(); label != forwardLabels.at(source).end(); label++) {
										if (label->getCost() < -EPSILON && label->getLength() > 1) {
											addExchanges_cycles(*label);
										}
									}*/
								}

								if (::strictly_less(this->valuePerPricing, this->value_cycles)) {
									this->value_cycles = this->valuePerPricing;
									this->optimalLabel = this->optimalLabel_cycles;
								}

							}

						}

						/*for (int l = 0; l < removeFromTabuList.size(); l++) {
							this->tabuList.erase(removeFromTabuList.at(l));
						}*/
						this->tabuList.clear();

					}

				}

			}

		}

		for (unordered_set<int>::const_iterator it = sourcesToAddToTabuList.begin(); it != sourcesToAddToTabuList.end(); it++) {
			this->tabuList.insert(*it);
		}

		this->value = min(this->value_chains, this->value_cycles);
		if (::strictly_less(this->value_chains, this->value_cycles)) {
			this->optimalLabel = this->optimalLabel_chains;
		}
		//cout << this->optimalLabel.toString() << "\n\n";


		//if (this->value > -EPSILON) {

		//	buildVertices_cycles();
		//	buildDualPrices_cycles();

		//	for (int i = 0; i < this->pairsAsSourcesToConsider.size(); i++) {
		//		this->valuePerPricing = 0.0;
		//		//cout << this->vertices.at(this->sourcesToConsider.at(i)).toString(false) << endl;
		//		int source = this->pairsAsSourcesToConsider.at(i);
		//		vector<list<Label>> forwardLabels = extendForward(source);
		//		
		//		//cout << "VALUE " << this->valuePerPricing << endl;

		//		if (this->valuePerPricing < -EPSILON) {
		//			cout << "SOURCE " << source << " " << this->valuePerPricing << endl;
		//		}
		//		
		//	}

		//}

		/*if (::isToPrint) {
			for (int k = 0; k < this->solution_pool.size(); k++) {
				const Exchange* ec = &this->solution_pool.at(k);
				double cost = priceVariable(ec);
				if (cost < -EPSILON) {
					cout << ec->toString() << "\nREDUCED COST\t" << cost << endl;
				}
			}

		}*/



		update_failed_to_find_favorably_priced_columns();

		if (!has_failed_to_find_favorably_priced_columns()) {
			return this->solution_pool;
		}
		else
			return PricingSubProblemAlgorithmAbstract<Instance, vector<Exchange>, DualSolution, GRBConstr>::solve(request, time_limit);

	}
	else
		return PricingSubProblemAlgorithmAbstract<Instance, vector<Exchange>, DualSolution, GRBConstr>::solve(request, time_limit);
}

void ExactGeneratorCyclesChains::update_failed_to_find_favorably_priced_columns() {
	this->fails_to_find_favorably_priced_columns = false;
	if (this->value > -EPSILON) {
		this->fails_to_find_favorably_priced_columns = true;
	}
}

void ExactGeneratorCyclesChains::buildActiveNonRobustCuts() {
	this->active_non_robust_cuts.clear();
	this->active_non_robust_duals.clear();
	double new_tol = ::EPSILON / 100;
	for (int i = 0; i < this->cut_constraints->size(); i++) {
		if (this->dual_variables->get_sigma_i(i) > new_tol) {
			this->active_non_robust_cuts.push_back(i);
			this->active_non_robust_duals.push_back(this->dual_variables->get_sigma_i(i));
		}
	}

	/*if (::isToPrint) {
		::appendToFile("fileCheck.log", "ARE INEQUALITIES ACTIVE? "+to_string(!this->active_non_robust_cuts.empty())+"\n");
	}*/

}

list<Label> ExactGeneratorCyclesChains::BellmanFord_cycles(const int& source, const int& maxLength, const vector<vector<int>>& arcs) {

	//preprocessing arcs
	this->best_dual_price = ::OMEGA;
	for (unordered_set<int>::const_iterator it = this->nodesPerPairToProcess.at(source).begin(); it != this->nodesPerPairToProcess.at(source).end(); it++) {
		for (int j = 0; j < arcs.at(*it).size(); j++) {
			this->best_dual_price = min(this->best_dual_price, this->dualPrices.at(*it).at(arcs.at(*it).at(j)));
		}
	}

	//initialisation
	vector<vector<double>> weights(maxLength, vector<double>(this->vertices.size(), ::OMEGA));
	weights.at(0).at(source) = this->dual_variables->get_beta() + this->dual_exchange_number_branch;
	vector<vector<bool>> vertexLists(maxLength, vector<bool>(this->vertices.size(), false));
	vertexLists.at(0).at(source) = true;
	vector<vector<int>> walks(maxLength, vector<int>(this->vertices.size(), -1));
	walks.at(0).at(source) = source;

	list<Label> negativeReducedCostPaths;

	//iterations
	for (int k = 1; k < maxLength; k++) {
		/*if (::isToPrint) {
			cout << "CURRENT LENGTH " << k << endl;
		}*/
		int previous = k - 1;
		for (int l = 0; l < vertexLists.at(previous).size(); l++) {

			if (vertexLists.at(previous).at(l)) {

				int id = l;

				//completion bound
				double currentWeight = weights.at(previous).at(id);

				/*if (::isToPrint) {
					cout << "CURRENT NODE " << id << "\tBEST LABEL " << currentWeight << "\tBD " <<best_dual_price<<" edge "<< (this->cyclesLength - k) <<" CB "<<
						currentWeight + (maxLength - k) * best_dual_price<<"\n";
					cout << "Current path ";
					for (int p = 0; p < walks.at(previous).at(id).size(); p++) {
						cout << walks.at(previous).at(id).at(p) << " ";
					}
					cout << "\n";
				}*/

				if (currentWeight + (maxLength - k) * this->best_dual_price < -EPSILON) {

					for (int j = 0; j < arcs.at(id).size(); j++) {
						int dest = arcs.at(id).at(j);
						double newCost = currentWeight + this->dualPrices.at(id).at(dest);

						/*if (::isToPrint) {
							cout << "DEST " << dest <<"\t"<<newCost << endl;
						}*/

						if (::strictly_less(newCost, weights.at(k).at(dest))) {

							weights.at(k).at(dest) = newCost;
							vertexLists.at(k).at(dest) = true;
							walks.at(k).at(dest) = walks.at(k - 1).at(id);
							walks.at(k).at(dest) = id;

							if (newCost < -EPSILON && dest == source) {

								/*int weight = 0;
								for (int i = 0; i < walks.at(k).at(dest).size() - 1; i++) {
									int id1 = walks.at(k).at(dest).at(i);
									int id2 = walks.at(k).at(dest).at(i + 1);
									const Vertex* v = &this->vertices.at(id1);
									weight += v->getOutGoingArcs().at(id2);
								}*/

								vector<int> seq(k + 1, -1);
								int current = dest;
								seq.at(k) = dest;
								int lentgth = k;
								while (lentgth > 0) {
									int previous = walks.at(lentgth).at(current);
									current = previous;
									lentgth--;
									seq.at(lentgth) = current;
								}

								int weight = 0;
								for (int i = 0; i < seq.size() - 1; i++) {
									int id1 = seq.at(i);
									int id2 = seq.at(i + 1);
									const Vertex* v = &this->vertices.at(id1);
									weight += v->getOutGoingArcs().at(id2);
								}

								Label extension(source, seq.size() - 1, weight, newCost);
								extension.setSequence(seq);
							
								//add sri dual prices to reduced cost
								double recomputed_cost_sri = add_sri_dual_prices(extension);
								/*if (::isToPrint) {
									cout << extension.toString() << "\n\n";
								}*/
								
								if (recomputed_cost_sri < -::EPSILON) {

									negativeReducedCostPaths.push_back(extension);
									if (::strictly_less(recomputed_cost_sri, this->valuePerPricing)) {
										this->valuePerPricing = recomputed_cost_sri;
										this->optimalLabel_cycles = extension;
									}

									this->is_early_terminated = true;
									return negativeReducedCostPaths;

									this->favourablyPricedVariablesCounter++;
									if (this->favourablyPricedVariablesCounter > ::PROMISINGLABELSPERITERATION) {
										this->is_early_terminated = true;
										negativeReducedCostPaths.sort();
										return negativeReducedCostPaths;
									}

								}

							}
						}
					}

				}

			}

		}

	}

	negativeReducedCostPaths.sort();
	return negativeReducedCostPaths;

}

void ExactGeneratorCyclesChains::buildDualPrices_cycles() {
	this->dualPrices = vector<vector<double>>(this->instance.getVertexNumber(), vector<double>(this->instance.getVertexNumber(), 0.0));
	this->verticesToConsider = vector<int>(this->instance.getVertexNumber(), 1);
	this->dual_exchange_number_branch = 0.0;
	for (int i = 0; i < this->instance.getVertexNumber(); i++) {
		const Vertex* v = &this->instance.getVertices().at(i);
		for (unordered_map<int, int>::const_iterator arc = v->getOutGoingArcs().begin(); arc != v->getOutGoingArcs().end(); arc++) {
			this->dualPrices.at(v->getId()).at(arc->first) -= arc->second;
			this->dualPrices.at(v->getId()).at(arc->first) += this->dual_variables->get_pi_i(arc->first);
		}
	}
	for (int i = 0; i < this->branching_constraints->size(); i++) {
		int rhs = this->branching_constraints->at(i)->get_rhs();
		double dual = ::OMEGA;
		if (rhs > 0) {
			dual = this->dual_variables->get_gamma_i(i);
		}
		if (this->branching_constraints->at(i)->get_name() == "ARCBRANCH") {
			int id1 = dynamic_cast<ArcBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_items().first;
			int id2 = dynamic_cast<ArcBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_items().second;
			this->dualPrices.at(id1).at(id2) += dual;
		}
		else if (this->branching_constraints->at(i)->get_name() == "VISITBRANCH") {
			int id = dynamic_cast<VisitBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_item();
			/*if (::isToPrint) {
				cout << "DUAL " << id << "\t" << this->dual_variables->get_gamma_i(i) << endl;
			}*/
			if (rhs == 0) {
				this->verticesToConsider.at(id) = 0;
			}
			for (int j = 0; j < this->instance.getVertexNumber(); j++) {
				this->dualPrices.at(j).at(id) += dual;
			}
		}
		else if (this->branching_constraints->at(i)->get_name() == "EXCHANGENUMBERBRANCH") {
			/*if (::isToPrint) {
				cout << "DUAL " << this->dual_variables->get_gamma_i(i) << endl;
			}*/
			this->dual_exchange_number_branch += dual;
			/*for (int j = 1; j < this->instance.getVertexNumber(); j++) {
				this->dualPrices.at(0).at(j) += dual;
			}*/
		}
	}
	/*cout << "DUAL PRICIES \n";
	for (int i = 0; i < this->instance.getVertexNumber(); i++) {
		const Vertex* v = &this->instance.getVertices().at(i);
		for (unordered_map<int, int>::const_iterator arc = v->getOutGoingArcs().begin(); arc != v->getOutGoingArcs().end(); arc++) {
			if (this->dualPrices.at(v->getId()).at(arc->first) != 0.0) {
				cout << "\t" << v->getId() << "\t" << arc->first << "\t" << arc->second << "\t" << this->dualPrices.at(v->getId()).at(arc->first) << endl;
			}
		}
	}
	cout << "\n";*/
	/*if (isToPrint) {
		string check = "DUAL PRICIES \n";
		for (int i = 0; i < this->instance.getVertexNumber(); i++) {
			const Vertex* v = &this->instance.getVertices().at(i);
			for (unordered_map<int, int>::const_iterator arc = v->getOutGoingArcs().begin(); arc != v->getOutGoingArcs().end(); arc++) {
				if (this->dualPrices.at(v->getId()).at(arc->first) != 0.0) {
					check.append("\t" + to_string(v->getId()) + "\t" + to_string(arc->first) + "\t" + to_string(arc->second) + "\t" + to_string(this->dualPrices.at(v->getId()).at(arc->first)) + "\n");
				}
			}

		}
		::appendToFile("fileCheck.log", check);
	}*/
}

list<Label> ExactGeneratorCyclesChains::BellmanFord_chains() {

	int chainLengthBF = this->chainsLength + 2;
	vector<vector<double>> weights(chainLengthBF, vector<double>(this->vertices.size(), ::OMEGA));
	weights.at(0).at(source) = 0;
	vector<vector<bool>> vertexLists(chainLengthBF, vector<bool>(this->vertices.size(), false));
	vertexLists.at(0).at(source) = true;
	vector<vector<int>> walks(chainLengthBF, vector<int>(this->vertices.size(), -1));
	walks.at(0).at(source) = source;

	list<Label> negativeReducedCostPaths;

	for (int k = 1; k < chainLengthBF; k++) {
		int previous = k - 1;
		for (int l = 0; l < vertexLists.at(previous).size(); l++) {

			if (vertexLists.at(previous).at(l)) {

				int id = l;

				//completion bound
				double currentWeight = weights.at(previous).at(id);

				if (currentWeight + (chainLengthBF - k) * this->best_dual_price < -EPSILON) {

					for (int j = 0; j < this->outgoingArcsToConsider.at(id).size(); j++) {
						int dest = this->outgoingArcsToConsider.at(id).at(j);
						double newCost = currentWeight + this->dualPrices.at(id).at(dest);
						if (::strictly_less(newCost, weights.at(k).at(dest))) {
							weights.at(k).at(dest) = newCost;
							vertexLists.at(k).at(dest) = true;
							//walks.at(k).at(dest) = walks.at(k - 1).at(id);
							walks.at(k).at(dest) = id;
							if (newCost < -EPSILON && k > 1) {

								/*int weight = 0;
								for (int i = 0; i < walks.at(k).at(dest).size() - 1; i++) {
									int id1 = walks.at(k).at(dest).at(i);
									int id2 = walks.at(k).at(dest).at(i + 1);
									const Vertex* v = &this->vertices.at(id1);
									weight += v->getOutGoingArcs().at(id2);
								}*/

								vector<int> seq(k + 1, -1);
								int current = dest;
								seq.at(k) = dest;
								int lentgth = k;
								while (lentgth > 0) {
									int previous = walks.at(lentgth).at(current);
									current = previous;
									lentgth--;
									seq.at(lentgth) = current;
								}

								int weight = 0;
								for (int i = 0; i < seq.size() - 1; i++) {
									int id1 = seq.at(i);
									int id2 = seq.at(i + 1);
									const Vertex* v = &this->vertices.at(id1);
									weight += v->getOutGoingArcs().at(id2);
								}

								Label extension(dest, seq.size() - 1, weight, newCost);
								extension.setSequence(seq);

								//add sri dual prices to reduced cost
								//cout << extension.toString() << endl;
								double recomputed_cost_sri = add_sri_dual_prices(extension); 

								if (recomputed_cost_sri < -::EPSILON) {

									//cout << extension.toString() << endl;
									if (::strictly_less(recomputed_cost_sri, this->value_chains)) {
										this->value_chains = recomputed_cost_sri;
										this->optimalLabel_chains = extension;
									}

									//check elementarity
									bool isElementary = true;
									unordered_set<int> vertices_set;
									for (int i = 0; i < seq.size(); i++) {
										int id1 = seq.at(i);
										if (vertices_set.find(id1) != vertices_set.end()) {
											isElementary = false;
											break;
										}
									}

									this->favourablyPricedVariablesCounter++;
									if (isElementary) {
										//cout << extension.toString() << endl;
										this->isOneNegativeChainElementary = true;
										negativeReducedCostPaths.push_back(extension);

									}

									//return negativeReducedCostPaths;

									if (this->favourablyPricedVariablesCounter >= ::PROMISINGLABELSPERITERATION) {
										this->is_early_terminated = true;
										negativeReducedCostPaths.sort();
										return negativeReducedCostPaths;
									}

								}
								/*else {
									cout << "COST " << extension.getCost() << "\t" << recomputed_cost_sri << "\n";
									cout << "\n";
								}*/

							}
						}
					}

				}

			}

		}

	}

	negativeReducedCostPaths.sort();
	return negativeReducedCostPaths;

}

vector<list<Label>> ExactGeneratorCyclesChains::extendForward_non_robust_cycles(const int& source, const unordered_set<int>& nodes, const vector<vector<int>>& arcs) {

	try {

		//INITIALIZATION
		int vSize = this->sourcesToConsider.size();
		vector<list<Label>> labels(this->vertices.size());
		Label sourceLabel(source, 0, 0, this->dual_variables->get_beta() + this->dual_exchange_number_branch);
		sourceLabel.buildSequence({});
		vector<int> ngMemory(this->wordsNumber, 0);
		sourceLabel.setActive_SSI(this->active_non_robust_cuts.size());
		sourceLabel.setNgMemory(this->wordsNumber);
		labels.at(source).push_back(sourceLabel);

		//ITERATIONS
		bool termination = false;

		while (termination != true) {

			termination = true;

			for (unordered_set<int>::const_iterator node = nodes.begin(); node != nodes.end(); node++) {

				const Vertex* v = &this->vertices.at(*node);
				//if (::isToPrint) {
				//	::appendToFile("label_check.log", "FIRST V\n" + v->toString(false) + "\n");
				//	//cout << "START\n" << v->toString(false) << "\n";
				//}

				for (list<Label>::iterator label = labels.at(*node).begin(); label != labels.at(*node).end(); label++) {

					if (!label->getIsExtended() && label->getLength() < this->cyclesLength) {

						//if (::isToPrint) {
						//	::appendToFile("label_check.log", "LABEL TO EXTEND\n" + label->toString() + "\n");
						//	//cout << "LABEL TO EXTEND\n" << label->toString() << "\n";
						//}

						for (int j = 0; j < arcs.at(*node).size(); j++) {

							int idW = arcs.at(*node).at(j);
							const Vertex* w = &this->vertices.at(idW);
							//if (::isToPrint) {
							//	::appendToFile("label_check.log", "REACHED\n" + w->toString(false) + "\n");
							//	//cout << "REACHED\n" << w->toString(false) << "\n";
							//}

							if (!label->isVisited(w->getWord(), w->getBitKey())) {

								double redCost = label->getCost() + this->dualPrices.at(*node).at(idW);
								Label extension(idW, label->getLength() + 1, label->getWeight() + v->getOutGoingArcs().at(idW), redCost);
								extension.buildNgMemory(label->getNgMemory(), w->getNgSet(), w->getWord(), w->getBitKey());
								extension.setActive_SSI(label->getActive_SSI());
								manage_extension_non_robust_cuts_cycles(extension, idW, w->getWord(), w->getBitKey());

								//if (::isToPrint) {
								//	::appendToFile("label_check.log", "EXTENDED\n" + extension.toString() + "\n");
								//	//cout << "EXTENDED\n" << extension.toString() << endl;
								//}

								//CHECK DOMINANCE+INSERT IN LIST

								bool isInserted = dominationAndInsertion_non_robust_cycles(labels.at(idW), *label, extension);
								if (isInserted) {
									/*if (::isToPrint) {
										::appendToFile("label_check.log", "INSERTEFD\n");
									}*/
									if (w->getId() == source && ::strictly_less(extension.getCost(), this->valuePerPricing) && extension.getLength() > 1) {
										this->optimalLabel_cycles = extension;
										this->valuePerPricing = extension.getCost();
										if (extension.getCost() < -::EPSILON) {
											this->is_early_terminated = true;
											return labels;
										}
									}
									termination = false;
								}
								//cout << "INSERTED? " << isInserted << endl;

							}

						}

					}

					label->setIsExtended(true);

				}

			}

		}

		return labels;

	}
	catch (...) {
		cout << "[ExactGeneratorCycles] - Error during optimization NON ROBUST" << endl;
	}

}

void ExactGeneratorCyclesChains::manage_extension_non_robust_cuts_cycles(Label& extension, const int& vertex_id, const int& vertex_word, const int& vertex_bit) {

	for (int i = 0; i < this->active_non_robust_cuts.size(); i++) {
		int cut_id = this->active_non_robust_cuts.at(i);
		const SubsetRowConstraint<GRBConstr>* ssi = dynamic_cast<SubsetRowConstraint<GRBConstr>*>(this->cut_constraints->at(cut_id));
		if (ssi->is_vertex_in_subset(vertex_word, vertex_bit)) {
			/*if (::isToPrint) {
			cout << ssi->toString() << endl;
			}*/
			int multiplier = ssi->get_multiplier(vertex_id);
			extension.addNonRobustDual(this->active_non_robust_duals.at(i), multiplier, ssi->getGCD(), i);
		}
	}

}

bool ExactGeneratorCyclesChains::dominationAndInsertion_non_robust_cycles(list<Label>& labels, const Label& current, Label& extension) {

	if (labels.empty()) {
		extension.buildSequence(current.getSequence());
		labels.push_back(extension);
		return true;
	}

	//if the list is not empty iterate over the list to eventually check the insertion and the dominance
	list<Label>::iterator it = labels.begin();
	int comparison;

	//until the cost of the current label is smaller than the candidate
	while (it != labels.end() && (comparison = it->dominates_non_robust(extension, this->active_non_robust_duals, this->active_non_robust_cuts))) {
		if (comparison == 2) {
			return false;
		}
		++it;
	}

	//until the cost of the current label is smaller than the candidate
	while (it != labels.end() && (comparison = it->equal_non_robust(extension, this->active_non_robust_duals, this->active_non_robust_cuts))) {
		//labels are equal
		if (comparison == 2) {
			return false;
		}

		//candidate is dominated
		if (it->dominates_non_robust(extension, this->active_non_robust_duals, this->active_non_robust_cuts) == 2) {
			return false;
		}

		//considered label dominance check
		if (extension.dominates_non_robust(*it, this->active_non_robust_duals, this->active_non_robust_cuts) == 2) {
			it = labels.erase(it);
		}
		else {
			++it;
		}

	}

	extension.buildSequence(current.getSequence());
	labels.insert(it, extension);

	while (it != labels.end()) {

		//considered label dominance check
		if (extension.dominates_non_robust(*it, this->active_non_robust_duals, this->active_non_robust_cuts) == 2) {
			it = labels.erase(it);
		}
		else {
			++it;
		}

	}

	return true;

}

void ExactGeneratorCyclesChains::addExchanges_cycles(const Label& label) {
	Exchange exchange("cycle", label.getWeight(), label.getLength(), label.getSequence(), this->instance.getVertexNumber());
	//cout << exchange.toString() << endl;
	/*if (::isToPrint) {

	}*/
	/*if (::isToPrint && !check_labels_reduced_cost(label, exchange)) {
		cout << "stop\n";
	}*/
	this->solution_pool.push_back(exchange);
}

void ExactGeneratorCyclesChains::buildVertices_chains() {
	this->verticesToConsider.clear();
	this->outgoingArcsToConsider = vector<vector<int>>(this->instance.getVertexNumber(), vector<int>());
	vector<vector<bool>> arcsToDiscard(this->instance.getVertexNumber(), vector<bool>(this->instance.getVertexNumber(), false));
	vector<bool> verticesToDiscard(this->instance.getVertexNumber(), false);
	//cout << "ARCS DISCARDER:\n";
	for (int i = 0; i < this->branching_constraints->size(); i++) {
		if (this->branching_constraints->at(i)->get_name() == "ARCBRANCH" && this->branching_constraints->at(i)->get_rhs() == 0) {
			int id1 = dynamic_cast<ArcBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_items().first;
			int id2 = dynamic_cast<ArcBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_items().second;
			arcsToDiscard.at(id1).at(id2) = true;
			/*if (::isToPrint) {
				cout << "ARC DISCARDED " << id1 << "\t" << id2 << endl;
			}*/
		}
		if (this->branching_constraints->at(i)->get_name() == "VISITBRANCH" && this->branching_constraints->at(i)->get_rhs() == 0) {
			int id = dynamic_cast<VisitBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_item();
			verticesToDiscard.at(id) = true;
			/*if (::isToPrint) {
				cout << "VERTEX DISCARDED " << id << endl;
			}*/
		}
	}
	for (int i = 0; i < this->instance.getVertexNumber(); i++) {
		const Vertex* v = &this->instance.getVertices().at(i);
		if (!verticesToDiscard.at(v->getId())) {
			this->verticesToConsider.push_back(v->getId());
			vector<int> outgoing;
			/*Vertex newVertex = Vertex(*v);
			for (unordered_map<int, int>::const_iterator arc = v->getInGoingArcs().begin(); arc != v->getInGoingArcs().end(); arc++) {
				if (arcsToDiscard.at(arc->first).at(v->getId()) || verticesToDiscard.at(arc->first)) {
					newVertex.removeInGoingArc(arc->first);
				}
			}*/
			for (unordered_map<int, int>::const_iterator arc = v->getOutGoingArcs().begin(); arc != v->getOutGoingArcs().end(); arc++) {
				if (!arcsToDiscard.at(v->getId()).at(arc->first) && !verticesToDiscard.at(arc->first)) {
					outgoing.push_back(arc->first);
				}
			}
			this->outgoingArcsToConsider.at(v->getId()) = outgoing;
		}
	}
}

void ExactGeneratorCyclesChains::buildDualPrices_chains() {
	this->dualPrices = vector<vector<double>>(this->instance.getVertexNumber(), vector<double>(this->instance.getVertexNumber(), 0.0));
	for (int i = 0; i < this->instance.getVertexNumber(); i++) {
		const Vertex* v = &this->instance.getVertices().at(i);
		for (unordered_map<int, int>::const_iterator arc = v->getOutGoingArcs().begin(); arc != v->getOutGoingArcs().end(); arc++) {
			this->dualPrices.at(v->getId()).at(arc->first) -= arc->second;
			this->dualPrices.at(v->getId()).at(arc->first) += this->dual_variables->get_pi_i(arc->first);
			if (v->getType() == 'D') {
				this->dualPrices.at(v->getId()).at(arc->first) += this->dual_variables->get_beta();
			}
		}
	}
	for (int i = 0; i < this->branching_constraints->size(); i++) {
		if (this->branching_constraints->at(i)->get_name() == "ARCBRANCH") {
			int id1 = dynamic_cast<ArcBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_items().first;
			int id2 = dynamic_cast<ArcBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_items().second;
			this->dualPrices.at(id1).at(id2) += this->dual_variables->get_gamma_i(i);
		}
		else if (this->branching_constraints->at(i)->get_name() == "VISITBRANCH") {
			int id = dynamic_cast<VisitBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_item();
			/*if (::isToPrint) {
				cout << "DUAL " << id << "\t" << this->dual_variables->get_gamma_i(i) << endl;
			}*/
			for (int j = 0; j < this->instance.getVertexNumber(); j++) {
				this->dualPrices.at(j).at(id) += this->dual_variables->get_gamma_i(i);
			}
		}
		else if (this->branching_constraints->at(i)->get_name() == "EXCHANGENUMBERBRANCH") {
			/*if (::isToPrint) {
				cout << "DUAL " << this->dual_variables->get_gamma_i(i) << endl;
			}*/
			for (int j = 1; j < this->instance.getVertexNumber(); j++) {
				this->dualPrices.at(0).at(j) += this->dual_variables->get_gamma_i(i);
			}
		}
	}
	
	/*if (isToPrint) {
		string check = "DUAL PRICIES \n";
		for (int i = 0; i < this->instance.getVertexNumber(); i++) {
			const Vertex* v = &this->instance.getVertices().at(i);
			for (unordered_map<int, int>::const_iterator arc = v->getOutGoingArcs().begin(); arc != v->getOutGoingArcs().end(); arc++) {
				if (this->dualPrices.at(v->getId()).at(arc->first) != 0.0) {
					check.append("\t" + to_string(v->getId()) + "\t" + to_string(arc->first) + "\t" + to_string(arc->second) + "\t" + to_string(this->dualPrices.at(v->getId()).at(arc->first)) + "\n");
				}
			}
			
		}
		::appendToFile("fileCheck.log", check);
	}*/

	/*cout << "DUAL PRICIES \n";
		for (int i = 0; i < this->instance.getVertexNumber(); i++) {
			const Vertex* v = &this->instance.getVertices().at(i);
			for (unordered_map<int, int>::const_iterator arc = v->getOutGoingArcs().begin(); arc != v->getOutGoingArcs().end(); arc++) {
				if (this->dualPrices.at(v->getId()).at(arc->first) != 0.0) {
					cout << "\t" << v->getId() << "\t" << arc->first << "\t" << arc->second << "\t" << this->dualPrices.at(v->getId()).at(arc->first) << endl;
				}
			}
		}*/

}

void ExactGeneratorCyclesChains::compute_best_dual_price() {
	this->best_dual_price = ::OMEGA;
	for (int i = 0; i < this->verticesToConsider.size(); i++) {
		int id = this->verticesToConsider.at(i);
		for (int j = 0; j < this->outgoingArcsToConsider.at(id).size(); j++) {
			this->best_dual_price = min(this->best_dual_price, this->dualPrices.at(id).at(this->outgoingArcsToConsider.at(id).at(j)));
		}
	}
}

vector<list<Label>> ExactGeneratorCyclesChains::extendForward_chains() {

	try {

		//INITIALIZATION
		int vSize = this->verticesToConsider.size();
		vector<list<Label>> labels(this->vertices.size());
		Label sourceLabel(this->source, 0, 0, 0.0);
		sourceLabel.buildSequence({});
		vector<int> ngMemory(this->wordsNumber, 0);
		sourceLabel.setNgMemory(this->wordsNumber);
		labels.at(this->source).push_back(sourceLabel);

		unordered_set<int> altruisticCovered;

		//ITERATIONS
		bool termination = false;

		while (termination != true) {

			termination = true;

			for (int i = 0; i < vSize; i++) {

				int idV = this->verticesToConsider.at(i);
				const Vertex* v = &this->vertices.at(idV);
				//cout << v->toString(false) << "\n\tPOS " << i << endl;

				for (list<Label>::iterator label = labels.at(idV).begin(); label != labels.at(idV).end(); label++) {

					double completionBound = (this->chainsLength - label->getLength() + 1) * this->best_dual_price;

					if (!label->getIsExtended() && label->getLength() <= this->chainsLength && label->getCost() + completionBound < -::EPSILON) {

						//cout << "LABEL\n" << label->toString() << endl;

						//for (unordered_map<int, int>::const_iterator arc = v->getOutGoingArcs().begin(); arc != v->getOutGoingArcs().end(); arc++) {
						for (int j = 0; j < this->outgoingArcsToConsider.at(idV).size(); j++) {

							int idW = this->outgoingArcsToConsider.at(idV).at(j);
							const Vertex* w = &this->vertices.at(idW);
							//cout << "TO REACH\n" << w->toString(false) << endl;

							if (!label->isVisited(w->getWord(), w->getBitKey())) {

								double redCost = label->getCost() + this->dualPrices.at(idV).at(idW);
								Label extension(idW, label->getLength() + 1, label->getWeight() + v->getOutGoingArcs().at(idW), redCost);
								extension.buildNgMemory(label->getNgMemory(), w->getNgSet(), w->getWord(), w->getBitKey());

								//CHECK DOMINANCE+INSERT IN LIST
								//cout << "EXTENSION\n" << extension.toString() << endl;
								bool isInserted = dominationAndInsertion_chains(labels.at(idW), *label, extension);
								if (isInserted) {
									if (extension.getLength() > 1) {
										if (::strictly_less(extension.getCost(), this->value_chains)) {
											this->optimalLabel_chains = extension;
											this->value_chains = extension.getCost();
										}
										if (extension.getCost() < -::EPSILON) {
											this->favourablyPricedVariablesCounter++;
											int altruistic = extension.getSequence().at(1);
											altruisticCovered.insert(altruistic);
											if (altruisticCovered.size() >= this->instance.getAltruisticDonorsNumber()) {
												this->is_early_terminated = true;
												return labels;
											}
										}
										if (this->favourablyPricedVariablesCounter > ::PROMISINGLABELSPERITERATION) {
											this->is_early_terminated = true;
											return labels;
										}
									}

									termination = false;
								}

							}

						}

					}

					label->setIsExtended(true);

				}

			}

		}

		return labels;

	}
	catch (...) {
		cout << "[ExactGenerator] - Error during optimization" << endl;
	}

}

vector<list<Label>> ExactGeneratorCyclesChains::extendForward_non_robust_chains() {

	try {

		//INITIALIZATION
		int vSize = this->verticesToConsider.size();
		vector<list<Label>> labels(this->vertices.size());
		Label sourceLabel(this->source, 0, 0, 0.0);
		sourceLabel.buildSequence({});
		vector<int> ngMemory(this->wordsNumber, 0);
		sourceLabel.setActive_SSI(this->active_non_robust_cuts.size());
		sourceLabel.setNgMemory(this->wordsNumber);
		labels.at(this->source).push_back(sourceLabel);

		//ITERATIONS
		bool termination = false;

		while (termination != true) {

			termination = true;

			for (int i = 0; i < vSize; i++) {

				int idV = this->verticesToConsider.at(i);
				const Vertex* v = &this->vertices.at(idV);
				//if (::isToPrint) {
				//	//::appendToFile("label_check.log", "FIRST V\n" + v->toString(false) + "\n");
				//	cout << "START\n" << v->toString(false) << "\n";
				//}

				for (list<Label>::iterator label = labels.at(idV).begin(); label != labels.at(idV).end(); label++) {

					if (!label->getIsExtended() && label->getLength() <= this->chainsLength) {

						//if (::isToPrint) {
						//	//::appendToFile("label_check.log", "LABEL TO EXTEND\n" + label->toString() + "\n");
						//	cout << "LABEL TO EXTEND\n" << label->toString() << "\n";
						//}

						for (int j = 0; j < this->outgoingArcsToConsider.at(idV).size(); j++) {

							int idW = this->outgoingArcsToConsider.at(idV).at(j);
							const Vertex* w = &this->vertices.at(idW);
							//if (::isToPrint) {
							//	//::appendToFile("label_check.log", "REACHED\n" + w->toString(false) + "\n");
							//	cout << "REACHED\n" << w->toString(false) << "\n";
							//	if (w->getId() == 434) {
							//		cout << "gdkk\n";
							//	}
							//}

							if (!label->isVisited(w->getWord(), w->getBitKey())) {

								double redCost = label->getCost() + this->dualPrices.at(idV).at(idW);
								Label extension(idW, label->getLength() + 1, label->getWeight() + v->getOutGoingArcs().at(idW), redCost);
								extension.buildNgMemory(label->getNgMemory(), w->getNgSet(), w->getWord(), w->getBitKey());
								extension.setActive_SSI(label->getActive_SSI());
								manage_extension_non_robust_cuts_chains(extension, idW, w->getWord(), w->getBitKey());

								//if (::isToPrint) {
								//	//::appendToFile("label_check.log", "EXTENDED\n" + extension.toString() + "\n");
								//	cout << "EXTENDED\n" << extension.toString() << endl;
								//}

								//CHECK DOMINANCE+INSERT IN LIST

								bool isInserted = dominationAndInsertion_non_robust_chains(labels.at(idW), *label, extension);
								if (isInserted) {
									if (extension.getLength() > 1) {
										if (::strictly_less(extension.getCost(), this->value_chains)) {
											this->optimalLabel_chains = extension;
											this->value_chains = extension.getCost();
										}
										if (extension.getCost() < -::EPSILON) {
											this->favourablyPricedVariablesCounter++;
										}
										if (this->favourablyPricedVariablesCounter > ::PROMISINGLABELSPERITERATION) {
											this->is_early_terminated = true;
											return labels;
										}
									}

									termination = false;
								}
								//cout << "INSERTED? " << isInserted << endl;

							}

						}

					}

					label->setIsExtended(true);

				}

			}

		}

		return labels;

	}
	catch (...) {
		cout << "[ExactGenerator] - Error during optimization NON ROBUST" << endl;
	}

}

bool ExactGeneratorCyclesChains::dominationAndInsertion_chains(list<Label>& labels, const Label& current, Label& extension) {

	if (labels.empty()) {
		extension.buildSequence(current.getSequence());
		labels.push_back(extension);
		return true;
	}

	//if the list is not empty iterate over the list to eventually check the insertion and the dominance
	list<Label>::iterator it = labels.begin();
	int comparison;

	//until the cost of the current label is smaller than the candidate
	while (it != labels.end() && (comparison = ((*it) < extension))) {
		if (comparison == 2) {
			return false;
		}
		++it;
	}

	//until the cost of the current label is smaller than the candidate
	while (it != labels.end() && (comparison = ((*it) == extension))) {
		//labels are equal
		if (comparison == 2) {
			return false;
		}

		//candidate is dominated
		if (((*it) < extension) == 2) {
			return false;
		}

		//considered label dominance check
		if ((extension < (*it)) == 2) {
			it = labels.erase(it);
		}
		else {
			++it;
		}

	}

	extension.buildSequence(current.getSequence());
	labels.insert(it, extension);

	while (it != labels.end()) {

		//considered label dominance check
		if ((extension < (*it)) == 2) {
			it = labels.erase(it);
		}
		else {
			++it;
		}

	}

	return true;

}

void ExactGeneratorCyclesChains::manage_extension_non_robust_cuts_chains(Label& extension, const int& vertex_id, const int& vertex_word, const int& vertex_bit) {

	for (int i = 0; i < this->active_non_robust_cuts.size(); i++) {
		int cut_id = this->active_non_robust_cuts.at(i);
		const SubsetRowConstraint<GRBConstr>* ssi = dynamic_cast<SubsetRowConstraint<GRBConstr>*>(this->cut_constraints->at(cut_id));
		if (ssi->is_vertex_in_subset(vertex_word, vertex_bit)) {
			/*if (::isToPrint) {
			cout << ssi->toString() << endl;
			}*/
			int multiplier = ssi->get_multiplier(vertex_id);
			extension.addNonRobustDual(this->active_non_robust_duals.at(i), multiplier, ssi->getGCD(), i);
		}
	}

}

bool ExactGeneratorCyclesChains::dominationAndInsertion_non_robust_chains(list<Label>& labels, const Label& current, Label& extension) {

	if (labels.empty()) {
		extension.buildSequence(current.getSequence());
		labels.push_back(extension);
		return true;
	}

	//if the list is not empty iterate over the list to eventually check the insertion and the dominance
	list<Label>::iterator it = labels.begin();
	int comparison;

	//until the cost of the current label is smaller than the candidate
	while (it != labels.end() && (comparison = it->dominates_non_robust(extension, this->active_non_robust_duals, this->active_non_robust_cuts))) {
		if (comparison == 2) {
			return false;
		}
		++it;
	}

	//until the cost of the current label is smaller than the candidate
	while (it != labels.end() && (comparison = it->equal_non_robust(extension, this->active_non_robust_duals, this->active_non_robust_cuts))) {
		//labels are equal
		if (comparison == 2) {
			return false;
		}

		//candidate is dominated
		if (it->dominates_non_robust(extension, this->active_non_robust_duals, this->active_non_robust_cuts) == 2) {
			return false;
		}

		//considered label dominance check
		if (extension.dominates_non_robust(*it, this->active_non_robust_duals, this->active_non_robust_cuts) == 2) {
			it = labels.erase(it);
		}
		else {
			++it;
		}

	}

	extension.buildSequence(current.getSequence());
	labels.insert(it, extension);

	while (it != labels.end()) {

		//considered label dominance check
		if (extension.dominates_non_robust(*it, this->active_non_robust_duals, this->active_non_robust_cuts) == 2) {
			it = labels.erase(it);
		}
		else {
			++it;
		}

	}

	return true;

}

void ExactGeneratorCyclesChains::addExchanges_chains(const Label& label, const bool& areSubpathsAdded) {
	Exchange exchange("chain", label.getWeight(), label.getLength(), label.getSequence(), this->instance.getVertexNumber());
	//cout << exchange.toString() << endl;
	/*if (::isToPrint) {
		
	}*/
	/*if (::isToPrint && !check_labels_reduced_cost(label, exchange)) {
		cout << "stop\n";
	}*/
	this->solution_pool.push_back(exchange);
	if (areSubpathsAdded) {
		for (int i = 3; i < label.getSequence().size(); i++) {
			vector<int> subSequence;
			int weight = 0;
			int length = 0;
			for (int j = 0; j < i; j++) {
				subSequence.push_back(label.getSequence().at(j));
			}
			for (int j = 0; j < subSequence.size() - 1; j++) {
				length++;
				weight += this->vertices.at(subSequence.at(j)).getOutGoingArcs().at(subSequence.at(j + 1));
			}
			Exchange subExchange("chain", weight, length, subSequence, this->instance.getVertexNumber());
			//cout << subExchange.toString() << endl;
			this->solution_pool.push_back(subExchange);
		}
	}
}

bool ExactGeneratorCyclesChains::dominationAndInsertion(list<Label>& labels, const Label& current, Label& extension) {

	if (labels.empty()) {
		extension.buildSequence(current.getSequence());
		labels.push_back(extension);
		return true;
	}

	//if the list is not empty iterate over the list to eventually check the insertion and the dominance
	list<Label>::iterator it = labels.begin();
	int comparison;

	//until the cost of the current label is smaller than the candidate
	while (it != labels.end() && (comparison = ((*it) < extension))) {
		if (comparison == 2) {
			return false;
		}
		++it;
	}

	//until the cost of the current label is smaller than the candidate
	while (it != labels.end() && (comparison = ((*it) == extension))) {
		//labels are equal
		if (comparison == 2) {
			return false;
		}

		//candidate is dominated
		if (((*it) < extension) == 2) {
			return false;
		}

		//considered label dominance check
		if ((extension < (*it)) == 2) {
			it = labels.erase(it);
		}
		else {
			++it;
		}

	}

	extension.buildSequence(current.getSequence());
	labels.insert(it, extension);

	while (it != labels.end()) {

		//considered label dominance check
		if ((extension < (*it)) == 2) {
			it = labels.erase(it);
		}
		else {
			++it;
		}

	}

	return true;

}

vector<list<Label>> ExactGeneratorCyclesChains::extendForward(const int& source) {

	try {

		//INITIALIZATION
		int vSize = this->sourcesToConsider.size();
		vector<list<Label>> labels(this->vertices.size());
		Label sourceLabel(source, 0, 0, 0.0);
		sourceLabel.buildSequence({});
		vector<int> ngMemory(this->wordsNumber, 0);
		sourceLabel.setNgMemory(this->wordsNumber);
		labels.at(source).push_back(sourceLabel);

		//ITERATIONS
		bool termination = false;

		while (termination != true) {

			termination = true;

			for (int i = 0; i < vSize; i++) {

				int idV = this->sourcesToConsider.at(i);
				const Vertex* v = &this->vertices.at(idV);
				//cout << v->toString(false) << "\n\tPOS " << i << endl;

				for (list<Label>::iterator label = labels.at(idV).begin(); label != labels.at(idV).end(); label++) {

					if (!label->getIsExtended() && label->getLength() < this->cyclesLength) {

						//cout << "LABEL\n" << label->toString() << endl;

						//for (unordered_map<int, int>::const_iterator arc = v->getOutGoingArcs().begin(); arc != v->getOutGoingArcs().end(); arc++) {
						for (int j = 0; j < this->outgoingArcsToConsider.at(idV).size(); j++) {

							int idW = this->outgoingArcsToConsider.at(idV).at(j);
							const Vertex* w = &this->vertices.at(idW);
							//cout << "TO REACH\n" << w->toString(false) << endl;

							if (!label->isVisited(w->getWord(), w->getBitKey())) {

								double redCost = label->getCost() + this->dualPrices.at(idV).at(idW);
								Label extension(idW, label->getLength() + 1, label->getWeight() + v->getOutGoingArcs().at(idW), redCost);
								extension.buildNgMemory(label->getNgMemory(), w->getNgSet(), w->getWord(), w->getBitKey());

								//CHECK DOMINANCE+INSERT IN LIST
								bool isInserted = dominationAndInsertion(labels.at(idW), *label, extension);
								//cout << extension.toString() << endl;
								if (isInserted) {
									if (w->getId() == source && ::strictly_less(extension.getCost(), this->valuePerPricing) && extension.getLength() > 1) {
										this->optimalLabel = extension;
										this->valuePerPricing = extension.getCost();
									}
									termination = false;
								}

							}

						}

					}

					label->setIsExtended(true);

				}

			}

		}


		/*for (int i = 0; i < labels.size(); i++) {
			cout << "\n\n\nLABELS OF " << i << "\n";
			for (list<Label>::const_iterator it = labels.at(i).begin(); it != labels.at(i).end(); it++) {
				cout << it->toString() << endl;
			}
		}
		*/
		return labels;

	}
	catch (...) {
		cout << "[ExactGeneratorCycles] - Error during optimization" << endl;
	}

}

void ExactGeneratorCyclesChains::buildVertices_cycles() {
	this->verticesToConsider.clear();
	this->sourcesToConsider.clear();
	this->outgoingArcsToConsider = vector<vector<int>>(this->instance.getVertexNumber(), vector<int>());
	vector<vector<bool>> arcsToDiscard(this->instance.getVertexNumber(), vector<bool>(this->instance.getVertexNumber(), false));
	vector<bool> verticesToDiscard(this->instance.getVertexNumber(), false);
	//cout << "ARCS DISCARDER:\n";
	for (int i = 0; i < this->branching_constraints->size(); i++) {
		if (this->branching_constraints->at(i)->get_name() == "ARCBRANCH" && this->branching_constraints->at(i)->get_rhs() == 0) {
			int id1 = dynamic_cast<ArcBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_items().first;
			int id2 = dynamic_cast<ArcBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_items().second;
			arcsToDiscard.at(id1).at(id2) = true;
			/*if (::isToPrint) {
				cout << "ARC DISCARDED " << id1 << "\t" << id2 << endl;
			}*/
		}
		if (this->branching_constraints->at(i)->get_name() == "VISITBRANCH" && this->branching_constraints->at(i)->get_rhs() == 0) {
			int id = dynamic_cast<VisitBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_item();
			verticesToDiscard.at(id) = true;
			/*if (::isToPrint) {
				cout << "VERTEX DISCARDED " << id << endl;
			}*/
		}
	}
	for (int i = 0; i < this->instance.getVertexNumber(); i++) {
		const Vertex* v = &this->instance.getVertices().at(i);
		if (!verticesToDiscard.at(v->getId())) {
			this->verticesToConsider.push_back(v->getId());
			if (v->getType() == 'I') {
				this->sourcesToConsider.push_back(v->getId());
			}
			vector<int> outgoing;
			/*Vertex newVertex = Vertex(*v);
			for (unordered_map<int, int>::const_iterator arc = v->getInGoingArcs().begin(); arc != v->getInGoingArcs().end(); arc++) {
				if (arcsToDiscard.at(arc->first).at(v->getId()) || verticesToDiscard.at(arc->first)) {
					newVertex.removeInGoingArc(arc->first);
				}
			}*/
			for (unordered_map<int, int>::const_iterator arc = v->getOutGoingArcs().begin(); arc != v->getOutGoingArcs().end(); arc++) {
				if (!arcsToDiscard.at(v->getId()).at(arc->first) && !verticesToDiscard.at(arc->first)) {
					outgoing.push_back(arc->first);
				}
			}
			this->outgoingArcsToConsider.at(v->getId()) = outgoing;
		}
	}
}

double ExactGeneratorCyclesChains::add_sri_dual_prices(const Label& label) const {

	double cost = label.getCost();
	for (int i = 0; i < this->active_non_robust_cuts.size(); i++) {
		int cut_id = this->active_non_robust_cuts.at(i);
		const SubsetRowConstraint<GRBConstr>* ssi = dynamic_cast<SubsetRowConstraint<GRBConstr>*>(this->cut_constraints->at(cut_id));
		double coeff = 0.0;
		//cout << ssi->toString() << endl;
		for (int j = 0; j < ssi->get_subset().size(); j++) {
			coeff += (ssi->get_multipliers().at(j) * label.get_visits_number(ssi->get_subset().at(j)));
		}
		coeff /= ssi->getGCD();
		coeff += EPSILON;
		coeff = floor(coeff);
		cost += (coeff * this->active_non_robust_duals.at(i));

	}
	return cost;

}

double ExactGeneratorCyclesChains::priceVariable(const Exchange* exchange) {

	double cost = this->dual_variables->get_beta();
	for (int i = 0; i < exchange->getSequence().size() - 1; i++) {
		const Vertex* v = &this->vertices.at(exchange->getSequence().at(i));
		cost -= v->getOutGoingArcs().at(exchange->getSequence().at(i + 1));
	}

	for (int i = 1; i < exchange->getSequence().size(); i++) {
		const Vertex* v = &this->vertices.at(exchange->getSequence().at(i));
		cost += this->dual_variables->get_pi_i(v->getId());
	}

	for (int i = 0; i < this->branching_constraints->size(); i++) {
		double rhs = this->branching_constraints->at(i)->get_rhs();
		double dual = this->dual_variables->get_gamma_i(i);
		int id1 = dynamic_cast<ArcBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_items().first;
		int id2 = dynamic_cast<ArcBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_items().second;
		cost += (dual * exchange->getTraverses(id1, id2));
	}

	for (int i = 0; i < this->cut_constraints->size(); i++) {
		const SubsetRowConstraint<GRBConstr>* ssi = dynamic_cast<SubsetRowConstraint<GRBConstr>*>(this->cut_constraints->at(i));
		double dual = this->dual_variables->get_sigma_i(i);
		int visits = 0;
		for (int j = 0; j < ssi->get_subset().size(); j++) {
			int id = ssi->get_subset().at(j);
			visits += ssi->get_multiplier(id) * exchange->getVisit(id);
		}
		double cc = visits * ssi->getGCD();
		cc += ::EPSILON;
		cc = floor(cc);
		cost += (cc * dual);
		if (cc > EPSILON && dual > EPSILON) {
			cout << ssi->toString() << "\t" << dual << "\t" << cc << endl;
		}
	}

	return cost;

}