Cbc  2.9.9
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
CglMixedIntegerRounding2.hpp
Go to the documentation of this file.
1 // LAST EDIT:
2 //-----------------------------------------------------------------------------
3 // name: Mixed Integer Rounding Cut Generator
4 // authors: Joao Goncalves (jog7@lehigh.edu)
5 // Laszlo Ladanyi (ladanyi@us.ibm.com)
6 // date: August 11, 2004
7 //-----------------------------------------------------------------------------
8 // Copyright (C) 2004, International Business Machines Corporation and others.
9 // All Rights Reserved.
10 // This code is published under the Eclipse Public License.
11 
12 #ifndef CglMixedIntegerRounding2_H
13 #define CglMixedIntegerRounding2_H
14 
15 #include <iostream>
16 #include <fstream>
17 //#include <vector>
18 
19 #include "CoinError.hpp"
20 
21 #include "CglCutGenerator.hpp"
22 #include "CoinIndexedVector.hpp"
23 
24 //=============================================================================
25 
26 #ifndef CGL_DEBUG
27 #define CGL_DEBUG 0
28 #endif
29 
30 //=============================================================================
31 
32 // Class to store variable upper bounds (VUB)
34 {
35  // Variable upper bounds have the form x_j <= a y_j, where x_j is
36  // a continuous variable and y_j is an integer variable
37 
38 protected:
39  int var_; // The index of y_j
40  double val_; // The value of a
41 
42 public:
43  // Default constructor
44  CglMixIntRoundVUB2() : var_(-1), val_(-1) {}
45 
46  // Copy constructor
48  var_ = source.var_;
49  val_ = source.val_;
50  }
51 
52  // Assignment operator
54  if (this != &rhs) {
55  var_ = rhs.var_;
56  val_ = rhs.val_;
57  }
58  return *this;
59  }
60 
61  // Destructor
63 
64  // Query and set functions
65  int getVar() const { return var_; }
66  double getVal() const { return val_; }
67  void setVar(const int v) { var_ = v; }
68  void setVal(const double v) { val_ = v; }
69 };
70 
71 //=============================================================================
72 
73 // Class to store variable lower bounds (VLB).
74 // It is the same as the class to store variable upper bounds
76 
77 //=============================================================================
78 
81 // Reference:
82 // Hugues Marchand and Laurence A. Wolsey
83 // Aggregation and Mixed Integer Rounding to Solve MIPs
84 // Operations Research, 49(3), May-June 2001.
85 // Also published as CORE Dicusion Paper 9839, June 1998.
86 
88 
90  const std::string mpdDir);
91 
92 
93 private:
94  //---------------------------------------------------------------------------
95  // Enumeration constants that describe the various types of rows
96  enum RowType {
97  // The row type of this row is NOT defined yet.
110  // The row contains continuous and integer variables;
111  // the total number of variables is at least 2
113  // The row contains only continuous variables
115  // The row contains only integer variables
117  // The row contains other types of rows
119  };
120 
121 
122 public:
123 
130  virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
131  const CglTreeInfo info = CglTreeInfo());
133 
134  //---------------------------------------------------------------------------
139 
141  CglMixedIntegerRounding2 (const int maxaggr,
142  const bool multiply,
143  const int criterion,
144  const int preproc = -1);
145 
148  const CglMixedIntegerRounding2 &);
149 
151  virtual CglCutGenerator * clone() const;
152 
155  operator=(
156  const CglMixedIntegerRounding2& rhs);
157 
159  virtual
162  virtual void refreshSolver(OsiSolverInterface * solver);
164  virtual std::string generateCpp( FILE * fp);
166 
167  //---------------------------------------------------------------------------
170  inline void setMAXAGGR_ (int maxaggr) {
172  if (maxaggr > 0) {
173  MAXAGGR_ = maxaggr;
174  }
175  else {
176  throw CoinError("Unallowable value. maxaggr must be > 0",
177  "gutsOfConstruct","CglMixedIntegerRounding2");
178  }
179  }
180 
182  inline int getMAXAGGR_ () const { return MAXAGGR_; }
183 
185  inline void setMULTIPLY_ (bool multiply) { MULTIPLY_ = multiply; }
186 
188  inline bool getMULTIPLY_ () const { return MULTIPLY_; }
189 
191  inline void setCRITERION_ (int criterion) {
192  if ((criterion >= 1) && (criterion <= 3)) {
193  CRITERION_ = criterion;
194  }
195  else {
196  throw CoinError("Unallowable value. criterion must be 1, 2 or 3",
197  "gutsOfConstruct","CglMixedIntegerRounding2");
198  }
199  }
200 
202  inline int getCRITERION_ () const { return CRITERION_; }
203 
205  void setDoPreproc(int value);
207  bool getDoPreproc() const;
209 
210 private:
211  //--------------------------------------------------------------------------
212  // Private member methods
213 
214  // Construct
215  void gutsOfConstruct ( const int maxaggr,
216  const bool multiply,
217  const int criterion,
218  const int preproc);
219 
220  // Delete
221  void gutsOfDelete();
222 
223  // Copy
224  void gutsOfCopy (const CglMixedIntegerRounding2& rhs);
225 
226  // Do preprocessing.
227  // It determines the type of each row. It also identifies the variable
228  // upper bounds and variable lower bounds.
229  // It may change sense and RHS for ranged rows
231 
232  // Determine the type of a given row.
233  RowType determineRowType(//const OsiSolverInterface& si,
234  const int rowLen, const int* ind,
235  const double* coef, const char sense,
236  const double rhs) const;
237 
238  // Generate MIR cuts
239  void generateMirCuts( const OsiSolverInterface& si,
240  const double* xlp,
241  const double* colUpperBound,
242  const double* colLowerBound,
243  const CoinPackedMatrix& matrixByRow,
244  const double* LHS,
245  //const double* coefByRow,
246  //const int* colInds,
247  //const int* rowStarts,
248  //const CoinPackedMatrix& matrixByCol,
249  const double* coefByCol,
250  const int* rowInds,
251  const int* colStarts,
252  OsiCuts& cs ) const;
253 
254  // Copy row selected to CoinIndexedVector
255  void copyRowSelected( const int iAggregate,
256  const int rowSelected,
257  CoinIndexedVector& setRowsAggregated,
258  int* listRowsAggregated,
259  double* xlpExtra,
260  const char sen,
261  const double rhs,
262  const double lhs,
263  const CoinPackedMatrix& matrixByRow,
264  CoinIndexedVector& rowToAggregate,
265  double& rhsToAggregate) const;
266 
267  // Select a row to aggregate
268  bool selectRowToAggregate( //const OsiSolverInterface& si,
269  const CoinIndexedVector& rowAggregated,
270  const double* colUpperBound,
271  const double* colLowerBound,
272  const CoinIndexedVector& setRowsAggregated,
273  const double* xlp, const double* coefByCol,
274  const int* rowInds, const int* colStarts,
275  int& rowSelected,
276  int& colSelected ) const;
277 
278  // Aggregation heuristic.
279  // Combines one or more rows of the original matrix
280  void aggregateRow( const int colSelected,
281  CoinIndexedVector& rowToAggregate, double rhs,
282  CoinIndexedVector& rowAggregated,
283  double& rhsAggregated ) const;
284 
285  // Choose the bound substitution based on the criteria defined by the user
286  inline bool isLowerSubst(const double inf,
287  const double aj,
288  const double xlp,
289  const double LB,
290  const double UB) const;
291 
292  // Bound substitution heuristic
293  bool boundSubstitution( const OsiSolverInterface& si,
294  const CoinIndexedVector& rowAggregated,
295  const double* xlp,
296  const double* xlpExtra,
297  const double* colUpperBound,
298  const double* colLowerBound,
299  CoinIndexedVector& mixedKnapsack,
300  double& rhsMixedKnapsack, double& sStar,
301  CoinIndexedVector& contVariablesInS ) const;
302 
303  // c-MIR separation heuristic
304  bool cMirSeparation ( const OsiSolverInterface& si,
305  const CoinPackedMatrix& matrixByRow,
306  const CoinIndexedVector& rowAggregated,
307  const int* listRowsAggregated,
308  const char* sense, const double* RHS,
309  //const double* coefByRow,
310  //const int* colInds, const int* rowStarts,
311  const double* xlp, const double sStar,
312  const double* colUpperBound,
313  const double* colLowerBound,
314  const CoinIndexedVector& mixedKnapsack,
315  const double& rhsMixedKnapsack,
316  const CoinIndexedVector& contVariablesInS,
317  CoinIndexedVector * workVector,
318  OsiRowCut& flowCut ) const;
319 
320  // function to create one c-MIR inequality
321  void cMirInequality( const int numInt,
322  const double delta,
323  const double numeratorBeta,
324  const int *knapsackIndices,
325  const double* knapsackElements,
326  const double* xlp,
327  const double sStar,
328  const double* colUpperBound,
329  const CoinIndexedVector& setC,
330  CoinIndexedVector& cMIR,
331  double& rhscMIR,
332  double& sCoef,
333  double& violation) const;
334 
335  // function to compute G
336  inline double functionG( const double d, const double f ) const;
337 
338  // function to print statistics (used only in debug mode)
339  void printStats(
340  std::ofstream & fout,
341  const bool hasCut,
342  const OsiSolverInterface& si,
343  const CoinIndexedVector& rowAggregated,
344  const double& rhsAggregated, const double* xlp,
345  const double* xlpExtra,
346  const int* listRowsAggregated,
347  const int* listColsSelected,
348  const int level,
349  const double* colUpperBound,
350  const double* colLowerBound ) const;
351 
352 
353 private:
354  //---------------------------------------------------------------------------
355  // Private member data
356 
357  // Maximum number of rows to aggregate
358  int MAXAGGR_;
359  // Flag that indicates if an aggregated row is also multiplied by -1
360  bool MULTIPLY_;
361  // The criterion to use in the bound substitution
363  // Tolerance used for numerical purposes
364  double EPSILON_;
367  // If violation of a cut is greater that this number, the cut is accepted
368  double TOLERANCE_;
377  // The number of rows of the problem.
378  int numRows_;
379  // The number columns of the problem.
380  int numCols_;
381  // Indicates whether preprocessing has been done.
383  // The array of CglMixIntRoundVUB2s.
385  // The array of CglMixIntRoundVLB2s.
387  // Array with the row types of the rows in the model.
389  // The indices of the rows of the initial matrix
390  int* indRows_;
391  // The number of rows of type ROW_MIX
393  // The indices of the rows of type ROW_MIX
395  // The number of rows of type ROW_CONT
397  // The indices of the rows of type ROW_CONT
399  // The number of rows of type ROW_INT
401  // The indices of the rows of type ROW_INT
403  // The number of rows of type ROW_CONT that have at least one variable
404  // with variable upper or lower bound
406  // The indices of the rows of type ROW_CONT that have at least one variable
407  // with variable upper or lower bound
409  // If integer - for speed
410  char * integerType_;
411  // Sense of rows (modified if ranges)
412  char * sense_;
413  // RHS of rows (modified if ranges)
414  double * RHS_;
415 
416 };
417 
418 //#############################################################################
419 // A function that tests the methods in the CglMixedIntegerRounding2 class. The
420 // only reason for it not to be a member method is that this way it doesn't
421 // have to be compiled into the library. And that's a gain, because the
422 // library should be compiled with optimization on, but this method should be
423 // compiled with debugging.
425  const std::string mpdDir);
426 
427 #endif
Error Class thrown by an exception.
Definition: CoinError.hpp:42
void CglMixedIntegerRounding2UnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
RowType determineRowType(const int rowLen, const int *ind, const double *coef, const char sense, const double rhs) const
CglMixedIntegerRounding2()
Default constructor.
bool isLowerSubst(const double inf, const double aj, const double xlp, const double LB, const double UB) const
void setMULTIPLY_(bool multiply)
Set MULTIPLY_.
void setMAXAGGR_(int maxaggr)
Set MAXAGGR_.
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:15
friend void CglMixedIntegerRounding2UnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
Collections of row cuts and column cuts.
Definition: OsiCuts.hpp:19
bool cMirSeparation(const OsiSolverInterface &si, const CoinPackedMatrix &matrixByRow, const CoinIndexedVector &rowAggregated, const int *listRowsAggregated, const char *sense, const double *RHS, const double *xlp, const double sStar, const double *colUpperBound, const double *colLowerBound, const CoinIndexedVector &mixedKnapsack, const double &rhsMixedKnapsack, const CoinIndexedVector &contVariablesInS, CoinIndexedVector *workVector, OsiRowCut &flowCut) const
void setCRITERION_(int criterion)
Set CRITERION_.
void cMirInequality(const int numInt, const double delta, const double numeratorBeta, const int *knapsackIndices, const double *knapsackElements, const double *xlp, const double sStar, const double *colUpperBound, const CoinIndexedVector &setC, CoinIndexedVector &cMIR, double &rhscMIR, double &sCoef, double &violation) const
virtual CglCutGenerator * clone() const
Clone.
int getCRITERION_() const
Get CRITERION_.
Abstract Base Class for describing an interface to a solver.
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate Mixed Integer Rounding cuts for the model data contained in si.
CglMixedIntegerRounding2 & operator=(const CglMixedIntegerRounding2 &rhs)
Assignment operator.
bool boundSubstitution(const OsiSolverInterface &si, const CoinIndexedVector &rowAggregated, const double *xlp, const double *xlpExtra, const double *colUpperBound, const double *colLowerBound, CoinIndexedVector &mixedKnapsack, double &rhsMixedKnapsack, double &sStar, CoinIndexedVector &contVariablesInS) const
int UNDEFINED_
There is no variable upper bound or variable lower bound defined.
int doPreproc_
Controls the preprocessing of the matrix to identify rows suitable for cut generation.
The row sense is &#39;E&#39;, the row has exactly two variables: one is binary and the other is a continous...
Indexed Vector.
Cut Generator Base Class.
void setVal(const double v)
bool selectRowToAggregate(const CoinIndexedVector &rowAggregated, const double *colUpperBound, const double *colLowerBound, const CoinIndexedVector &setRowsAggregated, const double *xlp, const double *coefByCol, const int *rowInds, const int *colStarts, int &rowSelected, int &colSelected) const
void mixIntRoundPreprocess(const OsiSolverInterface &si)
virtual ~CglMixedIntegerRounding2()
Destructor.
CglMixIntRoundVUB2(const CglMixIntRoundVUB2 &source)
After the row is flipped to &#39;L&#39;, the row has exactly two variables: one is positive binary and the ot...
Row Cut Class.
Definition: OsiRowCut.hpp:29
Sparse Matrix Base Class.
void aggregateRow(const int colSelected, CoinIndexedVector &rowToAggregate, double rhs, CoinIndexedVector &rowAggregated, double &rhsAggregated) const
void gutsOfConstruct(const int maxaggr, const bool multiply, const int criterion, const int preproc)
After the row is flipped to &#39;L&#39;, the row has exactly two variables: one is negative binary and the ot...
double functionG(const double d, const double f) const
void gutsOfCopy(const CglMixedIntegerRounding2 &rhs)
CglMixIntRoundVUB2 & operator=(const CglMixIntRoundVUB2 &rhs)
void setDoPreproc(int value)
Set doPreproc.
bool getMULTIPLY_() const
Get MULTIPLY_.
void copyRowSelected(const int iAggregate, const int rowSelected, CoinIndexedVector &setRowsAggregated, int *listRowsAggregated, double *xlpExtra, const char sen, const double rhs, const double lhs, const CoinPackedMatrix &matrixByRow, CoinIndexedVector &rowToAggregate, double &rhsToAggregate) const
CglMixIntRoundVUB2 CglMixIntRoundVLB2
int getMAXAGGR_() const
Get MAXAGGR_.
virtual void refreshSolver(OsiSolverInterface *solver)
This can be used to refresh any inforamtion.
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
void printStats(std::ofstream &fout, const bool hasCut, const OsiSolverInterface &si, const CoinIndexedVector &rowAggregated, const double &rhsAggregated, const double *xlp, const double *xlpExtra, const int *listRowsAggregated, const int *listColsSelected, const int level, const double *colUpperBound, const double *colLowerBound) const
void generateMirCuts(const OsiSolverInterface &si, const double *xlp, const double *colUpperBound, const double *colLowerBound, const CoinPackedMatrix &matrixByRow, const double *LHS, const double *coefByCol, const int *rowInds, const int *colStarts, OsiCuts &cs) const
Mixed Integer Rounding Cut Generator Class.
bool getDoPreproc() const
Get doPreproc.