Cgl 0.60.2

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

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
94 void printOptTab(OsiSolverInterface *solver) const;
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.
297 bool rs_are_different_matrices(const CoinPackedMatrix *mat1,
298 const CoinPackedMatrix *mat2,
299 const int nmaj,
300 const int nmin);
302
303
304 // Private member data
305
309
311 CglRedSplitParam param;
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
336 int card_intBasicVar_frac;
337
340 int card_intNonBasicVar;
341
344 int card_contNonBasicVar;
345
348 int card_nonBasicAtUpper;
349
352 int card_nonBasicAtLower;
353
356 int *cv_intBasicVar_frac;
357
360 int *intBasicVar_frac;
361
363 int *intNonBasicVar;
364
366 // slacks are considered continuous (no harm if this is not the case).
367 int *contNonBasicVar;
368
371 int *nonBasicAtUpper;
372
375 int *nonBasicAtLower;
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
405 int card_given_optsol;
406
409 int *is_integer;
410
413 int *low_is_lub;
414
417 int *up_is_lub;
418
420 OsiSolverInterface *solver;
421
423 const double *xlp;
424
426 const double *rowActivity;
427
429 const char *colType;
430
433 const CoinPackedMatrix *byRow;
434
436 };
437
438 //#############################################################################
444 void CglRedSplitUnitTest(const OsiSolverInterface * siP,
445 const std::string mpdDir );
446
447
448 #endif
CglRedSplit::needsOptimalBasis
virtual bool needsOptimalBasis() const
Return true if needs optimal basis to do cuts (will return true)
CglRedSplit::row_scale_factor
*double row_scale_factor(double *row)
Return the scale factor for the row.
CglRedSplit::getLUB
double getLUB() const
Get the value of LUB.
CglRedSplit::test_pair
int test_pair(int r1, int r2, double *norm)
Test if an ordered pair of rows yields a reduction.
CglRedSplit::CglRedSplitUnitTest
friend void CglRedSplitUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglRedSplit class.
CglRedSplit::generate_packed_row
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.
CglRedSplit::is_integer
int * is_integer
Characteristic vectors of structural integer variables or continuous variables currently fixed to int...
Definition: CglRedSplit.hpp:409
CglRedSplit::compute_is_integer
void compute_is_integer()
CglRedSplit::rowLower
const double * rowLower
Lower bounds for constraints.
Definition: CglRedSplit.hpp:326
CglRedSplitParam.hpp
CglRedSplit::intBasicVar_frac
int * intBasicVar_frac
List of integer structural basic variables (in order of pivot in selected rows for cut generation)...
Definition: CglRedSplit.hpp:360
CglRedSplit::generateCpp
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
CglRedSplit::xlp
const double * xlp
Pointer on point to separate. Reset by each call to generateCuts().
Definition: CglRedSplit.hpp:423
CglRedSplit::rs_are_different_matrices
bool rs_are_different_matrices(const CoinPackedMatrix *mat1, const CoinPackedMatrix *mat2, const int nmaj, const int nmin)
CglRedSplit::update_redTab
void update_redTab(int r1, int r2, int step)
Perform row r1 of tab := row r1 of tab - step * row r2 of tab.
CglRedSplit::rs_above_integer
double rs_above_integer(double value)
Compute the fractional part of value, allowing for small error.
CglRedSplit::getEPS_RELAX
double getEPS_RELAX() const
Get the value of EPS_RELAX.
CglRedSplit::contNonBasicTab
double ** contNonBasicTab
Current tableau for continuous non basic variables (structural or slack).
Definition: CglRedSplit.hpp:390
CglRedSplit::compute_is_lub
void compute_is_lub()
CglRedSplit::getEPS_COEFF_LUB
double getEPS_COEFF_LUB() const
Get the value of EPS_COEFF_LUB.
CglRedSplit::rhsTab
double * rhsTab
Right hand side of the tableau.
Definition: CglRedSplit.hpp:399
CglRedSplit::getEPS_COEFF
double getEPS_COEFF() const
Get the value of EPS_COEFF.
CglCutGenerator.hpp
CglRedSplit::card_nonBasicAtUpper
int card_nonBasicAtUpper
Number of non basic variables (structural or slack) at their upper bound in the current lp solution...
Definition: CglRedSplit.hpp:348
CglRedSplit::card_intNonBasicVar
int card_intNonBasicVar
Number of integer non basic structural variables in the current lp solution.
Definition: CglRedSplit.hpp:340
CglRedSplit::getMaxTab
double getMaxTab() const
Get the value of maxTab.
CglTreeInfo
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:15
OsiCuts
Collections of row cuts and column cuts.
Definition: OsiCuts.hpp:19
CglRedSplit::ncol
int ncol
Number of structural variables in the current LP.
Definition: CglRedSplit.hpp:317
CglRedSplit::intNonBasicTab
double ** intNonBasicTab
Current tableau for integer non basic structural variables.
Definition: CglRedSplit.hpp:395
CglRedSplit::colLower
const double * colLower
Lower bounds for structural variables.
Definition: CglRedSplit.hpp:320
CglRedSplit::setEPS_COEFF
void setEPS_COEFF(double value)
Set the value of EPS_COEFF, epsilon for values of coefficients; Default: 1e-8.
CglRedSplit::print
void print() const
Print some of the data members.
CglRedSplit::pi_mat
int ** pi_mat
Tableau of multipliers used to alter the rows used in generation.
Definition: CglRedSplit.hpp:385
CglRedSplit::flip
void flip(double *row)
Change the sign of the coefficients of the continuous non basic variables at their upper bound...
CglRedSplit::param
CglRedSplitParam param
Object with CglRedSplitParam members.
Definition: CglRedSplit.hpp:311
CglRedSplit
Gomory Reduce-and-Split Cut Generator Class; See method generateCuts().
Definition: CglRedSplit.hpp:26
OsiSolverInterface
Abstract Base Class for describing an interface to a solver.
Definition: OsiSolverInterface.hpp:61
CglRedSplit::card_intBasicVar_frac
int card_intBasicVar_frac
Number of integer basic structural variables that are fractional in the current lp solution (at least...
Definition: CglRedSplit.hpp:336
CglRedSplit::byRow
const CoinPackedMatrix * byRow
Pointer on matrix of coefficient ordered by rows.
Definition: CglRedSplit.hpp:433
CglRedSplit::CglRedSplit
CglRedSplit()
Default constructor.
CglRedSplit::setMinReduc
void setMinReduc(double value)
Set the value of minReduc, threshold for relative norm improvement for performing a reduction; Defaul...
CglRedSplit::getLimit
int getLimit() const
Get value of limit.
CglRedSplit::find_step
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...
CglRedSplit::setEPS_RELAX
void setEPS_RELAX(double value)
Set the value of EPS_RELAX, value used for relaxing the right hand side of each generated cut; Defaul...
CglCutGenerator
Cut Generator Base Class.
Definition: CglCutGenerator.hpp:23
CglRedSplit::update_pi_mat
void update_pi_mat(int r1, int r2, int step)
Perform row r1 of pi := row r1 of pi - step * row r2 of pi.
CglRedSplit::rs_are_different_vectors
bool rs_are_different_vectors(const int *vect1, const int *vect2, const int dim)
CglRedSplit::colUpper
const double * colUpper
Upper bounds for structural variables.
Definition: CglRedSplit.hpp:323
CglRedSplit::rowRhs
const double * rowRhs
Righ hand side for constraints (upper bound for ranged constraints).
Definition: CglRedSplit.hpp:332
CglRedSplit::reduce_contNonBasicTab
void reduce_contNonBasicTab()
Reduce rows of contNonBasicTab.
CglRedSplit::setEPS
void setEPS(double value)
Set the value of EPS, epsilon for double computations; Default: 1e-7.
CglRedSplit::mTab
int mTab
Number of rows in the reduced tableau (= card_intBasicVar_frac).
Definition: CglRedSplit.hpp:378
CglRedSplit::getMinReduc
double getMinReduc() const
Get the value of minReduc.
CglRedSplit::card_nonBasicAtLower
int card_nonBasicAtLower
Number of non basic variables (structural or slack) at their lower bound in the current lp solution...
Definition: CglRedSplit.hpp:352
CglRedSplit::getEPS
double getEPS() const
Get the value of EPS.
CglRedSplit::setParam
void setParam(const CglRedSplitParam &source)
CglRedSplit::nonBasicAtUpper
int * nonBasicAtUpper
List of non basic variables (structural or slack) at their upper bound.
Definition: CglRedSplit.hpp:371
CglRedSplit::rowUpper
const double * rowUpper
Upper bounds for constraints.
Definition: CglRedSplit.hpp:329
CglRedSplit::getNormIsZero
double getNormIsZero() const
Get the value of normIsZero.
CglRedSplit::setEPS_COEFF_LUB
void setEPS_COEFF_LUB(double value)
Set the value of EPS_COEFF_LUB, epsilon for values of coefficients for variables with absolute value ...
CglRedSplit::generate_cgcut_2
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...
CglRedSplit::solver
OsiSolverInterface * solver
Pointer on solver. Reset by each call to generateCuts().
Definition: CglRedSplit.hpp:420
CoinPackedMatrix
Sparse Matrix Base Class.
Definition: CoinPackedMatrix.hpp:79
CglRedSplit::low_is_lub
int * low_is_lub
Characteristic vector of the structural variables whose lower bound in absolute value is larger than ...
Definition: CglRedSplit.hpp:413
CglRedSplit::cv_intBasicVar_frac
int * cv_intBasicVar_frac
Characteristic vector for integer basic structural variables with non integer value in the current lp...
Definition: CglRedSplit.hpp:356
CglRedSplit::operator=
CglRedSplit & operator=(const CglRedSplit &rhs)
Assignment operator.
CglRedSplit::nTab
int nTab
Number of columns in the reduced tableau (= card_contNonBasicVar)
Definition: CglRedSplit.hpp:381
CglRedSplit::getAway
double getAway() const
Get value of away.
CglRedSplit::unflip
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...
CoinBigIndex
int CoinBigIndex
Definition: Coin_C_defines.h:136
CglRedSplit::getParam
CglRedSplitParam getParam() const
Definition: CglRedSplit.hpp:75
CglRedSplit::intNonBasicVar
int * intNonBasicVar
List of integer structural non basic variables.
Definition: CglRedSplit.hpp:363
CglRedSplit::clone
virtual CglCutGenerator * clone() const
Clone.
CglRedSplit::nonBasicAtLower
int * nonBasicAtLower
List of non basic variables (structural or slack) at their lower bound.
Definition: CglRedSplit.hpp:375
CglRedSplit::setMaxTab
void setMaxTab(double value)
Set the maximum allowed value for (mTab * mTab * CoinMax(mTab, nTab)) where mTab is the number of row...
CglRedSplit::nrow
int nrow
Number of rows ( = number of slack variables) in the current LP.
Definition: CglRedSplit.hpp:314
CglRedSplit::contNonBasicVar
int * contNonBasicVar
List of continuous non basic variables (structural or slack).
Definition: CglRedSplit.hpp:367
CglRedSplit::set_given_optsol
void set_given_optsol(const double *given_sol, const int card_sol)
Set given_optsol to the given optimal solution given_sol.
CglRedSplitUnitTest
void CglRedSplitUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglRedSplit class.
CglRedSplit::card_given_optsol
int card_given_optsol
Number of entries in given_optsol.
Definition: CglRedSplit.hpp:405
CglRedSplit::setNormIsZero
void setNormIsZero(double value)
Set the value of normIsZero, the threshold for considering a norm to be 0; Default: 1e-5...
CglRedSplit::~CglRedSplit
virtual ~CglRedSplit()
Destructor.
CglRedSplitParam
Class collecting parameters the Reduced-and-split cut generator.
Definition: CglRedSplitParam.hpp:61
CglRedSplit::generateCuts
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...
CglRedSplit::printOptTab
void printOptTab(OsiSolverInterface *solver) const
Print the current simplex tableau.
CglRedSplit::check_optsol
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.
CglRedSplit::setLUB
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...
CglRedSplit::setLimit
void setLimit(int limit)
Set limit, the maximum number of non zero coefficients in generated cut; Default: 50...
CglRedSplit::generate_cgcut
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...
CglRedSplit::given_optsol
const double * given_optsol
Given optimal solution that should not be cut; only for debug.
Definition: CglRedSplit.hpp:402
CglRedSplit::card_contNonBasicVar
int card_contNonBasicVar
Number of continuous non basic variables (structural or slack) in the current lp solution.
Definition: CglRedSplit.hpp:344
CglRedSplit::up_is_lub
int * up_is_lub
Characteristic vector of the structural variables whose upper bound in absolute value is larger than ...
Definition: CglRedSplit.hpp:417
CglRedSplit::colType
const char * colType
Pointer on column type. Reset by each call to generateCuts().
Definition: CglRedSplit.hpp:429
CglRedSplit::eliminate_slacks
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...
CglRedSplit::setAway
void setAway(double value)
Set away, the minimum distance from being integer used for selecting rows for cut generation; all row...
CglRedSplit::rowActivity
const double * rowActivity
Pointer on row activity. Reset by each call to generateCuts().
Definition: CglRedSplit.hpp:426
CglRedSplit::generate_row
void generate_row(int index_row, double *row)
Generate a row of the current LP tableau.