lemon/cbc.cc
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 29 Sep 2009 09:25:23 +0200
changeset 733 abf31e4af617
parent 567 3314f58e7b25
child 746 e4554cd6b2bf
child 973 ee581a0ecfbf
permissions -rw-r--r--
Copyright notices added to scripts
     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 
    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