Cbc  2.9.9
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 
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 
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 
332 
334  int nrow;
335 
337  int ncol;
338 
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 
368 
372 
376 
380 
384 
388 
392 
395 
399 
403 
407 
411 
414 
416  // slacks are considered continuous (no harm if this is not the case).
418 
422 
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 
462 
465 
467  const double *xlp;
468 
470  const double *rowActivity;
471 
475 
478  double startTime;
479 
481 };
482 
483 //#############################################################################
491  const std::string mpdDir );
492 
493 
494 #endif
int nrow
Number of rows ( = number of slack variables) in the current LP.
int * intBasicVar_frac
List of integer structural basic variables with fractional value (in order of pivot in selected rows ...
void rs_printvecDBL(const char *vecstr, const double *x, int n) const
int * cv_intBasicVar
Characteristic vector for integer basic structural variables.
const double * objective
Objective coefficients.
int * intBasicVar
List of integer structural basic variables (in order of pivot in selected rows for cut generation)...
void rs_printmatINT(const char *vecstr, const int *const *x, int m, int n) const
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...
void rs_deallocmatDBL(double ***v, int m)
int card_intBasicVar_frac
Number of integer basic structural variables that are fractional in the current lp solution (at least...
friend void CglRedSplit2UnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests some of the methods in the CglRedSplit2 class.
int card_intBasicVar
Number of integer basic structural variables.
void compute_is_integer()
double * norm
Norm of rows in workNonBasicTab; needed for faster computations.
int * nonBasicAtLower
List of non basic variables (structural or slack) at their lower bound.
int ncol
Number of structural variables in the current LP.
void printOptTab(OsiSolverInterface *solver) const
Print the current simplex tableau.
void reduce_workNonBasicTab(int numRows, CglRedSplit2Param::RowSelectionStrategy rowSelectionStrategy, int maxIterations)
Reduce rows of workNonBasicTab, i.e.
Class collecting parameters the Reduced-and-split cut generator.
double ** workNonBasicTab
Current tableau for continuous non basic variables (structural or slack).
int check_dynamism(double *row)
Returns 1 if the row has acceptable max/min coeff ratio.
virtual CglCutGenerator * clone() const
Clone.
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:15
const double * rowLower
Lower bounds for constraints.
Collections of row cuts and column cuts.
Definition: OsiCuts.hpp:19
ColumnScalingStrategy
Scaling strategies for new nonbasic columns for Lift &amp; Project; &quot;factor&quot; is the value of columnScalin...
int card_nonBasicAtLower
Number of non basic variables (structural or slack) at their lower bound in the current lp solution...
void rs_allocmatDBL(double ***v, int m, int n)
int * intNonBasicVar
List of integer structural non basic variables.
CglRedSplit2 & operator=(const CglRedSplit2 &rhs)
Assignment operator.
static double CoinCpuTime()
Definition: CoinTime.hpp:106
const double * colUpper
Upper bounds for structural variables.
int * nonBasicAtUpper
List of non basic variables (structural or slack) at their upper bound.
CglRedSplit2Param & getParam()
int tiltLandPcut(const OsiSolverInterface *si, double *row, double rowRhs, int rownumber, const double *xbar, const int *newnonbasics, OsiRowCut *cs, int *lambda=NULL)
bool rs_are_different_vectors(const int *vect1, const int *vect2, const int dim)
Abstract Base Class for describing an interface to a solver.
void unflip(double *row, double *rowrhs)
Change the sign of the coefficients of the continuous non basic variables at their upper bound and do...
Reduce-and-Split Cut Generator Class; See method generateCuts().
const double * xlp
Pointer on point to separate. Reset by each call to generateCuts().
int sort_rows_by_nonzeroes(struct sortElement *array, int rowIndex, int maxRows, int whichTab) const
int ludcmp(double **a, int n, int *indx, double *d, double *vv) const
double startTime
Time at which cut computations began.
ColumnSelectionStrategy
Column selection strategies; again, look them up in the paper.
int * cv_intBasicVar_frac
Characteristic vector for integer basic structural variables with non integer value in the current lp...
int sort_rows_by_cosine(struct sortElement *array, int rowIndex, int maxRows, int whichTab) const
Cut Generator Base Class.
void rs_printvecINT(const char *vecstr, const int *x, int n) const
int get_list_rows_reduction(int rowIndex, int numRowsReduction, int *list, const double *norm, CglRedSplit2Param::RowSelectionStrategy rowSelectionStrategy) const
int mTab
Number of rows in the reduced tableau (= card_intBasicVar).
double getTimeLimit() const
get the value
CglRedSplit2()
Default constructor.
void rs_printmatDBL(const char *vecstr, const double *const *x, int m, int n) const
Row Cut Class.
Definition: OsiRowCut.hpp:29
double compute_norm_change(double oldnorm, const int *listOfRows, int numElemList, const double *multipliers) const
int generate_packed_row(const double *xlp, double *row, int *rowind, double *rowelem, int *card_row, double &rhs)
Generate the packed cut from the row representation.
Sparse Matrix Base Class.
int card_intNonBasicVar
Number of integer non basic structural variables in the current lp solution.
void eliminate_slacks(double *row, const double *elements, const int *start, const int *indices, const int *rowLength, const double *rhs, double *rowrhs)
Use multiples of the initial inequalities to cancel out the coefficients of the slack variables...
int nTab
Number of columns in the reduced tableau (= card_contNonBasicVar)
int * cv_fracRowsTab
Characteristic vector for rows of the tableau selected for reduction with non integer value in the cu...
int generate_cgcut(double *row, double *rhs)
Generate a mixed integer Gomory cut, when all non basic variables are non negative and at their lower...
const double * colLower
Lower bounds for structural variables.
CglRedSplit2Param param
Object with CglRedSplit2Param members.
int * contNonBasicVar
List of continuous non basic variables (structural or slack).
double ** intNonBasicTab
Simplex tableau for integer non basic structural variables.
int card_workNonBasicVar
Number of continuous non basic variables (structural or slack) in the current working set for coeffic...
void CglRedSplit2UnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests some of the methods in the CglRedSplit2 class.
void rs_allocmatINT(int ***v, int m, int n)
double * rhsTab
Right hand side of the tableau.
void lubksb(double **a, int n, int *indx, double *b) const
int numRedRows
Number of rows which have been reduced.
OsiSolverInterface * solver
Pointer on solver. Reset by each call to generateCuts().
void fill_workNonBasicTab(CglRedSplit2Param::ColumnSelectionStrategy strategy, const int *ignore_list=NULL)
Fill workNonBasicTab, depending on the column selection strategy.
const double * reducedCost
Reduced costs for columns.
void rs_deallocmatINT(int ***v, int m)
double rs_dotProd(const double *u, const double *v, int dim) const
const double * rowUpper
Upper bounds for constraints.
const double * rowActivity
Pointer on row activity. Reset by each call to generateCuts().
void generate_row(int index_row, double *row)
Generate a linear combination of the rows of the current LP tableau, using the row multipliers stored...
double rs_above_integer(const double value) const
Compute the fractional part of value, allowing for small error.
const CoinPackedMatrix * byRow
Pointer on matrix of coefficient ordered by rows.
int generateMultipliers(const OsiSolverInterface &si, int *lambda, int maxNumMultipliers, int *basicVariables=NULL, OsiCuts *cs=NULL)
virtual ~CglRedSplit2()
Destructor.
int card_nonBasicAtUpper
Number of non basic variables (structural or slack) at their upper bound in the current lp solution...
int card_contNonBasicVar
Number of continuous non basic variables (structural or slack) in the current lp solution.
int ** pi_mat
Tableau of multipliers used to alter the rows used in generation.
const double * rowPrice
Row price.
const double * rowRhs
Righ hand side for constraints (upper bound for ranged constraints).
virtual bool needsOptimalBasis() const
Return true if needs optimal basis to do cuts (will return true)
void flip(double *row)
Change the sign of the coefficients of the continuous non basic variables at their upper bound...
RowSelectionStrategy
Enumerations for parameters.
double ** contNonBasicTab
Simplex tableau for continuous non basic variables (structural or slack).
bool checkTime() const
int * is_integer
Characteristic vectors of structural integer variables or continuous variables currently fixed to int...
void setParam(const CglRedSplit2Param &source)
void print() const
Print some of the data members; used for debugging.
int sort_rows_by_nonzeroes_greedy(struct sortElement *array, int rowIndex, int maxRows, int whichTab) const