1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
|
// $Id: CglSimpleRounding.hpp 1149 2013-10-21 18:23:53Z tkr $
// Copyright (C) 2000, International Business Machines
// Corporation and others. All Rights Reserved.
// This code is licensed under the terms of the Eclipse Public License (EPL).
#ifndef CglSimpleRounding_H
#define CglSimpleRounding_H
#include <string>
#include "CglCutGenerator.hpp"
#include "CoinPackedMatrix.hpp"
/** Simple Rounding Cut Generator Class
This class generates simple rounding cuts via the following method:
For each contraint,
attempt to derive a <= inequality in all integer variables
by netting out any continuous variables.
Divide the resulting integer inequality through by
the greatest common denomimator (gcd) of the lhs coefficients.
Round down the rhs.
Warning: Use with careful attention to data precision.
(Reference: Nemhauser and Wolsey, Integer and Combinatorial Optimization, 1988, pg 211.)
*/
class CglSimpleRounding : public CglCutGenerator {
friend void CglSimpleRoundingUnitTest(const OsiSolverInterface * siP,
const std::string mpdDir );
public:
/**@name Generate Cuts */
//@{
/** Generate simple rounding cuts for the model accessed through the solver interface.
Insert generated cuts into the cut set cs.
*/
virtual void generateCuts( const OsiSolverInterface & si, OsiCuts & cs,
const CglTreeInfo info = CglTreeInfo());
//@}
/**@name Constructors and destructors */
//@{
/// Default constructor
CglSimpleRounding ();
/// Copy constructor
CglSimpleRounding (
const CglSimpleRounding &);
/// Clone
virtual CglCutGenerator * clone() const;
/// Assignment operator
CglSimpleRounding &
operator=(
const CglSimpleRounding& rhs);
/// Destructor
virtual
~CglSimpleRounding ();
/// Create C++ lines to get to current state
virtual std::string generateCpp( FILE * fp);
//@}
private:
// Private member methods
/**@name Private methods */
//@{
/// Derive a <= inequality in integer variables from the rowIndex-th constraint
bool deriveAnIntegerRow(
const OsiSolverInterface & si,
int rowIndex,
const CoinShallowPackedVector & matrixRow,
CoinPackedVector & irow,
double & b,
bool * negative) const;
/** Given a vector of doubles, x, with size elements and a positive tolerance,
dataTol, this method returns the smallest power of 10 needed so that
x[i]*10**power "is integer" for all i=0,...,size-1.
** change of definition of dataTol so that it refers to original
data, not to scaled data as that seems to lead to problems.
So if xScaled is x[i]*10**power and xInt is rounded(xScaled)
then fabs(xScaled-xInt) <= dataTol*10**power. This means that
dataTol should be smaller - say 1.0e-12 rather tahn 1.0e-8
Returns -number of times overflowed if the power is so big that it will
cause overflow (i.e. integer stored will be bigger than 2**31).
Test in cut generator.
*/
int power10ToMakeDoubleAnInt(
int size, // the length of the vector x
const double * x,
double dataTol ) const; // the precision of the data, i.e. the positive
// epsilon, which is equivalent to zero
/**@name Greatest common denominators methods */
//@{
/// Returns the greatest common denominator of two positive integers, a and b.
inline int gcd(int a, int b) const;
/** Returns the greatest common denominator of a vector of
positive integers, vi, of length n.
*/
inline int gcdv(int n, const int * const vi) const;
//@}
//@}
/**@name Private member data */
//@{
/// A value within an epsilon_ neighborhood of 0 is considered to be 0.
double epsilon_;
//@}
};
//-------------------------------------------------------------------
// Returns the greatest common denominator of two
// positive integers, a and b, found using Euclid's algorithm
//-------------------------------------------------------------------
int
CglSimpleRounding::gcd(int a, int b) const
{
if(a > b) {
// Swap a and b
int temp = a;
a = b;
b = temp;
}
int remainder = b % a;
if (remainder == 0) return a;
else return gcd(remainder,a);
}
//-------------------------------------------------------------------
// Returns the greatest common denominator of a vector of
// positive integers, vi, of length n.
//-------------------------------------------------------------------
int
CglSimpleRounding::gcdv(int n, const int* const vi) const
{
if (n==0)
abort();
if (n==1)
return vi[0];
int retval=gcd(vi[0], vi[1]);
for (int i=2; i<n; i++){
retval=gcd(retval,vi[i]);
}
return retval;
}
//#############################################################################
/** A function that tests the methods in the CglSimpleRounding class. The
only reason for it not to be a member method is that this way it doesn't
have to be compiled into the library. And that's a gain, because the
library should be compiled with optimization on, but this method should be
compiled with debugging. */
void CglSimpleRoundingUnitTest(const OsiSolverInterface * siP,
const std::string mpdDir );
#endif
|
