Cgl 0.60.3
Loading...
Searching...
No Matches
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
38protected:
39 int var_; // The index of y_j
40 double val_; // The value of a
41
42public:
43 // Default constructor
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
89 friend void CglMixedIntegerRounding2UnitTest(const OsiSolverInterface * siP,
90 const std::string mpdDir);
91
92
93private:
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
122public:
123
130 virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
131 const CglTreeInfo info = CglTreeInfo());
133
134 //---------------------------------------------------------------------------
137
139
141 CglMixedIntegerRounding2 (const int maxaggr,
142 const bool multiply,
143 const int criterion,
144 const int preproc = -1);
145
149
151 virtual CglCutGenerator * clone() const;
152
156 const CglMixedIntegerRounding2& rhs);
157
159 virtual
162 virtual void refreshSolver(OsiSolverInterface * solver);
164 virtual std::string generateCpp( FILE * fp);
166
167 //---------------------------------------------------------------------------
170
171 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
210private:
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
222
223 // Copy
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
230 void mixIntRoundPreprocess(const OsiSolverInterface& si);
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 CoinBigIndex* 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 CoinBigIndex* 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)
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
353private:
354 //---------------------------------------------------------------------------
355 // Private member data
356
357 // Maximum number of rows to aggregate
359 // Flag that indicates if an aggregated row is also multiplied by -1
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
377 // The number of rows of the problem.
379 // The number columns of the problem.
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
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
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.
424void CglMixedIntegerRounding2UnitTest(const OsiSolverInterface * siP,
425 const std::string mpdDir);
426
427#endif
CglMixIntRoundVUB2 CglMixIntRoundVLB2
void CglMixedIntegerRounding2UnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
Cut Generator Base Class.
CglMixIntRoundVUB2(const CglMixIntRoundVUB2 &source)
CglMixIntRoundVUB2 & operator=(const CglMixIntRoundVUB2 &rhs)
void setVal(const double v)
Mixed Integer Rounding Cut Generator Class.
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 CoinBigIndex *colStarts, OsiCuts &cs) const
RowType determineRowType(const int rowLen, const int *ind, const double *coef, const char sense, const double rhs) const
void setMAXAGGR_(int maxaggr)
Set MAXAGGR_.
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
virtual ~CglMixedIntegerRounding2()
Destructor.
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
CglMixedIntegerRounding2(const CglMixedIntegerRounding2 &)
Copy constructor.
void gutsOfCopy(const CglMixedIntegerRounding2 &rhs)
CglMixedIntegerRounding2(const int maxaggr, const bool multiply, const int criterion, const int preproc=-1)
Alternate Constructor.
void setMULTIPLY_(bool multiply)
Set MULTIPLY_.
bool getMULTIPLY_() const
Get MULTIPLY_.
void setCRITERION_(int criterion)
Set CRITERION_.
void gutsOfConstruct(const int maxaggr, const bool multiply, const int criterion, const int preproc)
bool selectRowToAggregate(const CoinIndexedVector &rowAggregated, const double *colUpperBound, const double *colLowerBound, const CoinIndexedVector &setRowsAggregated, const double *xlp, const double *coefByCol, const int *rowInds, const CoinBigIndex *colStarts, int &rowSelected, int &colSelected) const
friend void CglMixedIntegerRounding2UnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
bool getDoPreproc() const
Get doPreproc.
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
bool isLowerSubst(const double inf, const double aj, const double xlp, const double LB, const double UB) const
void aggregateRow(const int colSelected, CoinIndexedVector &rowToAggregate, double rhs, CoinIndexedVector &rowAggregated, double &rhsAggregated) const
CglMixedIntegerRounding2()
Default constructor.
void mixIntRoundPreprocess(const OsiSolverInterface &si)
@ ROW_VARLB
After the row is flipped to 'L', the row has exactly two variables: one is positive binary and the ot...
@ 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,...
double functionG(const double d, const double f) const
int getCRITERION_() const
Get CRITERION_.
int doPreproc_
Controls the preprocessing of the matrix to identify rows suitable for cut generation.
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate Mixed Integer Rounding cuts for the model data contained in si.
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
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 setDoPreproc(int value)
Set doPreproc.
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.
virtual void refreshSolver(OsiSolverInterface *solver)
This can be used to refresh any inforamtion.
int UNDEFINED_
There is no variable upper bound or variable lower bound defined.
int getMAXAGGR_() const
Get MAXAGGR_.
CglMixedIntegerRounding2 & operator=(const CglMixedIntegerRounding2 &rhs)
Assignment operator.
Information about where the cut generator is invoked from.