COIN-OR::LEMON - Graph Library

source: lemon/lemon/cbc.cc @ 1369:9fd86ec2cb81

Last change on this file since 1369:9fd86ec2cb81 was 1336:0759d974de81, checked in by Gabor Gevay <ggab90@…>, 10 years ago

STL style iterators (#325)

For

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