CglRedSplit2.hpp

Go to the documentation of this file.

// Last edit: 04/03/10
//
// Name:     CglRedSplit2.hpp
// Author:   Giacomo Nannicini
//           Singapore University of Technology and Design
//           Singapore
//           email: nannicini@sutd.edu.sg
//           based on CglRedSplit by Francois Margot
// Date:     03/09/09
//-----------------------------------------------------------------------------
// Copyright (C) 2010, Giacomo Nannicini and others.  All Rights Reserved.
 
#ifndef CglRedSplit2_H
#define CglRedSplit2_H
 
#include "CglCutGenerator.hpp"
#include "CglRedSplit2Param.hpp"
#include "CoinWarmStartBasis.hpp"
#include "CoinHelperFunctions.hpp"
#include "CoinTime.hpp"
 
class CglRedSplit2 : public CglCutGenerator {
 
  friend void CglRedSplit2UnitTest(const OsiSolverInterface * siP,
                                  const std::string mpdDir);
public:
  virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
                            const CglTreeInfo info = CglTreeInfo());
 
  virtual bool needsOptimalBasis() const;
 
  // Generate the row multipliers computed by Reduce-and-Split from the
  // given OsiSolverInterface. The multipliers are written in lambda;
  // lambda should be of size nrow*maxNumMultipliers. We generate at most
  // maxNumMultipliers m-vectors of row multipliers, and return the number
  // of m-vectors that were generated.
  // If the caller wants to know which variables are basic in each row 
  // (same order as lambda), basicVariables should be non-NULL (size nrow).
  // This method can also generate the cuts corresponding to the multipliers
  // returned; it suffices to pass non-NULL OsiCuts.
  // This method is not needed by the typical user; however, it is useful
  // in the context of generating Lift & Project cuts.
  int generateMultipliers(const OsiSolverInterface& si, int* lambda,
                          int maxNumMultipliers, int* basicVariables = NULL,
                          OsiCuts* cs = NULL);
 
  // Try to improve a Lift & Project cut, by employing the
  // Reduce-and-Split procedure. We start from a row of a L&P tableau,
  // and generate a cut trying to reduce the coefficients on the
  // nonbasic variables.  Note that this L&P tableau will in general
  // have nonbasic variables which are nonzero in the point that we
  // want to cut off, so we should be careful.  Arguments:
  // OsiSolverInterface which contains the simplex tableau, initial
  // row from which the cut is derived, row rhs, row number of the
  // source row (if it is in the simplex tableau; otherwise, a
  // negative number; needed to avoid using duplicate rows), point
  // that we want to cut off (note: this is NOT a basic solution for
  // the OsiSolverInterace!), list of variables which are basic in
  // xbar but are nonbasic in the OsiSolverInterface. The computed cut
  // is written in OsiRowCut* cs. Finally, if a starting disjunction
  // is provided in the vector lambda (of size ncols, i.e. a
  // disjunction on the structural variables), the disjunction is
  // modified according to the cut which is produced.
  int tiltLandPcut(const OsiSolverInterface* si, double* row, 
                   double rowRhs, int rownumber, const double* xbar, 
                   const int* newnonbasics, OsiRowCut* cs, int* lambda = NULL);
 
  
  
 
  // Set the parameters to the values of the given CglRedSplit2Param object.
  void setParam(const CglRedSplit2Param &source); 
  // Return the CglRedSplit2Param object of the generator. 
  inline CglRedSplit2Param& getParam() {return param;}
 
  void print() const;
 
  void printOptTab(OsiSolverInterface *solver) const;
  
 
  CglRedSplit2();
 
  CglRedSplit2(const CglRedSplit2Param &RS_param);
 
  CglRedSplit2(const CglRedSplit2 &);
 
  virtual CglCutGenerator * clone() const;
 
  CglRedSplit2 & operator=(const CglRedSplit2& rhs);
  
  virtual ~CglRedSplit2 ();
 
 
private:
  
  // Private member methods
 
 
  // Method generating the cuts after all CglRedSplit2 members are 
  // properly set. This does the actual work. Returns the number of
  // generated cuts (or multipliers).
  // Will generate cuts if cs != NULL, and will generate multipliers
  // if lambda != NULL. 
  int generateCuts(OsiCuts* cs, int maxNumCuts, int* lambda = NULL);
 
  inline double rs_above_integer(const double value) const; 
 
  void fill_workNonBasicTab(CglRedSplit2Param::ColumnSelectionStrategy 
                            strategy, const int* ignore_list = NULL);
 
  void fill_workNonBasicTab(const int* newnonbasics, const double* xbar,
                            CglRedSplit2Param::ColumnScalingStrategy scaling);
 
  void reduce_workNonBasicTab(int numRows, 
                              CglRedSplit2Param::RowSelectionStrategy 
                              rowSelectionStrategy,
                              int maxIterations);
 
  void generate_row(int index_row, double *row);
 
  int generate_cgcut(double *row, double *rhs);
 
  void eliminate_slacks(double *row, 
                        const double *elements, 
                        const CoinBigIndex *start,
                        const int *indices,
                        const int *rowLength,
                        const double *rhs, double *rowrhs);
 
  void flip(double *row);
 
  void unflip(double *row, double *rowrhs);
 
  int check_dynamism(double *row);
 
  int generate_packed_row(const double *xlp, double *row,
                          int *rowind, double *rowelem, 
                          int *card_row, double & rhs);
 
  // Compute entries of is_integer.
  void compute_is_integer();
 
  // Check that two vectors are different.
  bool rs_are_different_vectors(const int *vect1, 
                                const int *vect2,
                                const int dim);
 
  // allocate matrix of integers
  void rs_allocmatINT(int ***v, int m, int n);
  // deallocate matrix of integers
  void rs_deallocmatINT(int ***v, int m);
  // allocate matrix of doubles
  void rs_allocmatDBL(double ***v, int m, int n);
  // deallocate matrix of doubles
  void rs_deallocmatDBL(double ***v, int m);
  // print a vector of integers
  void rs_printvecINT(const char *vecstr, const int *x, int n) const;
  // print a vector of doubles
  void rs_printvecDBL(const char *vecstr, const double *x, int n) const;
  // print a matrix of integers
  void rs_printmatINT(const char *vecstr, const int * const *x, int m, int n) const;
  // print a matrix of doubles
  void rs_printmatDBL(const char *vecstr, const double * const *x, int m, int n) const;
  // dot product
  double rs_dotProd(const double *u, const double *v, int dim) const;
  double rs_dotProd(const int *u, const double *v, int dim) const;
  // From Numerical Recipes in C: LU decomposition
  int ludcmp(double **a, int n, int *indx, double *d, double* vv) const;
  // from Numerical Recipes in C: backward substitution
  void lubksb(double **a, int n, int *indx, double *b) const;
 
  // Check if the linear combination given by listOfRows with given multipliers
  // improves the norm of row #rowindex; note: multipliers are rounded!
  // Returns the difference with respect to the old norm (if negative there is
  // an improvement, if positive norm increases)
  double compute_norm_change(double oldnorm, const int* listOfRows,
                             int numElemList, const double* multipliers) const;
 
  // Compute the list of rows that should be used to reduce row #rowIndex
  int get_list_rows_reduction(int rowIndex, int numRowsReduction, 
                              int* list, const double* norm, 
                              CglRedSplit2Param::RowSelectionStrategy 
                              rowSelectionStrategy) const;
 
  // Sorts the rows by increasing number of nonzeroes with respect to a given
  // row (rowIndex), on the nonbasic variables (whichTab == 0 means only
  // integer, whichTab == 1 means only workTab, whichTab == 2 means both).
  // The array for sorting must be allocated (and deleted) by caller.
  // Corresponds to BRS1 in the paper.
  int sort_rows_by_nonzeroes(struct sortElement* array, int rowIndex, 
                             int maxRows, int whichTab) const;
 
  // Greedy variant of the previous function; slower but typically
  // more effective. Corresponds to BRS2 in the paper.
  int sort_rows_by_nonzeroes_greedy(struct sortElement* array, int rowIndex, 
                                    int maxRows, int whichTab) const;
 
  // Sorts the rows by decreasing absolute value of the cosine of the
  // angle with respect to a given row (rowIndex), on the nonbasic
  // variables (whichTab == 0 means only integer, whichTab == 1 means
  // only workTab, whichTab == 2 means both).  The array for sorting
  // must be allocated (and deleted) by caller. Very effective
  // strategy in practice. Corresponds to BRS3 in the paper.
  int sort_rows_by_cosine(struct sortElement* array, int rowIndex, 
                          int maxRows, int whichTab) const;
 
  // Did we hit the time limit?
  inline bool checkTime() const{
    if ((CoinCpuTime() - startTime) < param.getTimeLimit()){
      return true;
    }
    return false;
  }
 
 
  
  // Private member data
 
 
  CglRedSplit2Param param;
 
  int nrow; 
 
  int ncol;
 
  int numRedRows;
 
  const double *colLower;
 
  const double *colUpper;
  
  const double *rowLower;
 
  const double *rowUpper;
 
  const double *rowRhs;
 
  const double *reducedCost;
 
  const double *rowPrice;
 
  const double* objective;
 
  int card_intBasicVar;
 
  int card_intBasicVar_frac;
 
  int card_intNonBasicVar; 
 
  int card_contNonBasicVar;
 
  int card_workNonBasicVar;
 
  int card_nonBasicAtUpper; 
 
  int card_nonBasicAtLower;
 
  int *cv_intBasicVar;  
 
  int *cv_intBasicVar_frac;  
 
  int *cv_fracRowsTab;  
 
  int *intBasicVar;
 
  int *intBasicVar_frac;
 
  int *intNonBasicVar; 
 
  // slacks are considered continuous (no harm if this is not the case).
  int *contNonBasicVar;
 
  int *nonBasicAtUpper;
 
  int *nonBasicAtLower;
 
  int mTab;
 
  int nTab;
 
  int **pi_mat;
 
  double **contNonBasicTab;
 
  double **workNonBasicTab;
 
  // Dimensions: mTab by card_intNonBasicVar.
  double **intNonBasicTab;
 
  double *rhsTab;
 
  double *norm;
 
  int *is_integer;
 
  OsiSolverInterface *solver;
 
  const double *xlp;
 
  const double *rowActivity;
 
  const CoinPackedMatrix *byRow;
 
  double startTime;
 
};
 
//#############################################################################
void CglRedSplit2UnitTest(const OsiSolverInterface * siP,
                         const std::string mpdDir );
 
 
#endif