COIN-OR::LEMON - Graph Library

source: lemon/lemon/cbc.cc @ 1140:8d281761dea4

Last change on this file since 1140:8d281761dea4 was 1140:8d281761dea4, checked in by Alpar Juttner <alpar@…>, 12 years ago

Fix buggy reinitialization in _solver_bits::VarIndex::clear() (#441)

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