/home/coin/SVN-release/OS-2.4.0/Couenne/src/cut/sdpcuts/CutGen.hpp

Go to the documentation of this file.
00001 /* $Id: CutGen.hpp 508 2011-02-15 21:52:44Z pbelotti $
00002  *
00003  * Name:    CutGen.hpp
00004  * Author:  Andrea Qualizza
00005  * Purpose: utilities for sdpcuts
00006  *
00007  * This file is licensed under the Eclipse Public License (EPL)
00008  */
00009 
00010 #ifndef SDPCUTGEN2_HPP
00011 #define SDPCUTGEN2_HPP
00012 
00013 #include "CglCutGenerator.hpp"
00014 #include "OsiSolverInterface.hpp"
00015 #include "OsiXxxSolverInterface.hpp"
00016 #include "Heuristics.hpp"
00017 #include "misc_util.hpp"
00018 
00019 #define SPARSIFY_MAX_CARD  10000
00020 #define SPARSIFY_OLD_DELTA 0.50
00021 #define SPARSIFY_NEW_DELTA 0.50
00022 #define WISE_SPARSIFY_GAP  0.0001
00023 #define SPARSIFY_OLD_NZ_THRESHOLD 0.50
00024 #define SPARSIFY_NEW_NZ_THRESHOLD 0.70
00025 
00026 #define indexQ(i,j,n) ((n) + (i) * (2*(n)-1-(i)) / 2 + (j))
00027 
00028 
00029 
00030 struct sparsify_trace {
00031                 int *generated_cuts1; int *generated_cuts2;
00032                 int *duplicate1; int *duplicate2; 
00033                 double *sparsifytime1; double *sparsifytime2; 
00034                 double *boundtime1; double *boundtime2; 
00035                 double *nzmean1; double *nzmean2; 
00036                 double *nzmin1; double *nzmin2;
00037                 double *nzmax1; double *nzmax2;  
00038                 int *decomp1; int *decomp2; 
00039                 double *single_column_sparsity_mean1; double *single_column_sparsity_mean2; 
00040                 int *single_column_sparsity_max1;int *single_column_sparsity_max2; 
00041                 int *single_column_sparsity_min1;int *single_column_sparsity_min2; 
00042                 double *column_pair_sparsity_mean1; double *column_pair_sparsity_mean2;
00043                 int *column_pair_sparsity_max1;int *column_pair_sparsity_max2;
00044                 int *column_pair_sparsity_min1;int *column_pair_sparsity_min2;
00045                 double *top_cuts_mean_violation1; double *top_cuts_mean_violation2;
00046                 double *bounds1;
00047                 double *times1;
00048                 double *bounds2;
00049                 double *times2;
00050                 int *iterations;
00051 };
00052 
00053 
00054 // Class to separate cuts
00055 
00056 class CutGen: public CglCutGenerator {
00057 
00058 private:
00059 
00060         int n_;                 // number of variables x_i (involved in quadratic terms)
00061         int t_;                 // number of variables y_i (NOT involved in quadratic terms)
00062         int N_;                 // number of variables x_i + X_ij  (= n*(n+3)/2)
00063         int cons_;              // number of constraints in the original problem
00064         double objConst_;       // constant to be added to the objective function value
00065         double *b_;             // objective function coefficients of the variables x_i
00066         double *c_;             // objective function coefficients of the variables y_i
00067         double **Q_;            // objective function coefficients of the variables X_ij
00068         double **origMat_;      // original problem constraints (linearized)
00069         double *origRhs_;       // original problem RHS
00070         char *origSense_;       // original problem sense
00071         double *xlb_;           // original problem lower bounds for x_i
00072         double *xub_;           // original problem upper bounds for x_i
00073         double *ylb_;           // original problem lower bounds for y_i
00074         double *yub_;           // original problem upper bounds for y_i
00075         OsiSolverInterface *si_;// pointer to the main problem
00076         Heuristics *heuristics_;// module to create feasible heuristic solutions
00077 
00078         Timer *globaltimer_;    //global timer (paused during checks/trace etc...)
00079 
00080         Tracer *tracer_;        //global tracer
00081 
00082         int *seed_;             // random seed used by random cut removal
00083 
00084         int _iter;              //stores current iteration index (can be used to disable some cut generators)
00085 
00086 //parameters
00087         int max_nb_cuts;        // maximum # of cuts to generate
00088         
00089         bool removeduplicates_; // checks and removes duplicate cuts generated by sparsify
00090 
00091         sparsify_trace spartrace;
00092 
00093 
00094 public:
00095 
00096         // constructor
00097         //  SdpCutGen  (int, double *, double **);
00098         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);
00099         
00100         // destructor
00101         ~CutGen ();
00102         
00103         // clone 
00104         CutGen *clone () const
00105         {return new CutGen (*this);}
00106         
00107 
00108         // return sparsify comparison trace structure
00109         sparsify_trace get_sparsify_trace() { return spartrace;}
00110 
00111         // return current lower (primal) bound
00112         double currObj() const {return heuristics_->currObj();}
00113         
00114         // return best lower (primal) bound
00115         double bestObj() const {return heuristics_->bestObj();}
00116 
00117         // return best lower (primal) solution
00118         double* bestSol() const {return heuristics_->bestSol();}
00119 
00120         // set max_nb_cuts
00121         void set_max_nb_cuts(const int max_c) { 
00122                 if(max_c > 0) max_nb_cuts = max_c;
00123                 else {
00124                         printf("### ERROR: SdpCutGen::set_max_nb_cuts(): max_c: %d\n", max_c);
00125                         exit(1);
00126                 }
00127         }
00128         
00129         // the main cut generator
00130         void generateCuts (const OsiSolverInterface &,  OsiCuts &, 
00131                            const CglTreeInfo = CglTreeInfo ()) const;
00132 
00133         void updateSol();
00134 
00135 
00136         void setIter(int iter) {
00137                 _iter = iter;
00138         }
00139 
00140 
00141 private:
00142         void compareSparsify(const OsiSolverInterface &si,int n, int m, const double *sol, double *z, double *w,FILE *out) const;
00143 
00144 
00145         void sparsify2(const int n,
00146                          const double *sol, double **sparse_v_mat,
00147                          int *card_v_mat, int min_nz, int *evdec_num) const;
00148 
00149         void genSDPcut (const OsiSolverInterface &si,
00150                                     OsiCuts &cs, double *v1, double *v2, bool checkduplicates,int *duplicate_cuts) const;
00151 
00152 
00153         void additionalSDPcuts(const OsiSolverInterface 
00154                                 &si,OsiCuts &cs, int np, const double *A, 
00155                                 const double *vector, int *duplicate_cuts) const;
00156 
00157 
00158 
00159         void zero_comp(const int ind_i, const double delta,
00160                           const int np, const int *selected,
00161                           int *loc_selected, 
00162                           int *ploc_card_selected, int *ploc_card_new_selected, 
00163                           double *ploc_lhs, 
00164                           double *locmargin, double **locmat, 
00165                           const double *sol, double *locv, 
00166                           const int evidx, bool wise, int *evdec_num, double *recomp_gap, double *threshold) const;
00167         void zero_valid_delta(const int np, const int *order,
00168                                  const int * selected,
00169                                  const int min_card_new_selected,
00170                                  const double min_delta, const int start_point, 
00171                                  const int curr_i, 
00172                                  int *loc_selected, 
00173                                  int *ploc_card_selected, 
00174                                  int *ploc_card_new_selected, 
00175                                  double *ploc_lhs, 
00176                                  double *locmargin, double **locmat, 
00177                                  int *pnchanged,
00178                                  const double *sol, double *locv, 
00179                                  const int evidx, bool wise,double *recomp_gap, double *threshold,
00180                                  int *pcard_selected,
00181                                  int *pnew_selected,
00182                                  int *trace_bin, const int trace_bin_size,
00183                                  double **sparse_v_mat,
00184                                  int *pcard_v_mat,
00185                                  const int init_card_selected, int *has_init_vect,
00186                                int *evdec_num) const;
00187         void zero_selected(const int np, const int *order,
00188                               const int *selected,
00189                               const int min_card_new_selected,
00190                               const double min_delta, const int start_point,
00191                               const int curr_i, 
00192                               int *loc_selected, int *ploc_card_selected, 
00193                               int *ploc_card_new_selected, 
00194                               double *ploc_lhs, 
00195                               double *locmargin, double **locmat, 
00196                               int *pnchanged,
00197                               const double *sol, double *locv, 
00198                               const int evidx, bool wise,double *recomp_gap, double *threshold,
00199                               int *pcard_selected,
00200                               int *pnew_selected,
00201                               int *trace_bin, const int trace_bin_size,
00202                               double **sparse_v_mat,
00203                               int *pcard_v_mat,
00204                               const int init_card_selected, int *has_init_vect,
00205                                int *evdec_num) const;
00206         void zero_pos_delta(const int np, const int *order,
00207                                const int *selected,
00208                                const int min_card_new_selected,
00209                                const int start_point, const int curr_i, 
00210                                int *loc_selected, int *ploc_card_selected, 
00211                                int *ploc_card_new_selected, 
00212                                double *ploc_lhs, 
00213                                double *locmargin, double **locmat, 
00214                                int *pnchanged, 
00215                                const double *sol, double *locv, 
00216                                const int evidx, bool wise,double *recomp_gap, double *threshold,
00217                                int *pcard_selected,
00218                                int *pnew_selected,
00219                                int *trace_bin, const int trace_bin_size,
00220                                double **sparse_v_mat,
00221                                int *pcard_v_mat,
00222                                const int init_card_selected, int *has_init_vect,
00223                                int *evdec_num) const;
00224         void add_v_cut(const int np,
00225                           const int *loc_selected, 
00226                           const int loc_card_selected,
00227                           const double *locv,
00228                           const int init_card_selected, int *has_init_vect,
00229                           int *selected, int *pcard_selected,
00230                           int *pnew_selected,
00231                           int *trace_bin, const int trace_bin_size,
00232                           double **sparse_v_mat,
00233                           int *pcard_v_mat) const;
00234         void update_sparsify_structures(const int np, 
00235                           const double *sol, double *v,double* margin, 
00236                           double** mat, double *lhs, const int *zeroed, 
00237                           int evidx, bool decompose, int *evdec_num) const;
00238 
00239         void sparsify(const int evidx, const double eigen_val, 
00240                          const double *v, const int n, 
00241                          const double *sol, double **sparse_v_mat,
00242                          int *card_v_mat , double *work_ev, bool wise, int *evdec_num) const;
00243         void sparsify_new(const int evidx, const double eigen_val, 
00244                          const double *v, const int n, 
00245                          const double *sol, double **sparse_v_mat,
00246                          int *card_v_mat , double *work_ev, bool wise, int *evdec_num) const;
00247 
00248         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;
00249 };
00250 
00251 #endif

Generated on Thu Sep 22 03:05:56 2011 by  doxygen 1.4.7