COIN-OR::LEMON - Graph Library

source: lemon/lemon/cbc.cc @ 1064:40bbb450143e

Last change on this file since 1064:40bbb450143e was 623:745e182d0139, checked in by Balazs Dezso <deba@…>, 16 years ago

Unified message handling for LP and MIP solvers (#9)

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