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