Cgl 0.60.3
Loading...
Searching...
No Matches
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
37protected:
38 int var_; // The index of y_j
39 double val_; // The value of a
40
41public:
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
92private:
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
121public:
122
129 virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
130 const CglTreeInfo info = CglTreeInfo());
132
133 //---------------------------------------------------------------------------
136
138
140 CglMixedIntegerRounding (const int maxaggr,
141 const bool multiply,
142 const int criterion,
143 const int preproc = -1);
144
148
150 virtual CglCutGenerator * clone() const;
151
155 const CglMixedIntegerRounding& rhs);
156
158 virtual
161 virtual void refreshSolver(OsiSolverInterface * solver);
163 virtual std::string generateCpp( FILE * fp);
165
166 //---------------------------------------------------------------------------
169
170 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
211private:
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
223
224 // Copy
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 CoinBigIndex* rowStarts,
249 const int* rowLengths,
250 //const CoinPackedMatrix& matrixByCol,
251 const double* coefByCol,
252 const int* rowInds,
253 const CoinBigIndex* 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 CoinBigIndex* 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)
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
357private:
358 //---------------------------------------------------------------------------
359 // Private member data
360
361 // Maximum number of rows to aggregate
363 // Flag that indicates if an aggregated row is also multiplied by -1
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
381 // The number of rows of the problem.
383 // The number columns of the problem.
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
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.
426void CglMixedIntegerRoundingUnitTest(const OsiSolverInterface * siP,
427 const std::string mpdDir);
428
429#endif
void CglMixedIntegerRoundingUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
CglMixIntRoundVUB CglMixIntRoundVLB
Cut Generator Base Class.
void setVal(const double v)
CglMixIntRoundVUB & operator=(const CglMixIntRoundVUB &rhs)
CglMixIntRoundVUB(const CglMixIntRoundVUB &source)
Mixed Integer Rounding Cut Generator Class.
bool getDoPreproc() const
Get doPreproc.
CglMixedIntegerRounding()
Default constructor.
CglMixedIntegerRounding & operator=(const CglMixedIntegerRounding &rhs)
Assignment operator.
friend void CglMixedIntegerRoundingUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
bool isLowerSubst(const double inf, const double aj, const double xlp, const double LB, const double UB) const
void gutsOfConstruct(const int maxaggr, const bool multiply, const int criterion, const int preproc)
int UNDEFINED_
There is no variable upper bound or variable lower bound defined.
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate Mixed Integer Rounding cuts for the model data contained in si.
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
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
CglMixedIntegerRounding(const int maxaggr, const bool multiply, const int criterion, const int preproc=-1)
Alternate Constructor.
int doPreproc_
Controls the preprocessing of the matrix to identify rows suitable for cut generation.
void setMULTIPLY_(bool multiply)
Set MULTIPLY_.
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 setMAXAGGR_(int maxaggr)
Set MAXAGGR_.
void setDoPreproc(int value)
Set doPreproc.
@ ROW_VARUB
After the row is flipped to 'L', the row has exactly two variables: one is negative binary and the ot...
@ ROW_VAREQ
The row sense is 'E', the row has exactly two variables: one is binary and the other is a continous,...
@ ROW_VARLB
After the row is flipped to 'L', the row has exactly two variables: one is positive binary and the ot...
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
virtual CglCutGenerator * clone() const
Clone.
bool getMULTIPLY_() const
Get MULTIPLY_.
virtual void refreshSolver(OsiSolverInterface *solver)
This can be used to refresh any inforamtion.
int getMAXAGGR_() const
Get MAXAGGR_.
void gutsOfCopy(const CglMixedIntegerRounding &rhs)
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
double functionG(const double d, const double f) const
void mixIntRoundPreprocess(const OsiSolverInterface &si)
void aggregateRow(const int colSelected, CoinPackedVector &rowToAggregate, double rhs, CoinPackedVector &rowAggregated, double &rhsAggregated) const
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 CoinBigIndex *colStarts, const int *colLengths, int &rowSelected, int &colSelected) const
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
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 CoinBigIndex *rowStarts, const int *rowLengths, const double *coefByCol, const int *rowInds, const CoinBigIndex *colStarts, const int *colLengths, OsiCuts &cs) const
void setCRITERION_(int criterion)
Set CRITERION_.
virtual ~CglMixedIntegerRounding()
Destructor.
CglMixedIntegerRounding(const CglMixedIntegerRounding &)
Copy constructor.
RowType determineRowType(const OsiSolverInterface &si, const int rowLen, const int *ind, const double *coef, const char sense, const double rhs) const
Information about where the cut generator is invoked from.