lemon/cbc.cc
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 09 Aug 2013 11:07:27 +0200
changeset 987 70b199792735
parent 951 ee581a0ecfbf
child 956 4764031c082c
child 964 7fdaa05a69a1
permissions -rw-r--r--
Clarification in biNodeConnected() doc (#439)
     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 
    46 namespace 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