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