coin-Cgl
CglRedSplit.hpp
Go to the documentation of this file.
1 // Last edit: 4/20/07
2 //
3 // Name: CglRedSplit.hpp
4 // Author: Francois Margot
5 // Tepper School of Business
6 // Carnegie Mellon University, Pittsburgh, PA 15213
7 // email: fmargot@andrew.cmu.edu
8 // Date: 2/6/05
9 //-----------------------------------------------------------------------------
10 // Copyright (C) 2005, Francois Margot and others. All Rights Reserved.
11 
12 #ifndef CglRedSplit_H
13 #define CglRedSplit_H
14 
15 #include "CglCutGenerator.hpp"
16 #include "CglRedSplitParam.hpp"
17 
23 class CglRedSplit : public CglCutGenerator {
24 
25  friend void CglRedSplitUnitTest(const OsiSolverInterface * siP,
26  const std::string mpdDir);
27 public:
58  virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
59  const CglTreeInfo info = CglTreeInfo());
60 
62  virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
63  const CglTreeInfo info = CglTreeInfo()) const;
64 
66  virtual bool needsOptimalBasis() const;
68 
69 
72 
73  // Set the parameters to the values of the given CglRedSplitParam object.
74  void setParam(const CglRedSplitParam &source);
75  // Return the CglRedSplitParam object of the generator.
76  inline CglRedSplitParam getParam() const {return param;}
77 
78  // Compute entries of low_is_lub and up_is_lub.
79  void compute_is_lub();
80 
81  // Compute entries of is_integer.
82  void compute_is_integer();
83 
89  void set_given_optsol(const double *given_sol, const int card_sol);
90 
92  void print() const;
93 
95  void printOptTab(OsiSolverInterface *solver) const;
96 
98 
101  //************************************************************
102  // TO BE REMOVED
105  void setLimit(int limit);
107  int getLimit() const;
108 
113  void setAway(double value);
115  double getAway() const;
119  void setLUB(double value);
121  double getLUB() const;
122 
125  void setEPS(double value);
127  double getEPS() const;
128 
131  void setEPS_COEFF(double value);
133  double getEPS_COEFF() const;
134 
138  void setEPS_COEFF_LUB(double value);
140  double getEPS_COEFF_LUB() const;
141 
145  void setEPS_RELAX(double value);
147  double getEPS_RELAX() const;
148 
151  void setNormIsZero(double value);
153  double getNormIsZero() const;
154 
157  void setMinReduc(double value);
159  double getMinReduc() const;
160 
166  void setMaxTab(double value);
168  double getMaxTab() const;
169  // END TO BE REMOVED
170  //************************************************************
171 
173 
176  CglRedSplit();
178 
180  CglRedSplit(const CglRedSplitParam &RS_param);
181 
183  CglRedSplit (const CglRedSplit &);
184 
186  virtual CglCutGenerator * clone() const;
187 
189  CglRedSplit &
190  operator=(
191  const CglRedSplit& rhs);
192 
194  virtual
195  ~CglRedSplit ();
197  virtual std::string generateCpp( FILE * fp);
199 
200 private:
201 
202  // Private member methods
203 
207 
208  // Method generating the cuts after all CglRedSplit members are properly set.
209  void generateCuts(OsiCuts & cs);
210 
212  inline double rs_above_integer(double value);
213 
215  void update_pi_mat(int r1, int r2, int step);
216 
218  void update_redTab(int r1, int r2, int step);
219 
222  void find_step(int r1, int r2, int *step,
223  double *reduc, double *norm);
224 
227  int test_pair(int r1, int r2, double *norm);
228 
230  void reduce_contNonBasicTab();
231 
233  void generate_row(int index_row, double *row);
234 
237  int generate_cgcut(double *row, double *rhs);
238 
241  int generate_cgcut_2(int basic_ind, double *row, double *rhs);
242 
245  void eliminate_slacks(double *row,
246  const double *elements,
247  const int *start,
248  const int *indices,
249  const int *rowLength,
250  const double *rhs, double *rowrhs);
251 
254  void flip(double *row);
255 
260  void unflip(double *row, double *rowrhs, double *slack_val);
261 
269  double row_scale_factor(double *row);
270 
272  int generate_packed_row(const double *xlp, double *row,
273  int *rowind, double *rowelem,
274  int *card_row, double & rhs);
275 
277  void check_optsol(const int calling_place,
278  const double *xlp, const double *slack_val,
279  const int do_flip);
280 
282  void check_optsol(const int calling_place,
283  const double *xlp, const double *slack_val,
284  const double *ck_row, const double ck_rhs,
285  const int cut_number, const int do_flip);
286 
287  // Check that two vectors are different.
288  bool rs_are_different_vectors(const int *vect1,
289  const int *vect2,
290  const int dim);
291 
292  // Check that two vectors are different.
293  bool rs_are_different_vectors(const double *vect1,
294  const double *vect2,
295  const int dim);
296 
297  // Check that two matrices are different.
298  bool rs_are_different_matrices(const CoinPackedMatrix *mat1,
299  const CoinPackedMatrix *mat2,
300  const int nmaj,
301  const int nmin);
303 
304 
305  // Private member data
306 
310 
313 
315  int nrow;
316 
318  int ncol;
319 
321  const double *colLower;
322 
324  const double *colUpper;
325 
327  const double *rowLower;
328 
330  const double *rowUpper;
331 
333  const double *rowRhs;
334 
338 
342 
346 
350 
354 
358 
362 
365 
367  // slacks are considered continuous (no harm if this is not the case).
369 
373 
377 
379  int mTab;
380 
382  int nTab;
383 
386  int **pi_mat;
387 
391  double **contNonBasicTab;
392 
395  // Dimensions: mTab by card_intNonBasicVar.
396  double **intNonBasicTab;
397 
400  double *rhsTab ;
401 
403  const double *given_optsol;
404 
407 
411 
415 
418  int *up_is_lub;
419 
421  OsiSolverInterface *solver;
422 
424  const double *xlp;
425 
427  const double *rowActivity;
428 
430  const char *colType;
431 
434  const CoinPackedMatrix *byRow;
435 
437 };
438 
439 //#############################################################################
445 void CglRedSplitUnitTest(const OsiSolverInterface * siP,
446  const std::string mpdDir );
447 
448 
449 #endif
void setNormIsZero(double value)
Set the value of normIsZero, the threshold for considering a norm to be 0; Default: 1e-5...
void print() const
Print some of the data members.
void printOptTab(OsiSolverInterface *solver) const
Print the current simplex tableau.
void check_optsol(const int calling_place, const double *xlp, const double *slack_val, const int do_flip)
Check that the generated cuts do not cut a given optimal solution.
int * up_is_lub
Characteristic vector of the structural variables whose upper bound in absolute value is larger than ...
double getEPS_RELAX() const
Get the value of EPS_RELAX.
int nTab
Number of columns in the reduced tableau (= card_contNonBasicVar)
int generate_cgcut(double *row, double *rhs)
Generate a mixed integer Chvatal-Gomory cut, when all non basic variables are non negative and at the...
int card_nonBasicAtLower
Number of non basic variables (structural or slack) at their lower bound in the current lp solution...
int * nonBasicAtUpper
List of non basic variables (structural or slack) at their upper bound.
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
double getAway() const
Get value of away.
void setEPS_RELAX(double value)
Set the value of EPS_RELAX, value used for relaxing the right hand side of each generated cut; Defaul...
void reduce_contNonBasicTab()
Reduce rows of contNonBasicTab.
void setLimit(int limit)
Set limit, the maximum number of non zero coefficients in generated cut; Default: 50...
void update_redTab(int r1, int r2, int step)
Perform row r1 of tab := row r1 of tab - step * row r2 of tab.
*double row_scale_factor(double *row)
Return the scale factor for the row.
void find_step(int r1, int r2, int *step, double *reduc, double *norm)
Find optimal integer step for changing row r1 by adding to it a multiple of another row r2...
const double * rowRhs
Righ hand side for constraints (upper bound for ranged constraints).
const double * rowLower
Lower bounds for constraints.
double getEPS_COEFF_LUB() const
Get the value of EPS_COEFF_LUB.
int * nonBasicAtLower
List of non basic variables (structural or slack) at their lower bound.
void set_given_optsol(const double *given_sol, const int card_sol)
Set given_optsol to the given optimal solution given_sol.
double rs_above_integer(double value)
Compute the fractional part of value, allowing for small error.
double getMinReduc() const
Get the value of minReduc.
Class collecting parameters the Reduced-and-split cut generator.
int getLimit() const
Get value of limit.
const double * colLower
Lower bounds for structural variables.
const double * colUpper
Upper bounds for structural variables.
int card_intNonBasicVar
Number of integer non basic structural variables in the current lp solution.
int * cv_intBasicVar_frac
Characteristic vector for integer basic structural variables with non integer value in the current lp...
double getLUB() const
Get the value of LUB.
int card_contNonBasicVar
Number of continuous non basic variables (structural or slack) in the current lp solution.
void generate_row(int index_row, double *row)
Generate a row of the current LP tableau.
CglRedSplit()
Default constructor.
int * intNonBasicVar
List of integer structural non basic variables.
int card_intBasicVar_frac
Number of integer basic structural variables that are fractional in the current lp solution (at least...
Gomory Reduce-and-Split Cut Generator Class; See method generateCuts().
Definition: CglRedSplit.hpp:23
void CglRedSplitUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglRedSplit class.
double getEPS_COEFF() const
Get the value of EPS_COEFF.
void setParam(const CglRedSplitParam &source)
Set given_optsol to the given optimal solution given_sol.
const CoinPackedMatrix * byRow
Pointer on matrix of coefficient ordered by rows.
int mTab
Number of rows in the reduced tableau (= card_intBasicVar_frac).
double ** intNonBasicTab
Current tableau for integer non basic structural variables.
int * intBasicVar_frac
List of integer structural basic variables (in order of pivot in selected rows for cut generation)...
int nrow
Number of rows ( = number of slack variables) in the current LP.
double getNormIsZero() const
Get the value of normIsZero.
void setMaxTab(double value)
Set the maximum allowed value for (mTab * mTab * CoinMax(mTab, nTab)) where mTab is the number of row...
void setEPS_COEFF(double value)
Set the value of EPS_COEFF, epsilon for values of coefficients; Default: 1e-8.
int card_nonBasicAtUpper
Number of non basic variables (structural or slack) at their upper bound in the current lp solution...
int * contNonBasicVar
List of continuous non basic variables (structural or slack).
void flip(double *row)
Change the sign of the coefficients of the continuous non basic variables at their upper bound...
Cut Generator Base Class.
virtual CglCutGenerator * clone() const
Clone.
void update_pi_mat(int r1, int r2, int step)
Perform row r1 of pi := row r1 of pi - step * row r2 of pi.
const double * xlp
Pointer on point to separate. Reset by each call to generateCuts().
bool rs_are_different_matrices(const CoinPackedMatrix *mat1, const CoinPackedMatrix *mat2, const int nmaj, const int nmin)
Compute the fractional part of value, allowing for small error.
double getEPS() const
Get the value of EPS.
double getMaxTab() const
Get the value of maxTab.
virtual bool needsOptimalBasis() const
Return true if needs optimal basis to do cuts (will return true)
CglRedSplit & operator=(const CglRedSplit &rhs)
Assignment operator.
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...
const double * rowUpper
Upper bounds for constraints.
void setEPS_COEFF_LUB(double value)
Set the value of EPS_COEFF_LUB, epsilon for values of coefficients for variables with absolute value ...
int test_pair(int r1, int r2, double *norm)
Test if an ordered pair of rows yields a reduction.
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...
int * low_is_lub
Characteristic vector of the structural variables whose lower bound in absolute value is larger than ...
virtual ~CglRedSplit()
Destructor.
OsiSolverInterface * solver
Pointer on solver. Reset by each call to generateCuts().
double ** contNonBasicTab
Current tableau for continuous non basic variables (structural or slack).
int ** pi_mat
Tableau of multipliers used to alter the rows used in generation.
const double * rowActivity
Pointer on row activity. Reset by each call to generateCuts().
const double * given_optsol
Given optimal solution that should not be cut; only for debug.
void setAway(double value)
Set away, the minimum distance from being integer used for selecting rows for cut generation; all row...
void setLUB(double value)
Set the value of LUB, value considered large for the absolute value of a lower or upper bound on a va...
void compute_is_integer()
Set given_optsol to the given optimal solution given_sol.
void setEPS(double value)
Set the value of EPS, epsilon for double computations; Default: 1e-7.
CglRedSplitParam param
Object with CglRedSplitParam members.
const char * colType
Pointer on column type. Reset by each call to generateCuts().
void setMinReduc(double value)
Set the value of minReduc, threshold for relative norm improvement for performing a reduction; Defaul...
void compute_is_lub()
Set given_optsol to the given optimal solution given_sol.
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:13
void unflip(double *row, double *rowrhs, double *slack_val)
Change the sign of the coefficients of the continuous non basic variables at their upper bound and do...
double * rhsTab
Right hand side of the tableau.
int card_given_optsol
Number of entries in given_optsol.
friend void CglRedSplitUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglRedSplit class.
int ncol
Number of structural variables in the current LP.
int generate_cgcut_2(int basic_ind, double *row, double *rhs)
Generate a mixed integer Chvatal-Gomory cut, when all non basic variables are non negative and at the...
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.
bool rs_are_different_vectors(const int *vect1, const int *vect2, const int dim)
Compute the fractional part of value, allowing for small error.
int * is_integer
Characteristic vectors of structural integer variables or continuous variables currently fixed to int...
CglRedSplitParam getParam() const
Set given_optsol to the given optimal solution given_sol.
Definition: CglRedSplit.hpp:76