1 | // Copyright (C) 2003, International Business Machines |
---|
2 | // Corporation and others. All Rights Reserved. |
---|
3 | #if defined(_MSC_VER) |
---|
4 | // Turn off compiler warning about long names |
---|
5 | # pragma warning(disable:4786) |
---|
6 | #endif |
---|
7 | #include <cassert> |
---|
8 | #include <cmath> |
---|
9 | #include <cfloat> |
---|
10 | |
---|
11 | #include "OsiSolverInterface.hpp" |
---|
12 | #include "CbcModel.hpp" |
---|
13 | #include "CbcMessage.hpp" |
---|
14 | #include "CbcCutGenerator.hpp" |
---|
15 | #include "CglProbing.hpp" |
---|
16 | #include "CoinTime.hpp" |
---|
17 | |
---|
18 | // Default Constructor |
---|
19 | CbcCutGenerator::CbcCutGenerator () |
---|
20 | : model_(NULL), |
---|
21 | generator_(NULL), |
---|
22 | whenCutGenerator_(-1), |
---|
23 | whenCutGeneratorInSub_(-100), |
---|
24 | switchOffIfLessThan_(0), |
---|
25 | depthCutGenerator_(-1), |
---|
26 | depthCutGeneratorInSub_(-1), |
---|
27 | generatorName_(NULL), |
---|
28 | normal_(true), |
---|
29 | atSolution_(false), |
---|
30 | whenInfeasible_(false), |
---|
31 | timing_(false), |
---|
32 | timeInCutGenerator_(0.0), |
---|
33 | numberTimes_(0), |
---|
34 | numberCuts_(0), |
---|
35 | numberColumnCuts_(0), |
---|
36 | numberCutsActive_(0) |
---|
37 | { |
---|
38 | } |
---|
39 | // Normal constructor |
---|
40 | CbcCutGenerator::CbcCutGenerator(CbcModel * model,CglCutGenerator * generator, |
---|
41 | int howOften, const char * name, |
---|
42 | bool normal, bool atSolution, |
---|
43 | bool infeasible, int howOftenInSub, |
---|
44 | int whatDepth, int whatDepthInSub, |
---|
45 | int switchOffIfLessThan) |
---|
46 | : |
---|
47 | depthCutGenerator_(whatDepth), |
---|
48 | depthCutGeneratorInSub_(whatDepthInSub), |
---|
49 | timing_(false), |
---|
50 | timeInCutGenerator_(0.0), |
---|
51 | numberTimes_(0), |
---|
52 | numberCuts_(0), |
---|
53 | numberColumnCuts_(0), |
---|
54 | numberCutsActive_(0) |
---|
55 | { |
---|
56 | model_ = model; |
---|
57 | generator_=generator->clone(); |
---|
58 | generator_->refreshSolver(model_->solver()); |
---|
59 | whenCutGenerator_=howOften; |
---|
60 | whenCutGeneratorInSub_ = howOftenInSub; |
---|
61 | switchOffIfLessThan_=switchOffIfLessThan; |
---|
62 | if (name) |
---|
63 | generatorName_=strdup(name); |
---|
64 | else |
---|
65 | generatorName_ = strdup("Unknown"); |
---|
66 | normal_=normal; |
---|
67 | atSolution_=atSolution; |
---|
68 | whenInfeasible_=infeasible; |
---|
69 | } |
---|
70 | |
---|
71 | // Copy constructor |
---|
72 | CbcCutGenerator::CbcCutGenerator ( const CbcCutGenerator & rhs) |
---|
73 | { |
---|
74 | model_ = rhs.model_; |
---|
75 | generator_=rhs.generator_->clone(); |
---|
76 | generator_->refreshSolver(model_->solver()); |
---|
77 | whenCutGenerator_=rhs.whenCutGenerator_; |
---|
78 | whenCutGeneratorInSub_ = rhs.whenCutGeneratorInSub_; |
---|
79 | switchOffIfLessThan_ = rhs.switchOffIfLessThan_; |
---|
80 | depthCutGenerator_=rhs.depthCutGenerator_; |
---|
81 | depthCutGeneratorInSub_ = rhs.depthCutGeneratorInSub_; |
---|
82 | generatorName_=strdup(rhs.generatorName_); |
---|
83 | normal_=rhs.normal_; |
---|
84 | atSolution_=rhs.atSolution_; |
---|
85 | whenInfeasible_=rhs.whenInfeasible_; |
---|
86 | timing_ = rhs.timing_; |
---|
87 | timeInCutGenerator_ = rhs.timeInCutGenerator_; |
---|
88 | numberTimes_ = rhs.numberTimes_; |
---|
89 | numberCuts_ = rhs.numberCuts_; |
---|
90 | numberColumnCuts_ = rhs.numberColumnCuts_; |
---|
91 | numberCutsActive_ = rhs.numberCutsActive_; |
---|
92 | } |
---|
93 | |
---|
94 | // Assignment operator |
---|
95 | CbcCutGenerator & |
---|
96 | CbcCutGenerator::operator=( const CbcCutGenerator& rhs) |
---|
97 | { |
---|
98 | if (this!=&rhs) { |
---|
99 | delete generator_; |
---|
100 | free(generatorName_); |
---|
101 | model_ = rhs.model_; |
---|
102 | generator_=rhs.generator_->clone(); |
---|
103 | generator_->refreshSolver(model_->solver()); |
---|
104 | whenCutGenerator_=rhs.whenCutGenerator_; |
---|
105 | whenCutGeneratorInSub_ = rhs.whenCutGeneratorInSub_; |
---|
106 | switchOffIfLessThan_ = rhs.switchOffIfLessThan_; |
---|
107 | depthCutGenerator_=rhs.depthCutGenerator_; |
---|
108 | depthCutGeneratorInSub_ = rhs.depthCutGeneratorInSub_; |
---|
109 | generatorName_=strdup(rhs.generatorName_); |
---|
110 | normal_=rhs.normal_; |
---|
111 | atSolution_=rhs.atSolution_; |
---|
112 | whenInfeasible_=rhs.whenInfeasible_; |
---|
113 | timing_ = rhs.timing_; |
---|
114 | timeInCutGenerator_ = rhs.timeInCutGenerator_; |
---|
115 | numberTimes_ = rhs.numberTimes_; |
---|
116 | numberCuts_ = rhs.numberCuts_; |
---|
117 | numberColumnCuts_ = rhs.numberColumnCuts_; |
---|
118 | numberCutsActive_ = rhs.numberCutsActive_; |
---|
119 | } |
---|
120 | return *this; |
---|
121 | } |
---|
122 | |
---|
123 | // Destructor |
---|
124 | CbcCutGenerator::~CbcCutGenerator () |
---|
125 | { |
---|
126 | free(generatorName_); |
---|
127 | delete generator_; |
---|
128 | } |
---|
129 | |
---|
130 | /* This is used to refresh any inforamtion. |
---|
131 | It also refreshes the solver in the cut generator |
---|
132 | in case generator wants to do some work |
---|
133 | */ |
---|
134 | void |
---|
135 | CbcCutGenerator::refreshModel(CbcModel * model) |
---|
136 | { |
---|
137 | model_=model; |
---|
138 | generator_->refreshSolver(model_->solver()); |
---|
139 | } |
---|
140 | /* Generate cuts for the model data contained in si. |
---|
141 | The generated cuts are inserted into and returned in the |
---|
142 | collection of cuts cs. |
---|
143 | */ |
---|
144 | bool |
---|
145 | CbcCutGenerator::generateCuts( OsiCuts & cs , bool fullScan, CbcNode * node) |
---|
146 | { |
---|
147 | int howOften = whenCutGenerator_; |
---|
148 | if (howOften==-100) |
---|
149 | return false; |
---|
150 | if (howOften>0) |
---|
151 | howOften = howOften % 1000000; |
---|
152 | else |
---|
153 | howOften=1; |
---|
154 | if (!howOften) |
---|
155 | howOften=1; |
---|
156 | bool returnCode=false; |
---|
157 | OsiSolverInterface * solver = model_->solver(); |
---|
158 | int depth; |
---|
159 | if (node) |
---|
160 | depth=node->depth(); |
---|
161 | else |
---|
162 | depth=0; |
---|
163 | int pass=model_->getCurrentPassNumber()-1; |
---|
164 | bool doThis=(model_->getNodeCount()%howOften)==0; |
---|
165 | if (depthCutGenerator_>0) { |
---|
166 | doThis = (depth % depthCutGenerator_) ==0; |
---|
167 | if (depth<depthCutGenerator_) |
---|
168 | doThis=true; // and also at top of tree |
---|
169 | } |
---|
170 | // But turn off if 100 |
---|
171 | if (howOften==100) |
---|
172 | doThis=false; |
---|
173 | // Switch off if special setting |
---|
174 | if (whenCutGeneratorInSub_==-200) { |
---|
175 | fullScan=false; |
---|
176 | doThis=false; |
---|
177 | } |
---|
178 | if (fullScan||doThis) { |
---|
179 | double time1=0.0; |
---|
180 | if (timing_) |
---|
181 | time1 = CoinCpuTime(); |
---|
182 | int cutsBefore = cs.sizeCuts(); |
---|
183 | CglTreeInfo info; |
---|
184 | info.level = depth; |
---|
185 | info.pass = pass; |
---|
186 | info.formulation_rows = model_->numberRowsAtContinuous(); |
---|
187 | info.inTree = node!=NULL; |
---|
188 | incrementNumberTimesEntered(); |
---|
189 | CglProbing* generator = |
---|
190 | dynamic_cast<CglProbing*>(generator_); |
---|
191 | if (!generator) { |
---|
192 | // Pass across model information in case it could be useful |
---|
193 | //OsiSolverInterface * solver = model_->solver(); |
---|
194 | //void * saveData = solver->getApplicationData(); |
---|
195 | //solver->setApplicationData(model_); |
---|
196 | generator_->generateCuts(*solver,cs,info); |
---|
197 | //solver->setApplicationData(saveData); |
---|
198 | } else { |
---|
199 | // Probing - return tight column bounds |
---|
200 | generator->generateCutsAndModify(*solver,cs,info); |
---|
201 | const double * tightLower = generator->tightLower(); |
---|
202 | const double * lower = solver->getColLower(); |
---|
203 | const double * tightUpper = generator->tightUpper(); |
---|
204 | const double * upper = solver->getColUpper(); |
---|
205 | const double * solution = solver->getColSolution(); |
---|
206 | int j; |
---|
207 | int numberColumns = solver->getNumCols(); |
---|
208 | double primalTolerance = 1.0e-8; |
---|
209 | #if 0 |
---|
210 | int numberChanged=0,ifCut=0; |
---|
211 | CoinPackedVector lbs; |
---|
212 | CoinPackedVector ubs; |
---|
213 | for (j=0;j<numberColumns;j++) { |
---|
214 | if (solver->isInteger(j)) { |
---|
215 | if (tightUpper[j]<upper[j]) { |
---|
216 | numberChanged++; |
---|
217 | assert (tightUpper[j]==floor(tightUpper[j]+0.5)); |
---|
218 | ubs.insert(j,tightUpper[j]); |
---|
219 | if (tightUpper[j]<solution[j]-primalTolerance) |
---|
220 | ifCut=1; |
---|
221 | } |
---|
222 | if (tightLower[j]>lower[j]) { |
---|
223 | numberChanged++; |
---|
224 | assert (tightLower[j]==floor(tightLower[j]+0.5)); |
---|
225 | lbs.insert(j,tightLower[j]); |
---|
226 | if (tightLower[j]>solution[j]+primalTolerance) |
---|
227 | ifCut=1; |
---|
228 | } |
---|
229 | } else { |
---|
230 | if (tightUpper[j]==tightLower[j]&& |
---|
231 | upper[j]>lower[j]) { |
---|
232 | // fix |
---|
233 | //solver->setColLower(j,tightLower[j]); |
---|
234 | //solver->setColUpper(j,tightUpper[j]); |
---|
235 | double value = tightUpper[j]; |
---|
236 | numberChanged++; |
---|
237 | if (value<upper[j]) |
---|
238 | ubs.insert(j,value); |
---|
239 | if (value>lower[j]) |
---|
240 | lbs.insert(j,value); |
---|
241 | } |
---|
242 | } |
---|
243 | } |
---|
244 | if (numberChanged) { |
---|
245 | OsiColCut cc; |
---|
246 | cc.setUbs(ubs); |
---|
247 | cc.setLbs(lbs); |
---|
248 | if (ifCut) { |
---|
249 | cc.setEffectiveness(100.0); |
---|
250 | } else { |
---|
251 | cc.setEffectiveness(1.0e-5); |
---|
252 | } |
---|
253 | cs.insert(cc); |
---|
254 | } |
---|
255 | // need to resolve if some bounds changed |
---|
256 | returnCode = !solver->basisIsAvailable(); |
---|
257 | assert (!returnCode); |
---|
258 | #else |
---|
259 | for (j=0;j<numberColumns;j++) { |
---|
260 | if (solver->isInteger(j)) { |
---|
261 | if (tightUpper[j]<upper[j]) { |
---|
262 | double nearest = floor(tightUpper[j]+0.5); |
---|
263 | assert (fabs(tightUpper[j]-nearest)<1.0e-7); |
---|
264 | solver->setColUpper(j,nearest); |
---|
265 | if (nearest<solution[j]-primalTolerance) |
---|
266 | returnCode=true; |
---|
267 | } |
---|
268 | if (tightLower[j]>lower[j]) { |
---|
269 | double nearest = floor(tightLower[j]+0.5); |
---|
270 | assert (fabs(tightLower[j]-nearest)<1.0e-7); |
---|
271 | solver->setColLower(j,nearest); |
---|
272 | if (nearest>solution[j]+primalTolerance) |
---|
273 | returnCode=true; |
---|
274 | } |
---|
275 | } else { |
---|
276 | if (tightUpper[j]==tightLower[j]&& |
---|
277 | upper[j]>lower[j]) { |
---|
278 | // fix |
---|
279 | solver->setColLower(j,tightLower[j]); |
---|
280 | solver->setColUpper(j,tightUpper[j]); |
---|
281 | if (tightLower[j]>solution[j]+primalTolerance|| |
---|
282 | tightUpper[j]<solution[j]-primalTolerance) |
---|
283 | returnCode=true; |
---|
284 | } |
---|
285 | } |
---|
286 | } |
---|
287 | //if (!solver->basisIsAvailable()) |
---|
288 | //returnCode=true; |
---|
289 | #endif |
---|
290 | } |
---|
291 | if (timing_) |
---|
292 | timeInCutGenerator_ += CoinCpuTime()-time1; |
---|
293 | // switch off if first time and no good |
---|
294 | if (node==NULL&&!pass) { |
---|
295 | if (cs.sizeCuts()-cutsBefore<CoinAbs(switchOffIfLessThan_)) { |
---|
296 | whenCutGenerator_=-99; |
---|
297 | whenCutGeneratorInSub_ = -200; |
---|
298 | } |
---|
299 | } |
---|
300 | } |
---|
301 | return returnCode; |
---|
302 | } |
---|
303 | void |
---|
304 | CbcCutGenerator::setHowOften(int howOften) |
---|
305 | { |
---|
306 | |
---|
307 | if (howOften>=1000000) { |
---|
308 | // leave Probing every 10 |
---|
309 | howOften = howOften % 1000000; |
---|
310 | CglProbing* generator = |
---|
311 | dynamic_cast<CglProbing*>(generator_); |
---|
312 | |
---|
313 | if (generator&&howOften>10) |
---|
314 | howOften=10+1000000; |
---|
315 | else |
---|
316 | howOften += 1000000; |
---|
317 | } |
---|
318 | whenCutGenerator_ = howOften; |
---|
319 | } |
---|
320 | void |
---|
321 | CbcCutGenerator::setWhatDepth(int value) |
---|
322 | { |
---|
323 | depthCutGenerator_ = value; |
---|
324 | } |
---|
325 | void |
---|
326 | CbcCutGenerator::setWhatDepthInSub(int value) |
---|
327 | { |
---|
328 | depthCutGeneratorInSub_ = value; |
---|
329 | } |
---|