/* $Id: CutGen.hpp 508 2011-02-15 21:52:44Z pbelotti $
 *
 * Name:    CutGen.hpp
 * Author:  Andrea Qualizza
 * Purpose: utilities for sdpcuts
 *
 * This file is licensed under the Eclipse Public License (EPL)
 */

#ifndef SDPCUTGEN2_HPP
#define SDPCUTGEN2_HPP

#include "CglCutGenerator.hpp"
#include "OsiSolverInterface.hpp"
#include "OsiXxxSolverInterface.hpp"
#include "Heuristics.hpp"
#include "misc_util.hpp"

#define SPARSIFY_MAX_CARD  10000
#define SPARSIFY_OLD_DELTA 0.50
#define SPARSIFY_NEW_DELTA 0.50
#define WISE_SPARSIFY_GAP  0.0001
#define SPARSIFY_OLD_NZ_THRESHOLD 0.50
#define SPARSIFY_NEW_NZ_THRESHOLD 0.70

#define indexQ(i,j,n) ((n) + (i) * (2*(n)-1-(i)) / 2 + (j))



struct sparsify_trace {
		int *generated_cuts1; int *generated_cuts2;
		int *duplicate1; int *duplicate2; 
		double *sparsifytime1; double *sparsifytime2; 
		double *boundtime1; double *boundtime2; 
		double *nzmean1; double *nzmean2; 
		double *nzmin1; double *nzmin2;
		double *nzmax1; double *nzmax2;  
		int *decomp1; int *decomp2; 
		double *single_column_sparsity_mean1; double *single_column_sparsity_mean2; 
		int *single_column_sparsity_max1;int *single_column_sparsity_max2; 
		int *single_column_sparsity_min1;int *single_column_sparsity_min2; 
		double *column_pair_sparsity_mean1; double *column_pair_sparsity_mean2;
		int *column_pair_sparsity_max1;int *column_pair_sparsity_max2;
		int *column_pair_sparsity_min1;int *column_pair_sparsity_min2;
		double *top_cuts_mean_violation1; double *top_cuts_mean_violation2;
		double *bounds1;
		double *times1;
		double *bounds2;
		double *times2;
		int *iterations;
};


// Class to separate cuts

class CutGen: public CglCutGenerator {

private:

	int n_;			// number of variables x_i (involved in quadratic terms)
	int t_;			// number of variables y_i (NOT involved in quadratic terms)
	int N_;			// number of variables x_i + X_ij  (= n*(n+3)/2)
	int cons_;		// number of constraints in the original problem
	double objConst_;	// constant to be added to the objective function value
	double *b_;		// objective function coefficients of the variables x_i
	double *c_;		// objective function coefficients of the variables y_i
	double **Q_;		// objective function coefficients of the variables X_ij
	double **origMat_;	// original problem constraints (linearized)
	double *origRhs_;	// original problem RHS
	char *origSense_;	// original problem sense
	double *xlb_;		// original problem lower bounds for x_i
	double *xub_;		// original problem upper bounds for x_i
	double *ylb_;		// original problem lower bounds for y_i
	double *yub_;		// original problem upper bounds for y_i
	OsiSolverInterface *si_;// pointer to the main problem
	Heuristics *heuristics_;// module to create feasible heuristic solutions

	Timer *globaltimer_;	//global timer (paused during checks/trace etc...)

	Tracer *tracer_;	//global tracer

	int *seed_;		// random seed used by random cut removal

	int _iter;		//stores current iteration index (can be used to disable some cut generators)

//parameters
	int max_nb_cuts; 	// maximum # of cuts to generate
	
	bool removeduplicates_;	// checks and removes duplicate cuts generated by sparsify

	sparsify_trace spartrace;


public:

	// constructor
	//  SdpCutGen  (int, double *, double **);
	CutGen(const int,const int,const int,const double,const double*,const double*,const double**,const double**,const double*,const char*,const double*,const double*,const double*,const double*,OsiSolverInterface *si, Timer *globaltimer, Tracer *tracer);
	
	// destructor
	~CutGen ();
	
	// clone 
	CutGen *clone () const
	{return new CutGen (*this);}
	

	// return sparsify comparison trace structure
	sparsify_trace get_sparsify_trace() { return spartrace;}

	// return current lower (primal) bound
	double currObj() const {return heuristics_->currObj();}
	
	// return best lower (primal) bound
	double bestObj() const {return heuristics_->bestObj();}

	// return best lower (primal) solution
	double* bestSol() const {return heuristics_->bestSol();}

	// set max_nb_cuts
	void set_max_nb_cuts(const int max_c) { 
		if(max_c > 0) max_nb_cuts = max_c;
		else {
			printf("### ERROR: SdpCutGen::set_max_nb_cuts(): max_c: %d\n", max_c);
			exit(1);
		}
	}
	
	// the main cut generator
	void generateCuts (const OsiSolverInterface &,  OsiCuts &, 
			   const CglTreeInfo = CglTreeInfo ()) const;

	void updateSol();


	void setIter(int iter) {
		_iter = iter;
	}


private:
	void compareSparsify(const OsiSolverInterface &si,int n, int m, const double *sol, double *z, double *w,FILE *out) const;


	void sparsify2(const int n,
			 const double *sol, double **sparse_v_mat,
			 int *card_v_mat, int min_nz, int *evdec_num) const;

	void genSDPcut (const OsiSolverInterface &si,
			            OsiCuts &cs, double *v1, double *v2, bool checkduplicates,int *duplicate_cuts) const;


	void additionalSDPcuts(const OsiSolverInterface 
				&si,OsiCuts &cs, int np, const double *A, 
				const double *vector, int *duplicate_cuts) const;



	void zero_comp(const int ind_i, const double delta,
			  const int np, const int *selected,
			  int *loc_selected, 
			  int *ploc_card_selected, int *ploc_card_new_selected, 
			  double *ploc_lhs, 
			  double *locmargin, double **locmat, 
			  const double *sol, double *locv, 
			  const int evidx, bool wise, int *evdec_num, double *recomp_gap, double *threshold) const;
	void zero_valid_delta(const int np, const int *order,
				 const int * selected,
				 const int min_card_new_selected,
				 const double min_delta, const int start_point, 
				 const int curr_i, 
				 int *loc_selected, 
				 int *ploc_card_selected, 
				 int *ploc_card_new_selected, 
				 double *ploc_lhs, 
				 double *locmargin, double **locmat, 
				 int *pnchanged,
				 const double *sol, double *locv, 
				 const int evidx, bool wise,double *recomp_gap, double *threshold,
			         int *pcard_selected,
			         int *pnew_selected,
			         int *trace_bin, const int trace_bin_size,
			         double **sparse_v_mat,
			         int *pcard_v_mat,
			         const int init_card_selected, int *has_init_vect,
			       int *evdec_num) const;
	void zero_selected(const int np, const int *order,
			      const int *selected,
			      const int min_card_new_selected,
			      const double min_delta, const int start_point,
			      const int curr_i, 
			      int *loc_selected, int *ploc_card_selected, 
			      int *ploc_card_new_selected, 
			      double *ploc_lhs, 
			      double *locmargin, double **locmat, 
			      int *pnchanged,
			      const double *sol, double *locv, 
			      const int evidx, bool wise,double *recomp_gap, double *threshold,
			      int *pcard_selected,
			      int *pnew_selected,
			      int *trace_bin, const int trace_bin_size,
			      double **sparse_v_mat,
			      int *pcard_v_mat,
			      const int init_card_selected, int *has_init_vect,
			       int *evdec_num) const;
	void zero_pos_delta(const int np, const int *order,
			       const int *selected,
			       const int min_card_new_selected,
			       const int start_point, const int curr_i, 
			       int *loc_selected, int *ploc_card_selected, 
			       int *ploc_card_new_selected, 
			       double *ploc_lhs, 
			       double *locmargin, double **locmat, 
			       int *pnchanged, 
			       const double *sol, double *locv, 
			       const int evidx, bool wise,double *recomp_gap, double *threshold,
			       int *pcard_selected,
			       int *pnew_selected,
			       int *trace_bin, const int trace_bin_size,
			       double **sparse_v_mat,
			       int *pcard_v_mat,
			       const int init_card_selected, int *has_init_vect,
			       int *evdec_num) const;
	void add_v_cut(const int np,
			  const int *loc_selected, 
			  const int loc_card_selected,
			  const double *locv,
			  const int init_card_selected, int *has_init_vect,
			  int *selected, int *pcard_selected,
			  int *pnew_selected,
			  int *trace_bin, const int trace_bin_size,
			  double **sparse_v_mat,
			  int *pcard_v_mat) const;
	void update_sparsify_structures(const int np, 
			  const double *sol, double *v,double* margin, 
			  double** mat, double *lhs, const int *zeroed, 
			  int evidx, bool decompose, int *evdec_num) const;

	void sparsify(const int evidx, const double eigen_val, 
			 const double *v, const int n, 
			 const double *sol, double **sparse_v_mat,
			 int *card_v_mat , double *work_ev, bool wise, int *evdec_num) const;
	void sparsify_new(const int evidx, const double eigen_val, 
			 const double *v, const int n, 
			 const double *sol, double **sparse_v_mat,
			 int *card_v_mat , double *work_ev, bool wise, int *evdec_num) const;

	void myremoveBestOneRowCol(double *matrix, int n, int running_n, int min_nz,bool *del_idx, double **sparse_v_mat, int *card_v_mat , int *evdec_num) const;
};

#endif
