Cgl  0.59.10
CglRedSplit2.hpp
Go to the documentation of this file.
1 // Last edit: 04/03/10
2 //
3 // Name: CglRedSplit2.hpp
4 // Author: Giacomo Nannicini
5 // Singapore University of Technology and Design
6 // Singapore
7 // email: nannicini@sutd.edu.sg
8 // based on CglRedSplit by Francois Margot
9 // Date: 03/09/09
10 //-----------------------------------------------------------------------------
11 // Copyright (C) 2010, Giacomo Nannicini and others. All Rights Reserved.
12 
13 #ifndef CglRedSplit2_H
14 #define CglRedSplit2_H
15 
16 #include "CglCutGenerator.hpp"
17 #include "CglRedSplit2Param.hpp"
18 #include "CoinWarmStartBasis.hpp"
19 #include "CoinHelperFunctions.hpp"
20 #include "CoinTime.hpp"
21 
31 class CglRedSplit2 : public CglCutGenerator {
32 
33  friend void CglRedSplit2UnitTest(const OsiSolverInterface * siP,
34  const std::string mpdDir);
35 public:
81  virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
82  const CglTreeInfo info = CglTreeInfo());
83 
85  virtual bool needsOptimalBasis() const;
86 
87  // Generate the row multipliers computed by Reduce-and-Split from the
88  // given OsiSolverInterface. The multipliers are written in lambda;
89  // lambda should be of size nrow*maxNumMultipliers. We generate at most
90  // maxNumMultipliers m-vectors of row multipliers, and return the number
91  // of m-vectors that were generated.
92  // If the caller wants to know which variables are basic in each row
93  // (same order as lambda), basicVariables should be non-NULL (size nrow).
94  // This method can also generate the cuts corresponding to the multipliers
95  // returned; it suffices to pass non-NULL OsiCuts.
96  // This method is not needed by the typical user; however, it is useful
97  // in the context of generating Lift & Project cuts.
98  int generateMultipliers(const OsiSolverInterface& si, int* lambda,
99  int maxNumMultipliers, int* basicVariables = NULL,
100  OsiCuts* cs = NULL);
101 
102  // Try to improve a Lift & Project cut, by employing the
103  // Reduce-and-Split procedure. We start from a row of a L&P tableau,
104  // and generate a cut trying to reduce the coefficients on the
105  // nonbasic variables. Note that this L&P tableau will in general
106  // have nonbasic variables which are nonzero in the point that we
107  // want to cut off, so we should be careful. Arguments:
108  // OsiSolverInterface which contains the simplex tableau, initial
109  // row from which the cut is derived, row rhs, row number of the
110  // source row (if it is in the simplex tableau; otherwise, a
111  // negative number; needed to avoid using duplicate rows), point
112  // that we want to cut off (note: this is NOT a basic solution for
113  // the OsiSolverInterace!), list of variables which are basic in
114  // xbar but are nonbasic in the OsiSolverInterface. The computed cut
115  // is written in OsiRowCut* cs. Finally, if a starting disjunction
116  // is provided in the vector lambda (of size ncols, i.e. a
117  // disjunction on the structural variables), the disjunction is
118  // modified according to the cut which is produced.
119  int tiltLandPcut(const OsiSolverInterface* si, double* row,
120  double rowRhs, int rownumber, const double* xbar,
121  const int* newnonbasics, OsiRowCut* cs, int* lambda = NULL);
122 
124 
125 
128 
129  // Set the parameters to the values of the given CglRedSplit2Param object.
130  void setParam(const CglRedSplit2Param &source);
131  // Return the CglRedSplit2Param object of the generator.
132  inline CglRedSplit2Param& getParam() {return param;}
133 
135  void print() const;
136 
138  void printOptTab(OsiSolverInterface *solver) const;
139 
141 
144  CglRedSplit2();
146 
148  CglRedSplit2(const CglRedSplit2Param &RS_param);
149 
151  CglRedSplit2(const CglRedSplit2 &);
152 
154  virtual CglCutGenerator * clone() const;
155 
157  CglRedSplit2 & operator=(const CglRedSplit2& rhs);
158 
160  virtual ~CglRedSplit2 ();
161 
163 
164 private:
165 
166  // Private member methods
167 
171 
172  // Method generating the cuts after all CglRedSplit2 members are
173  // properly set. This does the actual work. Returns the number of
174  // generated cuts (or multipliers).
175  // Will generate cuts if cs != NULL, and will generate multipliers
176  // if lambda != NULL.
177  int generateCuts(OsiCuts* cs, int maxNumCuts, int* lambda = NULL);
178 
180  inline double rs_above_integer(const double value) const;
181 
188  void fill_workNonBasicTab(CglRedSplit2Param::ColumnSelectionStrategy
189  strategy, const int* ignore_list = NULL);
190 
195  void fill_workNonBasicTab(const int* newnonbasics, const double* xbar,
197 
201  void reduce_workNonBasicTab(int numRows,
203  rowSelectionStrategy,
204  int maxIterations);
205 
209  void generate_row(int index_row, double *row);
210 
213  int generate_cgcut(double *row, double *rhs);
214 
217  void eliminate_slacks(double *row,
218  const double *elements,
219  const int *start,
220  const int *indices,
221  const int *rowLength,
222  const double *rhs, double *rowrhs);
223 
226  void flip(double *row);
227 
232  void unflip(double *row, double *rowrhs);
233 
239  int check_dynamism(double *row);
240 
242  int generate_packed_row(const double *xlp, double *row,
243  int *rowind, double *rowelem,
244  int *card_row, double & rhs);
245 
246  // Compute entries of is_integer.
247  void compute_is_integer();
248 
249  // Check that two vectors are different.
250  bool rs_are_different_vectors(const int *vect1,
251  const int *vect2,
252  const int dim);
253 
254  // allocate matrix of integers
255  void rs_allocmatINT(int ***v, int m, int n);
256  // deallocate matrix of integers
257  void rs_deallocmatINT(int ***v, int m);
258  // allocate matrix of doubles
259  void rs_allocmatDBL(double ***v, int m, int n);
260  // deallocate matrix of doubles
261  void rs_deallocmatDBL(double ***v, int m);
262  // print a vector of integers
263  void rs_printvecINT(const char *vecstr, const int *x, int n) const;
264  // print a vector of doubles
265  void rs_printvecDBL(const char *vecstr, const double *x, int n) const;
266  // print a matrix of integers
267  void rs_printmatINT(const char *vecstr, const int * const *x, int m, int n) const;
268  // print a matrix of doubles
269  void rs_printmatDBL(const char *vecstr, const double * const *x, int m, int n) const;
270  // dot product
271  double rs_dotProd(const double *u, const double *v, int dim) const;
272  double rs_dotProd(const int *u, const double *v, int dim) const;
273  // From Numerical Recipes in C: LU decomposition
274  int ludcmp(double **a, int n, int *indx, double *d, double* vv) const;
275  // from Numerical Recipes in C: backward substitution
276  void lubksb(double **a, int n, int *indx, double *b) const;
277 
278  // Check if the linear combination given by listOfRows with given multipliers
279  // improves the norm of row #rowindex; note: multipliers are rounded!
280  // Returns the difference with respect to the old norm (if negative there is
281  // an improvement, if positive norm increases)
282  double compute_norm_change(double oldnorm, const int* listOfRows,
283  int numElemList, const double* multipliers) const;
284 
285  // Compute the list of rows that should be used to reduce row #rowIndex
286  int get_list_rows_reduction(int rowIndex, int numRowsReduction,
287  int* list, const double* norm,
289  rowSelectionStrategy) const;
290 
291  // Sorts the rows by increasing number of nonzeroes with respect to a given
292  // row (rowIndex), on the nonbasic variables (whichTab == 0 means only
293  // integer, whichTab == 1 means only workTab, whichTab == 2 means both).
294  // The array for sorting must be allocated (and deleted) by caller.
295  // Corresponds to BRS1 in the paper.
296  int sort_rows_by_nonzeroes(struct sortElement* array, int rowIndex,
297  int maxRows, int whichTab) const;
298 
299  // Greedy variant of the previous function; slower but typically
300  // more effective. Corresponds to BRS2 in the paper.
301  int sort_rows_by_nonzeroes_greedy(struct sortElement* array, int rowIndex,
302  int maxRows, int whichTab) const;
303 
304  // Sorts the rows by decreasing absolute value of the cosine of the
305  // angle with respect to a given row (rowIndex), on the nonbasic
306  // variables (whichTab == 0 means only integer, whichTab == 1 means
307  // only workTab, whichTab == 2 means both). The array for sorting
308  // must be allocated (and deleted) by caller. Very effective
309  // strategy in practice. Corresponds to BRS3 in the paper.
310  int sort_rows_by_cosine(struct sortElement* array, int rowIndex,
311  int maxRows, int whichTab) const;
312 
313  // Did we hit the time limit?
314  inline bool checkTime() const{
315  if ((CoinCpuTime() - startTime) < param.getTimeLimit()){
316  return true;
317  }
318  return false;
319  }
320 
322 
323 
324  // Private member data
325 
329 
331  CglRedSplit2Param param;
332 
334  int nrow;
335 
337  int ncol;
338 
340  int numRedRows;
341 
343  const double *colLower;
344 
346  const double *colUpper;
347 
349  const double *rowLower;
350 
352  const double *rowUpper;
353 
355  const double *rowRhs;
356 
358  const double *reducedCost;
359 
361  const double *rowPrice;
362 
364  const double* objective;
365 
367  int card_intBasicVar;
368 
371  int card_intBasicVar_frac;
372 
375  int card_intNonBasicVar;
376 
379  int card_contNonBasicVar;
380 
383  int card_workNonBasicVar;
384 
387  int card_nonBasicAtUpper;
388 
391  int card_nonBasicAtLower;
392 
394  int *cv_intBasicVar;
395 
398  int *cv_intBasicVar_frac;
399 
402  int *cv_fracRowsTab;
403 
406  int *intBasicVar;
407 
410  int *intBasicVar_frac;
411 
413  int *intNonBasicVar;
414 
416  // slacks are considered continuous (no harm if this is not the case).
417  int *contNonBasicVar;
418 
421  int *nonBasicAtUpper;
422 
425  int *nonBasicAtLower;
426 
428  int mTab;
429 
431  int nTab;
432 
435  int **pi_mat;
436 
440  double **contNonBasicTab;
441 
445  double **workNonBasicTab;
446 
449  // Dimensions: mTab by card_intNonBasicVar.
450  double **intNonBasicTab;
451 
454  double *rhsTab;
455 
457  double *norm;
458 
461  int *is_integer;
462 
464  OsiSolverInterface *solver;
465 
467  const double *xlp;
468 
470  const double *rowActivity;
471 
474  const CoinPackedMatrix *byRow;
475 
478  double startTime;
479 
481 };
482 
483 //#############################################################################
490 void CglRedSplit2UnitTest(const OsiSolverInterface * siP,
491  const std::string mpdDir );
492 
493 
494 #endif
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate Reduce-and-Split Mixed Integer Gomory cuts for the model of the solver interface si...
friend void CglRedSplit2UnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests some of the methods in the CglRedSplit2 class.
Class collecting parameters the Reduced-and-split cut generator.
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:15
ColumnScalingStrategy
Scaling strategies for new nonbasic columns for Lift & Project; "factor" is the value of columnScalin...
void print() const
Print some of the data members; used for debugging.
double getTimeLimit() const
get the value
CglRedSplit2 & operator=(const CglRedSplit2 &rhs)
Assignment operator.
CglRedSplit2Param & getParam()
int tiltLandPcut(const OsiSolverInterface *si, double *row, double rowRhs, int rownumber, const double *xbar, const int *newnonbasics, OsiRowCut *cs, int *lambda=NULL)
Reduce-and-Split Cut Generator Class; See method generateCuts().
ColumnSelectionStrategy
Column selection strategies; again, look them up in the paper.
Cut Generator Base Class.
CglRedSplit2()
Default constructor.
virtual CglCutGenerator * clone() const
Clone.
int generateMultipliers(const OsiSolverInterface &si, int *lambda, int maxNumMultipliers, int *basicVariables=NULL, OsiCuts *cs=NULL)
virtual ~CglRedSplit2()
Destructor.
virtual bool needsOptimalBasis() const
Return true if needs optimal basis to do cuts (will return true)
void printOptTab(OsiSolverInterface *solver) const
Print the current simplex tableau.
RowSelectionStrategy
Enumerations for parameters.
void setParam(const CglRedSplit2Param &source)