|
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library. |
|
4 * |
|
5 * Copyright (C) 2003-2009 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 ///\file |
|
20 ///\brief Implementation of the CBC MIP solver interface. |
|
21 |
|
22 #include "cbc.h" |
|
23 |
|
24 #include <coin/CoinModel.hpp> |
|
25 #include <coin/CbcModel.hpp> |
|
26 #include <coin/OsiSolverInterface.hpp> |
|
27 |
|
28 #ifdef COIN_HAS_CLP |
|
29 #include "coin/OsiClpSolverInterface.hpp" |
|
30 #endif |
|
31 #ifdef COIN_HAS_OSL |
|
32 #include "coin/OsiOslSolverInterface.hpp" |
|
33 #endif |
|
34 |
|
35 #include "coin/CbcCutGenerator.hpp" |
|
36 #include "coin/CbcHeuristicLocal.hpp" |
|
37 #include "coin/CbcHeuristicGreedy.hpp" |
|
38 #include "coin/CbcHeuristicFPump.hpp" |
|
39 #include "coin/CbcHeuristicRINS.hpp" |
|
40 |
|
41 #include "coin/CglGomory.hpp" |
|
42 #include "coin/CglProbing.hpp" |
|
43 #include "coin/CglKnapsackCover.hpp" |
|
44 #include "coin/CglOddHole.hpp" |
|
45 #include "coin/CglClique.hpp" |
|
46 #include "coin/CglFlowCover.hpp" |
|
47 #include "coin/CglMixedIntegerRounding.hpp" |
|
48 |
|
49 #include "coin/CbcHeuristic.hpp" |
|
50 |
|
51 namespace lemon { |
|
52 |
|
53 CbcMip::CbcMip() { |
|
54 _prob = new CoinModel(); |
|
55 _prob->setProblemName("LEMON"); |
|
56 _osi_solver = 0; |
|
57 _cbc_model = 0; |
|
58 } |
|
59 |
|
60 CbcMip::CbcMip(const CbcMip& other) { |
|
61 _prob = new CoinModel(*other._prob); |
|
62 _osi_solver = 0; |
|
63 _cbc_model = 0; |
|
64 } |
|
65 |
|
66 CbcMip::~CbcMip() { |
|
67 delete _prob; |
|
68 if (_osi_solver) delete _osi_solver; |
|
69 if (_cbc_model) delete _cbc_model; |
|
70 } |
|
71 |
|
72 const char* CbcMip::_solverName() const { return "CbcMip"; } |
|
73 |
|
74 int CbcMip::_addCol() { |
|
75 _prob->addColumn(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX, 0.0, 0, false); |
|
76 return _prob->numberColumns() - 1; |
|
77 } |
|
78 |
|
79 CbcMip* CbcMip::newSolver() const { |
|
80 CbcMip* newlp = new CbcMip; |
|
81 return newlp; |
|
82 } |
|
83 |
|
84 CbcMip* CbcMip::cloneSolver() const { |
|
85 CbcMip* copylp = new CbcMip(*this); |
|
86 return copylp; |
|
87 } |
|
88 |
|
89 int CbcMip::_addRow() { |
|
90 _prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX); |
|
91 return _prob->numberRows() - 1; |
|
92 } |
|
93 |
|
94 |
|
95 void CbcMip::_eraseCol(int i) { |
|
96 _prob->deleteColumn(i); |
|
97 } |
|
98 |
|
99 void CbcMip::_eraseRow(int i) { |
|
100 _prob->deleteRow(i); |
|
101 } |
|
102 |
|
103 void CbcMip::_eraseColId(int i) { |
|
104 cols.eraseIndex(i); |
|
105 } |
|
106 |
|
107 void CbcMip::_eraseRowId(int i) { |
|
108 rows.eraseIndex(i); |
|
109 } |
|
110 |
|
111 void CbcMip::_getColName(int c, std::string& name) const { |
|
112 name = _prob->getColumnName(c); |
|
113 } |
|
114 |
|
115 void CbcMip::_setColName(int c, const std::string& name) { |
|
116 _prob->setColumnName(c, name.c_str()); |
|
117 } |
|
118 |
|
119 int CbcMip::_colByName(const std::string& name) const { |
|
120 return _prob->column(name.c_str()); |
|
121 } |
|
122 |
|
123 void CbcMip::_getRowName(int r, std::string& name) const { |
|
124 name = _prob->getRowName(r); |
|
125 } |
|
126 |
|
127 void CbcMip::_setRowName(int r, const std::string& name) { |
|
128 _prob->setRowName(r, name.c_str()); |
|
129 } |
|
130 |
|
131 int CbcMip::_rowByName(const std::string& name) const { |
|
132 return _prob->row(name.c_str()); |
|
133 } |
|
134 |
|
135 void CbcMip::_setRowCoeffs(int i, ExprIterator b, ExprIterator e) { |
|
136 for (ExprIterator it = b; it != e; ++it) { |
|
137 _prob->setElement(i, it->first, it->second); |
|
138 } |
|
139 } |
|
140 |
|
141 void CbcMip::_getRowCoeffs(int ix, InsertIterator b) const { |
|
142 int length = _prob->numberRows(); |
|
143 |
|
144 std::vector<int> indices(length); |
|
145 std::vector<Value> values(length); |
|
146 |
|
147 length = _prob->getRow(ix, &indices[0], &values[0]); |
|
148 |
|
149 for (int i = 0; i < length; ++i) { |
|
150 *b = std::make_pair(indices[i], values[i]); |
|
151 ++b; |
|
152 } |
|
153 } |
|
154 |
|
155 void CbcMip::_setColCoeffs(int ix, ExprIterator b, ExprIterator e) { |
|
156 for (ExprIterator it = b; it != e; ++it) { |
|
157 _prob->setElement(it->first, ix, it->second); |
|
158 } |
|
159 } |
|
160 |
|
161 void CbcMip::_getColCoeffs(int ix, InsertIterator b) const { |
|
162 int length = _prob->numberColumns(); |
|
163 |
|
164 std::vector<int> indices(length); |
|
165 std::vector<Value> values(length); |
|
166 |
|
167 length = _prob->getColumn(ix, &indices[0], &values[0]); |
|
168 |
|
169 for (int i = 0; i < length; ++i) { |
|
170 *b = std::make_pair(indices[i], values[i]); |
|
171 ++b; |
|
172 } |
|
173 } |
|
174 |
|
175 void CbcMip::_setCoeff(int ix, int jx, Value value) { |
|
176 _prob->setElement(ix, jx, value); |
|
177 } |
|
178 |
|
179 CbcMip::Value CbcMip::_getCoeff(int ix, int jx) const { |
|
180 return _prob->getElement(ix, jx); |
|
181 } |
|
182 |
|
183 |
|
184 void CbcMip::_setColLowerBound(int i, Value lo) { |
|
185 LEMON_ASSERT(lo != INF, "Invalid bound"); |
|
186 _prob->setColumnLower(i, lo == - INF ? - COIN_DBL_MAX : lo); |
|
187 } |
|
188 |
|
189 CbcMip::Value CbcMip::_getColLowerBound(int i) const { |
|
190 double val = _prob->getColumnLower(i); |
|
191 return val == - COIN_DBL_MAX ? - INF : val; |
|
192 } |
|
193 |
|
194 void CbcMip::_setColUpperBound(int i, Value up) { |
|
195 LEMON_ASSERT(up != -INF, "Invalid bound"); |
|
196 _prob->setColumnUpper(i, up == INF ? COIN_DBL_MAX : up); |
|
197 } |
|
198 |
|
199 CbcMip::Value CbcMip::_getColUpperBound(int i) const { |
|
200 double val = _prob->getColumnUpper(i); |
|
201 return val == COIN_DBL_MAX ? INF : val; |
|
202 } |
|
203 |
|
204 void CbcMip::_setRowLowerBound(int i, Value lo) { |
|
205 LEMON_ASSERT(lo != INF, "Invalid bound"); |
|
206 _prob->setRowLower(i, lo == - INF ? - COIN_DBL_MAX : lo); |
|
207 } |
|
208 |
|
209 CbcMip::Value CbcMip::_getRowLowerBound(int i) const { |
|
210 double val = _prob->getRowLower(i); |
|
211 return val == - COIN_DBL_MAX ? - INF : val; |
|
212 } |
|
213 |
|
214 void CbcMip::_setRowUpperBound(int i, Value up) { |
|
215 LEMON_ASSERT(up != -INF, "Invalid bound"); |
|
216 _prob->setRowUpper(i, up == INF ? COIN_DBL_MAX : up); |
|
217 } |
|
218 |
|
219 CbcMip::Value CbcMip::_getRowUpperBound(int i) const { |
|
220 double val = _prob->getRowUpper(i); |
|
221 return val == COIN_DBL_MAX ? INF : val; |
|
222 } |
|
223 |
|
224 void CbcMip::_setObjCoeffs(ExprIterator b, ExprIterator e) { |
|
225 int num = _prob->numberColumns(); |
|
226 for (int i = 0; i < num; ++i) { |
|
227 _prob->setColumnObjective(i, 0.0); |
|
228 } |
|
229 for (ExprIterator it = b; it != e; ++it) { |
|
230 _prob->setColumnObjective(it->first, it->second); |
|
231 } |
|
232 } |
|
233 |
|
234 void CbcMip::_getObjCoeffs(InsertIterator b) const { |
|
235 int num = _prob->numberColumns(); |
|
236 for (int i = 0; i < num; ++i) { |
|
237 Value coef = _prob->getColumnObjective(i); |
|
238 if (coef != 0.0) { |
|
239 *b = std::make_pair(i, coef); |
|
240 ++b; |
|
241 } |
|
242 } |
|
243 } |
|
244 |
|
245 void CbcMip::_setObjCoeff(int i, Value obj_coef) { |
|
246 _prob->setColumnObjective(i, obj_coef); |
|
247 } |
|
248 |
|
249 CbcMip::Value CbcMip::_getObjCoeff(int i) const { |
|
250 return _prob->getColumnObjective(i); |
|
251 } |
|
252 |
|
253 CbcMip::SolveExitStatus CbcMip::_solve() { |
|
254 |
|
255 if (_osi_solver) { |
|
256 delete _osi_solver; |
|
257 } |
|
258 #ifdef COIN_HAS_CLP |
|
259 _osi_solver = new OsiClpSolverInterface(); |
|
260 #elif COIN_HAS_OSL |
|
261 _osi_solver = new OsiOslSolverInterface(); |
|
262 #else |
|
263 #error Cannot instantiate Osi solver |
|
264 #endif |
|
265 |
|
266 _osi_solver->loadFromCoinModel(*_prob); |
|
267 |
|
268 if (_cbc_model) { |
|
269 delete _cbc_model; |
|
270 } |
|
271 _cbc_model= new CbcModel(*_osi_solver); |
|
272 |
|
273 switch (_message_level) { |
|
274 case MESSAGE_NO_OUTPUT: |
|
275 _osi_solver->messageHandler()->setLogLevel(0); |
|
276 _cbc_model->setLogLevel(0); |
|
277 break; |
|
278 case MESSAGE_ERROR_MESSAGE: |
|
279 _osi_solver->messageHandler()->setLogLevel(1); |
|
280 _cbc_model->setLogLevel(1); |
|
281 break; |
|
282 case MESSAGE_NORMAL_OUTPUT: |
|
283 _osi_solver->messageHandler()->setLogLevel(2); |
|
284 _cbc_model->setLogLevel(2); |
|
285 break; |
|
286 case MESSAGE_FULL_OUTPUT: |
|
287 _osi_solver->messageHandler()->setLogLevel(3); |
|
288 _cbc_model->setLogLevel(3); |
|
289 break; |
|
290 } |
|
291 |
|
292 _cbc_model->initialSolve(); |
|
293 _cbc_model->solver()->setHintParam(OsiDoReducePrint, true, OsiHintTry); |
|
294 |
|
295 if (!_cbc_model->isInitialSolveAbandoned() && |
|
296 _cbc_model->isInitialSolveProvenOptimal() && |
|
297 !_cbc_model->isInitialSolveProvenPrimalInfeasible() && |
|
298 !_cbc_model->isInitialSolveProvenDualInfeasible()) { |
|
299 |
|
300 CglProbing generator1; |
|
301 generator1.setUsingObjective(true); |
|
302 generator1.setMaxPass(3); |
|
303 generator1.setMaxProbe(100); |
|
304 generator1.setMaxLook(50); |
|
305 generator1.setRowCuts(3); |
|
306 _cbc_model->addCutGenerator(&generator1, -1, "Probing"); |
|
307 |
|
308 CglGomory generator2; |
|
309 generator2.setLimit(300); |
|
310 _cbc_model->addCutGenerator(&generator2, -1, "Gomory"); |
|
311 |
|
312 CglKnapsackCover generator3; |
|
313 _cbc_model->addCutGenerator(&generator3, -1, "Knapsack"); |
|
314 |
|
315 CglOddHole generator4; |
|
316 generator4.setMinimumViolation(0.005); |
|
317 generator4.setMinimumViolationPer(0.00002); |
|
318 generator4.setMaximumEntries(200); |
|
319 _cbc_model->addCutGenerator(&generator4, -1, "OddHole"); |
|
320 |
|
321 CglClique generator5; |
|
322 generator5.setStarCliqueReport(false); |
|
323 generator5.setRowCliqueReport(false); |
|
324 _cbc_model->addCutGenerator(&generator5, -1, "Clique"); |
|
325 |
|
326 CglMixedIntegerRounding mixedGen; |
|
327 _cbc_model->addCutGenerator(&mixedGen, -1, "MixedIntegerRounding"); |
|
328 |
|
329 CglFlowCover flowGen; |
|
330 _cbc_model->addCutGenerator(&flowGen, -1, "FlowCover"); |
|
331 |
|
332 #ifdef COIN_HAS_CLP |
|
333 OsiClpSolverInterface* osiclp = |
|
334 dynamic_cast<OsiClpSolverInterface*>(_cbc_model->solver()); |
|
335 if (osiclp->getNumRows() < 300 && osiclp->getNumCols() < 500) { |
|
336 osiclp->setupForRepeatedUse(2, 0); |
|
337 } |
|
338 #endif |
|
339 |
|
340 CbcRounding heuristic1(*_cbc_model); |
|
341 heuristic1.setWhen(3); |
|
342 _cbc_model->addHeuristic(&heuristic1); |
|
343 |
|
344 CbcHeuristicLocal heuristic2(*_cbc_model); |
|
345 heuristic2.setWhen(3); |
|
346 _cbc_model->addHeuristic(&heuristic2); |
|
347 |
|
348 CbcHeuristicGreedyCover heuristic3(*_cbc_model); |
|
349 heuristic3.setAlgorithm(11); |
|
350 heuristic3.setWhen(3); |
|
351 _cbc_model->addHeuristic(&heuristic3); |
|
352 |
|
353 CbcHeuristicFPump heuristic4(*_cbc_model); |
|
354 heuristic4.setWhen(3); |
|
355 _cbc_model->addHeuristic(&heuristic4); |
|
356 |
|
357 CbcHeuristicRINS heuristic5(*_cbc_model); |
|
358 heuristic5.setWhen(3); |
|
359 _cbc_model->addHeuristic(&heuristic5); |
|
360 |
|
361 if (_cbc_model->getNumCols() < 500) { |
|
362 _cbc_model->setMaximumCutPassesAtRoot(-100); |
|
363 } else if (_cbc_model->getNumCols() < 5000) { |
|
364 _cbc_model->setMaximumCutPassesAtRoot(100); |
|
365 } else { |
|
366 _cbc_model->setMaximumCutPassesAtRoot(20); |
|
367 } |
|
368 |
|
369 if (_cbc_model->getNumCols() < 5000) { |
|
370 _cbc_model->setNumberStrong(10); |
|
371 } |
|
372 |
|
373 _cbc_model->solver()->setIntParam(OsiMaxNumIterationHotStart, 100); |
|
374 _cbc_model->branchAndBound(); |
|
375 } |
|
376 |
|
377 if (_cbc_model->isAbandoned()) { |
|
378 return UNSOLVED; |
|
379 } else { |
|
380 return SOLVED; |
|
381 } |
|
382 } |
|
383 |
|
384 CbcMip::Value CbcMip::_getSol(int i) const { |
|
385 return _cbc_model->getColSolution()[i]; |
|
386 } |
|
387 |
|
388 CbcMip::Value CbcMip::_getSolValue() const { |
|
389 return _cbc_model->getObjValue(); |
|
390 } |
|
391 |
|
392 CbcMip::ProblemType CbcMip::_getType() const { |
|
393 if (_cbc_model->isProvenOptimal()) { |
|
394 return OPTIMAL; |
|
395 } else if (_cbc_model->isContinuousUnbounded()) { |
|
396 return UNBOUNDED; |
|
397 } |
|
398 return FEASIBLE; |
|
399 } |
|
400 |
|
401 void CbcMip::_setSense(Sense sense) { |
|
402 switch (sense) { |
|
403 case MIN: |
|
404 _prob->setOptimizationDirection(1.0); |
|
405 break; |
|
406 case MAX: |
|
407 _prob->setOptimizationDirection(- 1.0); |
|
408 break; |
|
409 } |
|
410 } |
|
411 |
|
412 CbcMip::Sense CbcMip::_getSense() const { |
|
413 if (_prob->optimizationDirection() > 0.0) { |
|
414 return MIN; |
|
415 } else if (_prob->optimizationDirection() < 0.0) { |
|
416 return MAX; |
|
417 } else { |
|
418 LEMON_ASSERT(false, "Wrong sense"); |
|
419 return CbcMip::Sense(); |
|
420 } |
|
421 } |
|
422 |
|
423 void CbcMip::_setColType(int i, CbcMip::ColTypes col_type) { |
|
424 switch (col_type){ |
|
425 case INTEGER: |
|
426 _prob->setInteger(i); |
|
427 break; |
|
428 case REAL: |
|
429 _prob->setContinuous(i); |
|
430 break; |
|
431 default:; |
|
432 LEMON_ASSERT(false, "Wrong sense"); |
|
433 } |
|
434 } |
|
435 |
|
436 CbcMip::ColTypes CbcMip::_getColType(int i) const { |
|
437 return _prob->getColumnIsInteger(i) ? INTEGER : REAL; |
|
438 } |
|
439 |
|
440 void CbcMip::_clear() { |
|
441 delete _prob; |
|
442 if (_osi_solver) { |
|
443 delete _osi_solver; |
|
444 _osi_solver = 0; |
|
445 } |
|
446 if (_cbc_model) { |
|
447 delete _cbc_model; |
|
448 _cbc_model = 0; |
|
449 } |
|
450 |
|
451 _prob = new CoinModel(); |
|
452 rows.clear(); |
|
453 cols.clear(); |
|
454 } |
|
455 |
|
456 void CbcMip::messageLevel(MessageLevel m) { |
|
457 _message_level = m; |
|
458 } |
|
459 |
|
460 } //END OF NAMESPACE LEMON |