Cgl 0.60.3
Loading...
Searching...
No Matches
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$
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
27
28 friend void CglRedSplitUnitTest(const OsiSolverInterface * siP,
29 const std::string mpdDir);
30public:
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.
79
80 // Compute entries of 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
177
180
183
185 virtual CglCutGenerator * clone() const;
186
190 const CglRedSplit& rhs);
191
193 virtual
196 virtual std::string generateCpp( FILE * fp);
198
199private:
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
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
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
391
394 // Dimensions: mTab by card_intNonBasicVar.
396
399 double *rhsTab ;
400
402 const double *given_optsol;
403
406
410
414
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//#############################################################################
444void CglRedSplitUnitTest(const OsiSolverInterface * siP,
445 const std::string mpdDir );
446
447
448#endif
void CglRedSplitUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglRedSplit class.
Cut Generator Base Class.
Class collecting parameters the Reduced-and-split cut generator.
Gomory Reduce-and-Split Cut Generator Class; See method generateCuts().
Definition: CglRedSplit.hpp:26
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.
const double * given_optsol
Given optimal solution that should not be cut; only for debug.
double getEPS_RELAX() const
Get the value of EPS_RELAX.
void setParam(const CglRedSplitParam &source)
CglRedSplit(const CglRedSplitParam &RS_param)
Constructor with specified parameters.
int * cv_intBasicVar_frac
Characteristic vector for integer basic structural variables with non integer value in the current lp...
bool rs_are_different_vectors(const int *vect1, const int *vect2, const int dim)
void set_given_optsol(const double *given_sol, const int card_sol)
Set given_optsol to the given optimal solution given_sol.
double row_scale_factor(double *row)
Return the scale factor for the row.
OsiSolverInterface * solver
Pointer on solver. Reset by each call to generateCuts().
int card_nonBasicAtUpper
Number of non basic variables (structural or slack) at their upper bound in the current lp solution.
double getLUB() const
Get the value of LUB.
int * is_integer
Characteristic vectors of structural integer variables or continuous variables currently fixed to int...
virtual bool needsOptimalBasis() const
Return true if needs optimal basis to do cuts (will return true)
double getMinReduc() const
Get the value of minReduc.
void setEPS_COEFF_LUB(double value)
Set the value of EPS_COEFF_LUB, epsilon for values of coefficients for variables with absolute value ...
const char * colType
Pointer on column type. Reset by each call to generateCuts().
void flip(double *row)
Change the sign of the coefficients of the continuous non basic variables at their upper bound.
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...
void setNormIsZero(double value)
Set the value of normIsZero, the threshold for considering a norm to be 0; Default: 1e-5.
void setEPS_RELAX(double value)
Set the value of EPS_RELAX, value used for relaxing the right hand side of each generated cut; Defaul...
int test_pair(int r1, int r2, double *norm)
Test if an ordered pair of rows yields a reduction.
int * contNonBasicVar
List of continuous non basic variables (structural or slack).
CglRedSplitParam param
Object with CglRedSplitParam members.
double getEPS_COEFF() const
Get the value of EPS_COEFF.
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 nrow
Number of rows ( = number of slack variables) in the current LP.
void reduce_contNonBasicTab()
Reduce rows of contNonBasicTab.
void print() const
Print some of the data members
void setAway(double value)
Set away, the minimum distance from being integer used for selecting rows for cut generation; all row...
virtual CglCutGenerator * clone() const
Clone.
const double * colLower
Lower bounds for structural variables.
double * rhsTab
Right hand side of the tableau.
double getMaxTab() const
Get the value of maxTab.
int nTab
Number of columns in the reduced tableau (= card_contNonBasicVar)
double rs_above_integer(double value)
Compute the fractional part of value, allowing for small error.
int * nonBasicAtLower
List of non basic variables (structural or slack) at their lower bound.
CglRedSplit & operator=(const CglRedSplit &rhs)
Assignment operator.
const double * xlp
Pointer on point to separate. Reset by each call to generateCuts().
int * up_is_lub
Characteristic vector of the structural variables whose upper bound in absolute value is larger than ...
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
int * intBasicVar_frac
List of integer structural basic variables (in order of pivot in selected rows for cut generation).
CglRedSplitParam getParam() const
Definition: CglRedSplit.hpp:75
double getEPS_COEFF_LUB() const
Get the value of EPS_COEFF_LUB.
void update_redTab(int r1, int r2, int step)
Perform row r1 of tab := row r1 of tab - step * row r2 of tab.
const CoinPackedMatrix * byRow
Pointer on matrix of coefficient ordered by rows.
int card_nonBasicAtLower
Number of non basic variables (structural or slack) at their lower bound in the current lp 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...
int mTab
Number of rows in the reduced tableau (= card_intBasicVar_frac).
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.
const double * rowUpper
Upper bounds for constraints.
virtual ~CglRedSplit()
Destructor.
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...
double ** contNonBasicTab
Current tableau for continuous non basic variables (structural or slack).
void setEPS(double value)
Set the value of EPS, epsilon for double computations; Default: 1e-7.
void setLimit(int limit)
Set limit, the maximum number of non zero coefficients in generated cut; Default: 50.
void compute_is_lub()
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 card_intBasicVar_frac
Number of integer basic structural variables that are fractional in the current lp solution (at least...
bool rs_are_different_matrices(const CoinPackedMatrix *mat1, const CoinPackedMatrix *mat2, const int nmaj, const int nmin)
int card_given_optsol
Number of entries in given_optsol.
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.
int card_intNonBasicVar
Number of integer non basic structural variables in the current lp solution.
int ncol
Number of structural variables in the current LP.
CglRedSplit()
Default constructor.
void setEPS_COEFF(double value)
Set the value of EPS_COEFF, epsilon for values of coefficients; Default: 1e-8.
int ** pi_mat
Tableau of multipliers used to alter the rows used in generation.
const double * colUpper
Upper bounds for structural variables.
int * nonBasicAtUpper
List of non basic variables (structural or slack) at their upper bound.
double getAway() const
Get value of away.
bool rs_are_different_vectors(const double *vect1, const double *vect2, const int dim)
const double * rowActivity
Pointer on row activity. Reset by each call to generateCuts().
double getEPS() const
Get the value of EPS.
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 * rowLower
Lower bounds for constraints.
void generateCuts(OsiCuts &cs)
const double * rowRhs
Righ hand side for constraints (upper bound for ranged constraints).
void generate_row(int index_row, double *row)
Generate a row of the current LP tableau.
void printOptTab(OsiSolverInterface *solver) const
Print the current simplex tableau
int getLimit() const
Get value of limit.
double getNormIsZero() const
Get the value of normIsZero.
double ** intNonBasicTab
Current tableau for integer non basic structural variables.
void check_optsol(const int calling_place, const double *xlp, const double *slack_val, const double *ck_row, const double ck_rhs, const int cut_number, const int do_flip)
Check that the generated cuts do not cut a given optimal solution.
void compute_is_integer()
int * low_is_lub
Characteristic vector of the structural variables whose lower bound in absolute value is larger than ...
void setMinReduc(double value)
Set the value of minReduc, threshold for relative norm improvement for performing a reduction; Defaul...
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(const CglRedSplit &)
Copy constructor.
int * intNonBasicVar
List of integer structural non basic variables.
friend void CglRedSplitUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglRedSplit class.
int card_contNonBasicVar
Number of continuous non basic variables (structural or slack) in the current lp solution.
void setMaxTab(double value)
Set the maximum allowed value for (mTab * mTab * CoinMax(mTab, nTab)) where mTab is the number of row...
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:15