- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

# /home/coin/svn-release/Alps-1.5.2/Cgl/src/CglRedSplit2/CglRedSplit2.hpp

Go to the documentation of this file.

    00001 // Last edit: 04/03/10
    00002 //
    00003 // Name:     CglRedSplit2.hpp
    00004 // Author:   Giacomo Nannicini
    00005 //           Singapore University of Technology and Design
    00006 //           Singapore
    00007 //           email: nannicini@sutd.edu.sg
    00008 //           based on CglRedSplit by Francois Margot
    00009 // Date:     03/09/09
    00010 //-----------------------------------------------------------------------------
    00011 // Copyright (C) 2010, Giacomo Nannicini and others.  All Rights Reserved.
    00012
    00013 #ifndef CglRedSplit2_H
    00014 #define CglRedSplit2_H
    00015
    00016 #include "CglCutGenerator.hpp"
    00017 #include "CglRedSplit2Param.hpp"
    00018 #include "CoinWarmStartBasis.hpp"
    00019 #include "CoinHelperFunctions.hpp"
    00020 #include "CoinTime.hpp"
    00021
    00031 class CglRedSplit2 : public CglCutGenerator {
    00032
    00033   friend void CglRedSplit2UnitTest(const OsiSolverInterface * siP,
    00034                                   const std::string mpdDir);
    00035 public:
    00081   virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
    00082                             const CglTreeInfo info = CglTreeInfo());
    00083
    00085   virtual bool needsOptimalBasis() const;
    00086
    00087   // Generate the row multipliers computed by Reduce-and-Split from the
    00088   // given OsiSolverInterface. The multipliers are written in lambda;
    00089   // lambda should be of size nrow*maxNumMultipliers. We generate at most
    00090   // maxNumMultipliers m-vectors of row multipliers, and return the number
    00091   // of m-vectors that were generated.
    00092   // If the caller wants to know which variables are basic in each row
    00093   // (same order as lambda), basicVariables should be non-NULL (size nrow).
    00094   // This method can also generate the cuts corresponding to the multipliers
    00095   // returned; it suffices to pass non-NULL OsiCuts.
    00096   // This method is not needed by the typical user; however, it is useful
    00097   // in the context of generating Lift & Project cuts.
    00098   int generateMultipliers(const OsiSolverInterface& si, int* lambda,
    00099                           int maxNumMultipliers, int* basicVariables = NULL,
    00100                           OsiCuts* cs = NULL);
    00101
    00102   // Try to improve a Lift & Project cut, by employing the
    00103   // Reduce-and-Split procedure. We start from a row of a L&P tableau,
    00104   // and generate a cut trying to reduce the coefficients on the
    00105   // nonbasic variables.  Note that this L&P tableau will in general
    00106   // have nonbasic variables which are nonzero in the point that we
    00107   // want to cut off, so we should be careful.  Arguments:
    00108   // OsiSolverInterface which contains the simplex tableau, initial
    00109   // row from which the cut is derived, row rhs, row number of the
    00110   // source row (if it is in the simplex tableau; otherwise, a
    00111   // negative number; needed to avoid using duplicate rows), point
    00112   // that we want to cut off (note: this is NOT a basic solution for
    00113   // the OsiSolverInterace!), list of variables which are basic in
    00114   // xbar but are nonbasic in the OsiSolverInterface. The computed cut
    00115   // is written in OsiRowCut* cs. Finally, if a starting disjunction
    00116   // is provided in the vector lambda (of size ncols, i.e. a
    00117   // disjunction on the structural variables), the disjunction is
    00118   // modified according to the cut which is produced.
    00119   int tiltLandPcut(const OsiSolverInterface* si, double* row,
    00120                    double rowRhs, int rownumber, const double* xbar,
    00121                    const int* newnonbasics, OsiRowCut* cs, int* lambda = NULL);
    00122
    00124
    00125
    00128
    00129   // Set the parameters to the values of the given CglRedSplit2Param object.
    00130   void setParam(const CglRedSplit2Param &source);
    00131   // Return the CglRedSplit2Param object of the generator.
    00132   inline CglRedSplit2Param& getParam() {return param;}
    00133
    00135   void print() const;
    00136
    00138   void printOptTab(OsiSolverInterface *solver) const;
    00139
    00141
    00144
    00145   CglRedSplit2();
    00146
    00148   CglRedSplit2(const CglRedSplit2Param &RS_param);
    00149
    00151   CglRedSplit2(const CglRedSplit2 &);
    00152
    00154   virtual CglCutGenerator * clone() const;
    00155
    00157   CglRedSplit2 & operator=(const CglRedSplit2& rhs);
    00158
    00160   virtual ~CglRedSplit2 ();
    00161
    00163
    00164 private:
    00165
    00166   // Private member methods
    00167
    00171
    00172   // Method generating the cuts after all CglRedSplit2 members are
    00173   // properly set. This does the actual work. Returns the number of
    00174   // generated cuts (or multipliers).
    00175   // Will generate cuts if cs != NULL, and will generate multipliers
    00176   // if lambda != NULL.
    00177   int generateCuts(OsiCuts* cs, int maxNumCuts, int* lambda = NULL);
    00178
    00180   inline double rs_above_integer(const double value) const;
    00181
    00188   void fill_workNonBasicTab(CglRedSplit2Param::ColumnSelectionStrategy
    00189                             strategy, const int* ignore_list = NULL);
    00190
    00195   void fill_workNonBasicTab(const int* newnonbasics, const double* xbar,
    00196                             CglRedSplit2Param::ColumnScalingStrategy scaling);
    00197
    00201   void reduce_workNonBasicTab(int numRows,
    00202                               CglRedSplit2Param::RowSelectionStrategy
    00203                               rowSelectionStrategy,
    00204                               int maxIterations);
    00205
    00209   void generate_row(int index_row, double *row);
    00210
    00213   int generate_cgcut(double *row, double *rhs);
    00214
    00217   void eliminate_slacks(double *row,
    00218                         const double *elements,
    00219                         const int *start,
    00220                         const int *indices,
    00221                         const int *rowLength,
    00222                         const double *rhs, double *rowrhs);
    00223
    00226   void flip(double *row);
    00227
    00232   void unflip(double *row, double *rowrhs);
    00233
    00239   int check_dynamism(double *row);
    00240
    00242   int generate_packed_row(const double *xlp, double *row,
    00243                           int *rowind, double *rowelem,
    00244                           int *card_row, double & rhs);
    00245
    00246   // Compute entries of is_integer.
    00247   void compute_is_integer();
    00248
    00249   // Check that two vectors are different.
    00250   bool rs_are_different_vectors(const int *vect1,
    00251                                 const int *vect2,
    00252                                 const int dim);
    00253
    00254   // allocate matrix of integers
    00255   void rs_allocmatINT(int ***v, int m, int n);
    00256   // deallocate matrix of integers
    00257   void rs_deallocmatINT(int ***v, int m);
    00258   // allocate matrix of doubles
    00259   void rs_allocmatDBL(double ***v, int m, int n);
    00260   // deallocate matrix of doubles
    00261   void rs_deallocmatDBL(double ***v, int m);
    00262   // print a vector of integers
    00263   void rs_printvecINT(const char *vecstr, const int *x, int n) const;
    00264   // print a vector of doubles
    00265   void rs_printvecDBL(const char *vecstr, const double *x, int n) const;
    00266   // print a matrix of integers
    00267   void rs_printmatINT(const char *vecstr, const int * const *x, int m, int n) const;
    00268   // print a matrix of doubles
    00269   void rs_printmatDBL(const char *vecstr, const double * const *x, int m, int n) const;
    00270   // dot product
    00271   double rs_dotProd(const double *u, const double *v, int dim) const;
    00272   double rs_dotProd(const int *u, const double *v, int dim) const;
    00273   // From Numerical Recipes in C: LU decomposition
    00274   int ludcmp(double **a, int n, int *indx, double *d, double* vv) const;
    00275   // from Numerical Recipes in C: backward substitution
    00276   void lubksb(double **a, int n, int *indx, double *b) const;
    00277
    00278   // Check if the linear combination given by listOfRows with given multipliers
    00279   // improves the norm of row #rowindex; note: multipliers are rounded!
    00280   // Returns the difference with respect to the old norm (if negative there is
    00281   // an improvement, if positive norm increases)
    00282   double compute_norm_change(double oldnorm, const int* listOfRows,
    00283                              int numElemList, const double* multipliers) const;
    00284
    00285   // Compute the list of rows that should be used to reduce row #rowIndex
    00286   int get_list_rows_reduction(int rowIndex, int numRowsReduction,
    00287                               int* list, const double* norm,
    00288                               CglRedSplit2Param::RowSelectionStrategy
    00289                               rowSelectionStrategy) const;
    00290
    00291   // Sorts the rows by increasing number of nonzeroes with respect to a given
    00292   // row (rowIndex), on the nonbasic variables (whichTab == 0 means only
    00293   // integer, whichTab == 1 means only workTab, whichTab == 2 means both).
    00294   // The array for sorting must be allocated (and deleted) by caller.
    00295   // Corresponds to BRS1 in the paper.
    00296   int sort_rows_by_nonzeroes(struct sortElement* array, int rowIndex,
    00297                              int maxRows, int whichTab) const;
    00298
    00299   // Greedy variant of the previous function; slower but typically
    00300   // more effective. Corresponds to BRS2 in the paper.
    00301   int sort_rows_by_nonzeroes_greedy(struct sortElement* array, int rowIndex,
    00302                                     int maxRows, int whichTab) const;
    00303
    00304   // Sorts the rows by decreasing absolute value of the cosine of the
    00305   // angle with respect to a given row (rowIndex), on the nonbasic
    00306   // variables (whichTab == 0 means only integer, whichTab == 1 means
    00307   // only workTab, whichTab == 2 means both).  The array for sorting
    00308   // must be allocated (and deleted) by caller. Very effective
    00309   // strategy in practice. Corresponds to BRS3 in the paper.
    00310   int sort_rows_by_cosine(struct sortElement* array, int rowIndex,
    00311                           int maxRows, int whichTab) const;
    00312
    00313   // Did we hit the time limit?
    00314   inline bool checkTime() const{
    00315     if ((CoinCpuTime() - startTime) < param.getTimeLimit()){
    00316       return true;
    00317     }
    00318     return false;
    00319   }
    00320
    00322
    00323
    00324   // Private member data
    00325
    00329
    00331   CglRedSplit2Param param;
    00332
    00334   int nrow;
    00335
    00337   int ncol;
    00338
    00340   int numRedRows;
    00341
    00343   const double *colLower;
    00344
    00346   const double *colUpper;
    00347
    00349   const double *rowLower;
    00350
    00352   const double *rowUpper;
    00353
    00355   const double *rowRhs;
    00356
    00358   const double *reducedCost;
    00359
    00361   const double *rowPrice;
    00362
    00364   const double* objective;
    00365
    00367   int card_intBasicVar;
    00368
    00371   int card_intBasicVar_frac;
    00372
    00375   int card_intNonBasicVar;
    00376
    00379   int card_contNonBasicVar;
    00380
    00383   int card_workNonBasicVar;
    00384
    00387   int card_nonBasicAtUpper;
    00388
    00391   int card_nonBasicAtLower;
    00392
    00394   int *cv_intBasicVar;
    00395
    00398   int *cv_intBasicVar_frac;
    00399
    00402   int *cv_fracRowsTab;
    00403
    00406   int *intBasicVar;
    00407
    00410   int *intBasicVar_frac;
    00411
    00413   int *intNonBasicVar;
    00414
    00416   // slacks are considered continuous (no harm if this is not the case).
    00417   int *contNonBasicVar;
    00418
    00421   int *nonBasicAtUpper;
    00422
    00425   int *nonBasicAtLower;
    00426
    00428   int mTab;
    00429
    00431   int nTab;
    00432
    00435   int **pi_mat;
    00436
    00440   double **contNonBasicTab;
    00441
    00445   double **workNonBasicTab;
    00446
    00449   // Dimensions: mTab by card_intNonBasicVar.
    00450   double **intNonBasicTab;
    00451
    00454   double *rhsTab;
    00455
    00457   double *norm;
    00458
    00461   int *is_integer;
    00462
    00464   OsiSolverInterface *solver;
    00465
    00467   const double *xlp;
    00468
    00470   const double *rowActivity;
    00471
    00474   const CoinPackedMatrix *byRow;
    00475
    00478   double startTime;
    00479
    00481 };
    00482
    00483 //#############################################################################
    00490 void CglRedSplit2UnitTest(const OsiSolverInterface * siP,
    00491                          const std::string mpdDir );
    00492
    00493
    00494 #endif