Cgl  0.59.9
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 
88  friend void CglMixedIntegerRoundingUnitTest(const OsiSolverInterface * siP,
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.
97  ROW_UNDEFINED,
101  ROW_VARUB,
105  ROW_VARLB,
108  ROW_VAREQ,
109  // The row contains continuous and integer variables;
110  // the total number of variables is at least 2
111  ROW_MIX,
112  // The row contains only continuous variables
113  ROW_CONT,
114  // The row contains only integer variables
115  ROW_INT,
116  // The row contains other types of rows
117  ROW_OTHER
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
231  void mixIntRoundPreprocess(const OsiSolverInterface& si);
232 
233  // Determine the type of a given row.
234  RowType determineRowType(const OsiSolverInterface& si,
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
271  bool selectRowToAggregate( const OsiSolverInterface& si,
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
366  int CRITERION_;
367  // Tolerance used for numerical purposes
368  double EPSILON_;
370  int UNDEFINED_;
371  // If violation of a cut is greater that this number, the cut is accepted
372  double TOLERANCE_;
380  int doPreproc_;
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.
386  bool doneInitPre_;
387  // The array of CglMixIntRoundVUBs.
388  CglMixIntRoundVUB* vubs_;
389  // The array of CglMixIntRoundVLBs.
390  CglMixIntRoundVLB* vlbs_;
391  // Array with the row types of the rows in the model.
392  RowType* rowTypes_;
393  // The indices of the rows of the initial matrix
394  int* indRows_;
395  // The number of rows of type ROW_MIX
396  int numRowMix_;
397  // The indices of the rows of type ROW_MIX
398  int* indRowMix_;
399  // The number of rows of type ROW_CONT
400  int numRowCont_;
401  // The indices of the rows of type ROW_CONT
402  int* indRowCont_;
403  // The number of rows of type ROW_INT
404  int numRowInt_;
405  // The indices of the rows of type ROW_INT
406  int* indRowInt_;
407  // The number of rows of type ROW_CONT that have at least one variable
408  // with variable upper or lower bound
409  int numRowContVB_;
410  // The indices of the rows of type ROW_CONT that have at least one variable
411  // with variable upper or lower bound
412  int* indRowContVB_;
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.
426 void CglMixedIntegerRoundingUnitTest(const OsiSolverInterface * siP,
427  const std::string mpdDir);
428 
429 #endif
void setMULTIPLY_(bool multiply)
Set MULTIPLY_.
void setCRITERION_(int criterion)
Set CRITERION_.
void setVal(const double v)
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:15
CglMixIntRoundVUB & operator=(const CglMixIntRoundVUB &rhs)
Mixed Integer Rounding Cut Generator Class.
int getCRITERION_() const
Get CRITERION_.
Cut Generator Base Class.
CglMixIntRoundVUB(const CglMixIntRoundVUB &source)
void CglMixedIntegerRoundingUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
bool getMULTIPLY_() const
Get MULTIPLY_.
CglMixIntRoundVUB CglMixIntRoundVLB
int getMAXAGGR_() const
Get MAXAGGR_.