Cbc  2.10.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 // $Id: CglRedSplit.hpp 1387 2017-09-29 11:02:03Z forrest $
11 //-----------------------------------------------------------------------------
12 // Copyright (C) 2005, Francois Margot and others. All Rights Reserved.
13 // This code is licensed under the terms of the Eclipse Public License (EPL).
14 
15 #ifndef CglRedSplit_H
16 #define CglRedSplit_H
17 
18 #include "CglCutGenerator.hpp"
19 #include "CglRedSplitParam.hpp"
20 
26 class CglRedSplit : public CglCutGenerator {
27 
28  friend void CglRedSplitUnitTest(const OsiSolverInterface * siP,
29  const std::string mpdDir);
30 public:
61  virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
62  const CglTreeInfo info = CglTreeInfo());
63 
65  virtual bool needsOptimalBasis() const;
67 
68 
71 
72  // Set the parameters to the values of the given CglRedSplitParam object.
73  void setParam(const CglRedSplitParam &source);
74  // Return the CglRedSplitParam object of the generator.
75  inline CglRedSplitParam getParam() const {return param;}
76 
77  // Compute entries of low_is_lub and up_is_lub.
78  void compute_is_lub();
79 
80  // Compute entries of is_integer.
81  void compute_is_integer();
82 
88  void set_given_optsol(const double *given_sol, const int card_sol);
89 
91  void print() const;
92 
95 
97 
100  //************************************************************
101  // TO BE REMOVED
104  void setLimit(int limit);
106  int getLimit() const;
107 
112  void setAway(double value);
114  double getAway() const;
118  void setLUB(double value);
120  double getLUB() const;
121 
124  void setEPS(double value);
126  double getEPS() const;
127 
130  void setEPS_COEFF(double value);
132  double getEPS_COEFF() const;
133 
137  void setEPS_COEFF_LUB(double value);
139  double getEPS_COEFF_LUB() const;
140 
144  void setEPS_RELAX(double value);
146  double getEPS_RELAX() const;
147 
150  void setNormIsZero(double value);
152  double getNormIsZero() const;
153 
156  void setMinReduc(double value);
158  double getMinReduc() const;
159 
165  void setMaxTab(double value);
167  double getMaxTab() const;
168  // END TO BE REMOVED
169  //************************************************************
170 
172 
175  CglRedSplit();
177 
179  CglRedSplit(const CglRedSplitParam &RS_param);
180 
182  CglRedSplit (const CglRedSplit &);
183 
185  virtual CglCutGenerator * clone() const;
186 
188  CglRedSplit &
189  operator=(
190  const CglRedSplit& rhs);
191 
193  virtual
194  ~CglRedSplit ();
196  virtual std::string generateCpp( FILE * fp);
198 
199 private:
200 
201  // Private member methods
202 
206 
207  // Method generating the cuts after all CglRedSplit members are properly set.
208  void generateCuts(OsiCuts & cs);
209 
211  inline double rs_above_integer(double value);
212 
214  void update_pi_mat(int r1, int r2, int step);
215 
217  void update_redTab(int r1, int r2, int step);
218 
221  void find_step(int r1, int r2, int *step,
222  double *reduc, double *norm);
223 
226  int test_pair(int r1, int r2, double *norm);
227 
229  void reduce_contNonBasicTab();
230 
232  void generate_row(int index_row, double *row);
233 
236  int generate_cgcut(double *row, double *rhs);
237 
240  int generate_cgcut_2(int basic_ind, double *row, double *rhs);
241 
244  void eliminate_slacks(double *row,
245  const double *elements,
246  const CoinBigIndex *start,
247  const int *indices,
248  const int *rowLength,
249  const double *rhs, double *rowrhs);
250 
253  void flip(double *row);
254 
259  void unflip(double *row, double *rowrhs, double *slack_val);
260 
268  double row_scale_factor(double *row);
269 
271  int generate_packed_row(const double *xlp, double *row,
272  int *rowind, double *rowelem,
273  int *card_row, double & rhs);
274 
276  void check_optsol(const int calling_place,
277  const double *xlp, const double *slack_val,
278  const int do_flip);
279 
281  void check_optsol(const int calling_place,
282  const double *xlp, const double *slack_val,
283  const double *ck_row, const double ck_rhs,
284  const int cut_number, const int do_flip);
285 
286  // Check that two vectors are different.
287  bool rs_are_different_vectors(const int *vect1,
288  const int *vect2,
289  const int dim);
290 
291  // Check that two vectors are different.
292  bool rs_are_different_vectors(const double *vect1,
293  const double *vect2,
294  const int dim);
295 
296  // Check that two matrices are different.
298  const CoinPackedMatrix *mat2,
299  const int nmaj,
300  const int nmin);
302 
303 
304  // Private member data
305 
309 
312 
314  int nrow;
315 
317  int ncol;
318 
320  const double *colLower;
321 
323  const double *colUpper;
324 
326  const double *rowLower;
327 
329  const double *rowUpper;
330 
332  const double *rowRhs;
333 
337 
341 
345 
349 
353 
357 
361 
364 
366  // slacks are considered continuous (no harm if this is not the case).
368 
372 
376 
378  int mTab;
379 
381  int nTab;
382 
385  int **pi_mat;
386 
390  double **contNonBasicTab;
391 
394  // Dimensions: mTab by card_intNonBasicVar.
395  double **intNonBasicTab;
396 
399  double *rhsTab ;
400 
402  const double *given_optsol;
403 
406 
410 
414 
417  int *up_is_lub;
418 
421 
423  const double *xlp;
424 
426  const double *rowActivity;
427 
429  const char *colType;
430 
434 
436 };
437 
438 //#############################################################################
444 void CglRedSplitUnitTest(const OsiSolverInterface * siP,
445  const std::string mpdDir );
446 
447 
448 #endif
virtual bool needsOptimalBasis() const
Return true if needs optimal basis to do cuts (will return true)
*double row_scale_factor(double *row)
Return the scale factor for the row.
double getLUB() const
Get the value of LUB.
int test_pair(int r1, int r2, double *norm)
Test if an ordered pair of rows yields a reduction.
friend void CglRedSplitUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglRedSplit class.
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.
int * is_integer
Characteristic vectors of structural integer variables or continuous variables currently fixed to int...
void compute_is_integer()
const double * rowLower
Lower bounds for constraints.
int * intBasicVar_frac
List of integer structural basic variables (in order of pivot in selected rows for cut generation)...
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
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)
void update_redTab(int r1, int r2, int step)
Perform row r1 of tab := row r1 of tab - step * row r2 of tab.
double rs_above_integer(double value)
Compute the fractional part of value, allowing for small error.
double getEPS_RELAX() const
Get the value of EPS_RELAX.
double ** contNonBasicTab
Current tableau for continuous non basic variables (structural or slack).
void compute_is_lub()
double getEPS_COEFF_LUB() const
Get the value of EPS_COEFF_LUB.
double * rhsTab
Right hand side of the tableau.
double getEPS_COEFF() const
Get the value of EPS_COEFF.
int card_nonBasicAtUpper
Number of non basic variables (structural or slack) at their upper bound in the current lp solution...
int card_intNonBasicVar
Number of integer non basic structural variables in the current lp solution.
double getMaxTab() const
Get the value of maxTab.
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:15
Collections of row cuts and column cuts.
Definition: OsiCuts.hpp:19
int ncol
Number of structural variables in the current LP.
double ** intNonBasicTab
Current tableau for integer non basic structural variables.
const double * colLower
Lower bounds for structural variables.
void setEPS_COEFF(double value)
Set the value of EPS_COEFF, epsilon for values of coefficients; Default: 1e-8.
void print() const
Print some of the data members.
int ** pi_mat
Tableau of multipliers used to alter the rows used in generation.
void flip(double *row)
Change the sign of the coefficients of the continuous non basic variables at their upper bound...
CglRedSplitParam param
Object with CglRedSplitParam members.
Gomory Reduce-and-Split Cut Generator Class; See method generateCuts().
Definition: CglRedSplit.hpp:26
Abstract Base Class for describing an interface to a solver.
int card_intBasicVar_frac
Number of integer basic structural variables that are fractional in the current lp solution (at least...
const CoinPackedMatrix * byRow
Pointer on matrix of coefficient ordered by rows.
CglRedSplit()
Default constructor.
void setMinReduc(double value)
Set the value of minReduc, threshold for relative norm improvement for performing a reduction; Defaul...
int getLimit() const
Get value of limit.
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...
void setEPS_RELAX(double value)
Set the value of EPS_RELAX, value used for relaxing the right hand side of each generated cut; Defaul...
Cut Generator Base Class.
void update_pi_mat(int r1, int r2, int step)
Perform row r1 of pi := row r1 of pi - step * row r2 of pi.
bool rs_are_different_vectors(const int *vect1, const int *vect2, const int dim)
const double * colUpper
Upper bounds for structural variables.
const double * rowRhs
Righ hand side for constraints (upper bound for ranged constraints).
void reduce_contNonBasicTab()
Reduce rows of contNonBasicTab.
void setEPS(double value)
Set the value of EPS, epsilon for double computations; Default: 1e-7.
int mTab
Number of rows in the reduced tableau (= card_intBasicVar_frac).
double getMinReduc() const
Get the value of minReduc.
int card_nonBasicAtLower
Number of non basic variables (structural or slack) at their lower bound in the current lp solution...
double getEPS() const
Get the value of EPS.
void setParam(const CglRedSplitParam &source)
int * nonBasicAtUpper
List of non basic variables (structural or slack) at their upper bound.
const double * rowUpper
Upper bounds for constraints.
double getNormIsZero() const
Get the value of normIsZero.
void setEPS_COEFF_LUB(double value)
Set the value of EPS_COEFF_LUB, epsilon for values of coefficients for variables with absolute value ...
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...
OsiSolverInterface * solver
Pointer on solver. Reset by each call to generateCuts().
Sparse Matrix Base Class.
int * low_is_lub
Characteristic vector of the structural variables whose lower bound in absolute value is larger than ...
int * cv_intBasicVar_frac
Characteristic vector for integer basic structural variables with non integer value in the current lp...
CglRedSplit & operator=(const CglRedSplit &rhs)
Assignment operator.
int nTab
Number of columns in the reduced tableau (= card_contNonBasicVar)
double getAway() const
Get value of away.
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...
int CoinBigIndex
CglRedSplitParam getParam() const
Definition: CglRedSplit.hpp:75
int * intNonBasicVar
List of integer structural non basic variables.
virtual CglCutGenerator * clone() const
Clone.
int * nonBasicAtLower
List of non basic variables (structural or slack) at their lower bound.
void setMaxTab(double value)
Set the maximum allowed value for (mTab * mTab * CoinMax(mTab, nTab)) where mTab is the number of row...
int nrow
Number of rows ( = number of slack variables) in the current LP.
int * contNonBasicVar
List of continuous non basic variables (structural or slack).
void set_given_optsol(const double *given_sol, const int card_sol)
Set given_optsol to the given optimal solution given_sol.
void CglRedSplitUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglRedSplit class.
int card_given_optsol
Number of entries in given_optsol.
void setNormIsZero(double value)
Set the value of normIsZero, the threshold for considering a norm to be 0; Default: 1e-5...
virtual ~CglRedSplit()
Destructor.
Class collecting parameters the Reduced-and-split cut generator.
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 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.
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 setLimit(int limit)
Set limit, the maximum number of non zero coefficients in generated cut; Default: 50...
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...
const double * given_optsol
Given optimal solution that should not be cut; only for debug.
int card_contNonBasicVar
Number of continuous non basic variables (structural or slack) in the current lp solution.
int * up_is_lub
Characteristic vector of the structural variables whose upper bound in absolute value is larger than ...
const char * colType
Pointer on column type. Reset by each call to generateCuts().
void eliminate_slacks(double *row, const double *elements, const CoinBigIndex *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...
void setAway(double value)
Set away, the minimum distance from being integer used for selecting rows for cut generation; all row...
const double * rowActivity
Pointer on row activity. Reset by each call to generateCuts().
void generate_row(int index_row, double *row)
Generate a row of the current LP tableau.