Cgl 0.60.8
Loading...
Searching...
No Matches
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
32
33 friend void CglRedSplit2UnitTest(const OsiSolverInterface * siP,
34 const std::string mpdDir);
35public:
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
138 void printOptTab(OsiSolverInterface *solver) const;
139
141
146
149
152
154 virtual CglCutGenerator * clone() const;
155
158
160 virtual ~CglRedSplit2 ();
161
163
164private:
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 CoinBigIndex *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.
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
441
446
449 // Dimensions: mTab by card_intNonBasicVar.
451
454 double *rhsTab;
455
457 double *norm;
458
462
464 OsiSolverInterface *solver;
465
467 const double *xlp;
468
470 const double *rowActivity;
471
474 const CoinPackedMatrix *byRow;
475
478 double startTime;
479
481};
482
483//#############################################################################
490void CglRedSplit2UnitTest(const OsiSolverInterface * siP,
491 const std::string mpdDir );
492
493
494#endif
void CglRedSplit2UnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests some of the methods in the CglRedSplit2 class.
Cut Generator Base Class.
Class collecting parameters the Reduced-and-split cut generator.
RowSelectionStrategy
Enumerations for parameters.
ColumnSelectionStrategy
Column selection strategies; again, look them up in the paper.
double getTimeLimit() const
get the value
ColumnScalingStrategy
Scaling strategies for new nonbasic columns for Lift & Project; "factor" is the value of columnScalin...
Reduce-and-Split Cut Generator Class; See method generateCuts().
void setParam(const CglRedSplit2Param &source)
double rs_dotProd(const int *u, const double *v, int dim) const
const double * rowUpper
Upper bounds for constraints.
double rs_above_integer(const double value) const
Compute the fractional part of value, allowing for small error.
int card_nonBasicAtLower
Number of non basic variables (structural or slack) at their lower bound in the current lp solution.
friend void CglRedSplit2UnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests some of the methods in the CglRedSplit2 class.
int numRedRows
Number of rows which have been reduced.
int * cv_fracRowsTab
Characteristic vector for rows of the tableau selected for reduction with non integer value in the cu...
int generateMultipliers(const OsiSolverInterface &si, int *lambda, int maxNumMultipliers, int *basicVariables=NULL, OsiCuts *cs=NULL)
void print() const
Print some of the data members; used for debugging.
void unflip(double *row, double *rowrhs)
Change the sign of the coefficients of the continuous non basic variables at their upper bound and do...
const double * xlp
Pointer on point to separate. Reset by each call to generateCuts().
const double * objective
Objective coefficients.
double compute_norm_change(double oldnorm, const int *listOfRows, int numElemList, const double *multipliers) const
int * cv_intBasicVar_frac
Characteristic vector for integer basic structural variables with non integer value in the current lp...
double ** workNonBasicTab
Current tableau for continuous non basic variables (structural or slack).
int mTab
Number of rows in the reduced tableau (= card_intBasicVar).
int sort_rows_by_nonzeroes_greedy(struct sortElement *array, int rowIndex, int maxRows, int whichTab) const
void rs_allocmatDBL(double ***v, int m, int n)
int card_intBasicVar
Number of integer basic structural variables.
void rs_deallocmatDBL(double ***v, int m)
const double * rowRhs
Righ hand side for constraints (upper bound for ranged constraints).
int get_list_rows_reduction(int rowIndex, int numRowsReduction, int *list, const double *norm, CglRedSplit2Param::RowSelectionStrategy rowSelectionStrategy) const
const double * colUpper
Upper bounds for structural variables.
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...
void flip(double *row)
Change the sign of the coefficients of the continuous non basic variables at their upper bound.
int card_contNonBasicVar
Number of continuous non basic variables (structural or slack) in the current lp solution.
double ** intNonBasicTab
Simplex tableau for integer non basic structural variables.
void compute_is_integer()
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 fill_workNonBasicTab(const int *newnonbasics, const double *xbar, CglRedSplit2Param::ColumnScalingStrategy scaling)
Fill workNonBasicTab, alternate version for Lift & Project: also reduces columns which are now nonbas...
int tiltLandPcut(const OsiSolverInterface *si, double *row, double rowRhs, int rownumber, const double *xbar, const int *newnonbasics, OsiRowCut *cs, int *lambda=NULL)
void rs_printvecDBL(const char *vecstr, const double *x, int n) const
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 ** contNonBasicTab
Simplex tableau for continuous non basic variables (structural or slack).
int * cv_intBasicVar
Characteristic vector for integer basic structural variables.
int card_intNonBasicVar
Number of integer non basic structural variables in the current lp solution.
void rs_allocmatINT(int ***v, int m, int n)
double startTime
Time at which cut computations began.
CglRedSplit2()
Default constructor.
int ludcmp(double **a, int n, int *indx, double *d, double *vv) const
int generateCuts(OsiCuts *cs, int maxNumCuts, int *lambda=NULL)
double rs_dotProd(const double *u, const double *v, int dim) const
const double * reducedCost
Reduced costs for columns.
int nTab
Number of columns in the reduced tableau (= card_contNonBasicVar)
OsiSolverInterface * solver
Pointer on solver. Reset by each call to generateCuts().
int * intBasicVar_frac
List of integer structural basic variables with fractional value (in order of pivot in selected rows ...
void rs_printmatDBL(const char *vecstr, const double *const *x, int m, int n) const
int check_dynamism(double *row)
Returns 1 if the row has acceptable max/min coeff ratio.
CglRedSplit2 & operator=(const CglRedSplit2 &rhs)
Assignment operator.
CglRedSplit2(const CglRedSplit2Param &RS_param)
Constructor with specified parameters.
const double * rowLower
Lower bounds for constraints.
const double * rowPrice
Row price.
void rs_deallocmatINT(int ***v, int m)
CglRedSplit2Param & getParam()
int * nonBasicAtLower
List of non basic variables (structural or slack) at their lower bound.
CglRedSplit2Param param
Object with CglRedSplit2Param members.
const CoinPackedMatrix * byRow
Pointer on matrix of coefficient ordered by rows.
int nrow
Number of rows ( = number of slack variables) in the current LP.
int * nonBasicAtUpper
List of non basic variables (structural or slack) at their upper bound.
const double * rowActivity
Pointer on row activity. Reset by each call to generateCuts().
virtual CglCutGenerator * clone() const
Clone.
const double * colLower
Lower bounds for structural variables.
int * is_integer
Characteristic vectors of structural integer variables or continuous variables currently fixed to int...
bool checkTime() const
int ncol
Number of structural variables in the current LP.
void reduce_workNonBasicTab(int numRows, CglRedSplit2Param::RowSelectionStrategy rowSelectionStrategy, int maxIterations)
Reduce rows of workNonBasicTab, i.e.
int * intBasicVar
List of integer structural basic variables (in order of pivot in selected rows for cut generation).
CglRedSplit2(const CglRedSplit2 &)
Copy constructor.
void rs_printvecINT(const char *vecstr, const int *x, int n) const
void lubksb(double **a, int n, int *indx, double *b) const
virtual bool needsOptimalBasis() const
Return true if needs optimal basis to do cuts (will return true)
void printOptTab(OsiSolverInterface *solver) const
Print the current simplex tableau
void rs_printmatINT(const char *vecstr, const int *const *x, int m, int n) const
int card_nonBasicAtUpper
Number of non basic variables (structural or slack) at their upper bound in the current lp solution.
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 card_intBasicVar_frac
Number of integer basic structural variables that are fractional in the current lp solution (at least...
bool rs_are_different_vectors(const int *vect1, const int *vect2, const int dim)
int card_workNonBasicVar
Number of continuous non basic variables (structural or slack) in the current working set for coeffic...
virtual ~CglRedSplit2()
Destructor.
double * norm
Norm of rows in workNonBasicTab; needed for faster computations.
int sort_rows_by_nonzeroes(struct sortElement *array, int rowIndex, int maxRows, int whichTab) const
int sort_rows_by_cosine(struct sortElement *array, int rowIndex, int maxRows, int whichTab) const
int * contNonBasicVar
List of continuous non basic variables (structural or slack).
void fill_workNonBasicTab(CglRedSplit2Param::ColumnSelectionStrategy strategy, const int *ignore_list=NULL)
Fill workNonBasicTab, depending on the column selection strategy.
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 * intNonBasicVar
List of integer structural non basic variables.
double * rhsTab
Right hand side of the tableau.
int ** pi_mat
Tableau of multipliers used to alter the rows used in generation.
Information about where the cut generator is invoked from.