# HG changeset patch
# User Balazs Dezso <deba@inf.elte.hu>
# Date 2009-04-01 22:58:58
# Node ID 3314f58e7b255e03ab9a6a65c66dffbffab77ff7
# Parent  e7017ec2d5cd298d9a7e835243c3bc3b4a280683

Add CBC support (#204)

diff --git a/Makefile.am b/Makefile.am
--- a/Makefile.am
+++ b/Makefile.am
@@ -11,6 +11,8 @@
 	m4/lx_check_cplex.m4 \
 	m4/lx_check_glpk.m4 \
 	m4/lx_check_soplex.m4 \
+	m4/lx_check_clp.m4 \
+	m4/lx_check_cbc.m4 \
 	CMakeLists.txt \
 	cmake/FindGhostscript.cmake \
 	cmake/FindGLPK.cmake \
diff --git a/configure.ac b/configure.ac
--- a/configure.ac
+++ b/configure.ac
@@ -60,6 +60,7 @@
 LX_CHECK_CPLEX
 LX_CHECK_SOPLEX
 LX_CHECK_CLP
+LX_CHECK_CBC
 
 AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
 AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"])
@@ -119,6 +120,7 @@
 echo CPLEX support................. : $lx_cplex_found
 echo SOPLEX support................ : $lx_soplex_found
 echo CLP support................... : $lx_clp_found
+echo CBC support................... : $lx_cbc_found
 echo
 echo Build additional tools........ : $enable_tools
 echo
diff --git a/lemon/Makefile.am b/lemon/Makefile.am
--- a/lemon/Makefile.am
+++ b/lemon/Makefile.am
@@ -12,7 +12,7 @@
 	lemon/color.cc \
 	lemon/lp_base.cc \
 	lemon/lp_skeleton.cc \
-        lemon/random.cc \
+	lemon/random.cc \
 	lemon/bits/windows.cc
 
 
@@ -21,13 +21,15 @@
 	$(GLPK_CFLAGS) \
 	$(CPLEX_CFLAGS) \
 	$(SOPLEX_CXXFLAGS) \
-	$(CLP_CXXFLAGS)
+	$(CLP_CXXFLAGS) \
+	$(CBC_CXXFLAGS)
 
 lemon_libemon_la_LDFLAGS = \
 	$(GLPK_LIBS) \
 	$(CPLEX_LIBS) \
 	$(SOPLEX_LIBS) \
-	$(CLP_LIBS)
+	$(CLP_LIBS) \
+	$(CBC_LIBS)
 
 if HAVE_GLPK
 lemon_libemon_la_SOURCES += lemon/glpk.cc
@@ -45,6 +47,10 @@
 lemon_libemon_la_SOURCES += lemon/clp.cc
 endif
 
+if HAVE_CBC
+lemon_libemon_la_SOURCES += lemon/cbc.cc
+endif
+
 lemon_HEADERS += \
 	lemon/adaptors.h \
 	lemon/arg_parser.h \
diff --git a/lemon/cbc.cc b/lemon/cbc.cc
new file mode 100644
--- /dev/null
+++ b/lemon/cbc.cc
@@ -0,0 +1,460 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2009
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+///\file
+///\brief Implementation of the CBC MIP solver interface.
+
+#include "cbc.h"
+
+#include <coin/CoinModel.hpp>
+#include <coin/CbcModel.hpp>
+#include <coin/OsiSolverInterface.hpp>
+
+#ifdef COIN_HAS_CLP
+#include "coin/OsiClpSolverInterface.hpp"
+#endif
+#ifdef COIN_HAS_OSL
+#include "coin/OsiOslSolverInterface.hpp"
+#endif
+
+#include "coin/CbcCutGenerator.hpp"
+#include "coin/CbcHeuristicLocal.hpp"
+#include "coin/CbcHeuristicGreedy.hpp"
+#include "coin/CbcHeuristicFPump.hpp"
+#include "coin/CbcHeuristicRINS.hpp"
+
+#include "coin/CglGomory.hpp"
+#include "coin/CglProbing.hpp"
+#include "coin/CglKnapsackCover.hpp"
+#include "coin/CglOddHole.hpp"
+#include "coin/CglClique.hpp"
+#include "coin/CglFlowCover.hpp"
+#include "coin/CglMixedIntegerRounding.hpp"
+
+#include "coin/CbcHeuristic.hpp"
+
+namespace lemon {
+
+  CbcMip::CbcMip() {
+    _prob = new CoinModel();
+    _prob->setProblemName("LEMON");
+    _osi_solver = 0;
+    _cbc_model = 0;
+  }
+
+  CbcMip::CbcMip(const CbcMip& other) {
+    _prob = new CoinModel(*other._prob);
+    _osi_solver = 0;
+    _cbc_model = 0;
+  }
+
+  CbcMip::~CbcMip() {
+    delete _prob;
+    if (_osi_solver) delete _osi_solver;
+    if (_cbc_model) delete _cbc_model;
+  }
+
+  const char* CbcMip::_solverName() const { return "CbcMip"; }
+
+  int CbcMip::_addCol() {
+    _prob->addColumn(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX, 0.0, 0, false);
+    return _prob->numberColumns() - 1;
+  }
+
+  CbcMip* CbcMip::newSolver() const {
+    CbcMip* newlp = new CbcMip;
+    return newlp;
+  }
+
+  CbcMip* CbcMip::cloneSolver() const {
+    CbcMip* copylp = new CbcMip(*this);
+    return copylp;
+  }
+
+  int CbcMip::_addRow() {
+    _prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX);
+    return _prob->numberRows() - 1;
+  }
+
+
+  void CbcMip::_eraseCol(int i) {
+    _prob->deleteColumn(i);
+  }
+
+  void CbcMip::_eraseRow(int i) {
+    _prob->deleteRow(i);
+  }
+
+  void CbcMip::_eraseColId(int i) {
+    cols.eraseIndex(i);
+  }
+
+  void CbcMip::_eraseRowId(int i) {
+    rows.eraseIndex(i);
+  }
+
+  void CbcMip::_getColName(int c, std::string& name) const {
+    name = _prob->getColumnName(c);
+  }
+
+  void CbcMip::_setColName(int c, const std::string& name) {
+    _prob->setColumnName(c, name.c_str());
+  }
+
+  int CbcMip::_colByName(const std::string& name) const {
+    return _prob->column(name.c_str());
+  }
+
+  void CbcMip::_getRowName(int r, std::string& name) const {
+    name = _prob->getRowName(r);
+  }
+
+  void CbcMip::_setRowName(int r, const std::string& name) {
+    _prob->setRowName(r, name.c_str());
+  }
+
+  int CbcMip::_rowByName(const std::string& name) const {
+    return _prob->row(name.c_str());
+  }
+
+  void CbcMip::_setRowCoeffs(int i, ExprIterator b, ExprIterator e) {
+    for (ExprIterator it = b; it != e; ++it) {
+      _prob->setElement(i, it->first, it->second);
+    }
+  }
+
+  void CbcMip::_getRowCoeffs(int ix, InsertIterator b) const {
+    int length = _prob->numberRows();
+
+    std::vector<int> indices(length);
+    std::vector<Value> values(length);
+
+    length = _prob->getRow(ix, &indices[0], &values[0]);
+
+    for (int i = 0; i < length; ++i) {
+      *b = std::make_pair(indices[i], values[i]);
+      ++b;
+    }
+  }
+
+  void CbcMip::_setColCoeffs(int ix, ExprIterator b, ExprIterator e) {
+    for (ExprIterator it = b; it != e; ++it) {
+      _prob->setElement(it->first, ix, it->second);
+    }
+  }
+
+  void CbcMip::_getColCoeffs(int ix, InsertIterator b) const {
+    int length = _prob->numberColumns();
+
+    std::vector<int> indices(length);
+    std::vector<Value> values(length);
+
+    length = _prob->getColumn(ix, &indices[0], &values[0]);
+
+    for (int i = 0; i < length; ++i) {
+      *b = std::make_pair(indices[i], values[i]);
+      ++b;
+    }
+  }
+
+  void CbcMip::_setCoeff(int ix, int jx, Value value) {
+    _prob->setElement(ix, jx, value);
+  }
+
+  CbcMip::Value CbcMip::_getCoeff(int ix, int jx) const {
+    return _prob->getElement(ix, jx);
+  }
+
+
+  void CbcMip::_setColLowerBound(int i, Value lo) {
+    LEMON_ASSERT(lo != INF, "Invalid bound");
+    _prob->setColumnLower(i, lo == - INF ? - COIN_DBL_MAX : lo);
+  }
+
+  CbcMip::Value CbcMip::_getColLowerBound(int i) const {
+    double val = _prob->getColumnLower(i);
+    return val == - COIN_DBL_MAX ? - INF : val;
+  }
+
+  void CbcMip::_setColUpperBound(int i, Value up) {
+    LEMON_ASSERT(up != -INF, "Invalid bound");
+    _prob->setColumnUpper(i, up == INF ? COIN_DBL_MAX : up);
+  }
+
+  CbcMip::Value CbcMip::_getColUpperBound(int i) const {
+    double val = _prob->getColumnUpper(i);
+    return val == COIN_DBL_MAX ? INF : val;
+  }
+
+  void CbcMip::_setRowLowerBound(int i, Value lo) {
+    LEMON_ASSERT(lo != INF, "Invalid bound");
+    _prob->setRowLower(i, lo == - INF ? - COIN_DBL_MAX : lo);
+  }
+
+  CbcMip::Value CbcMip::_getRowLowerBound(int i) const {
+    double val = _prob->getRowLower(i);
+    return val == - COIN_DBL_MAX ? - INF : val;
+  }
+
+  void CbcMip::_setRowUpperBound(int i, Value up) {
+    LEMON_ASSERT(up != -INF, "Invalid bound");
+    _prob->setRowUpper(i, up == INF ? COIN_DBL_MAX : up);
+  }
+
+  CbcMip::Value CbcMip::_getRowUpperBound(int i) const {
+    double val = _prob->getRowUpper(i);
+    return val == COIN_DBL_MAX ? INF : val;
+  }
+
+  void CbcMip::_setObjCoeffs(ExprIterator b, ExprIterator e) {
+    int num = _prob->numberColumns();
+    for (int i = 0; i < num; ++i) {
+      _prob->setColumnObjective(i, 0.0);
+    }
+    for (ExprIterator it = b; it != e; ++it) {
+      _prob->setColumnObjective(it->first, it->second);
+    }
+  }
+
+  void CbcMip::_getObjCoeffs(InsertIterator b) const {
+    int num = _prob->numberColumns();
+    for (int i = 0; i < num; ++i) {
+      Value coef = _prob->getColumnObjective(i);
+      if (coef != 0.0) {
+        *b = std::make_pair(i, coef);
+        ++b;
+      }
+    }
+  }
+
+  void CbcMip::_setObjCoeff(int i, Value obj_coef) {
+    _prob->setColumnObjective(i, obj_coef);
+  }
+
+  CbcMip::Value CbcMip::_getObjCoeff(int i) const {
+    return _prob->getColumnObjective(i);
+  }
+
+  CbcMip::SolveExitStatus CbcMip::_solve() {
+
+    if (_osi_solver) {
+      delete _osi_solver;
+    }
+#ifdef COIN_HAS_CLP
+    _osi_solver = new OsiClpSolverInterface();
+#elif COIN_HAS_OSL
+    _osi_solver = new OsiOslSolverInterface();
+#else
+#error Cannot instantiate Osi solver
+#endif
+
+    _osi_solver->loadFromCoinModel(*_prob);
+
+    if (_cbc_model) {
+      delete _cbc_model;
+    }
+    _cbc_model= new CbcModel(*_osi_solver);
+
+    switch (_message_level) {
+    case MESSAGE_NO_OUTPUT:
+      _osi_solver->messageHandler()->setLogLevel(0);
+      _cbc_model->setLogLevel(0);
+      break;
+    case MESSAGE_ERROR_MESSAGE:
+      _osi_solver->messageHandler()->setLogLevel(1);
+      _cbc_model->setLogLevel(1);
+      break;
+    case MESSAGE_NORMAL_OUTPUT:
+      _osi_solver->messageHandler()->setLogLevel(2);
+      _cbc_model->setLogLevel(2);
+      break;
+    case MESSAGE_FULL_OUTPUT:
+      _osi_solver->messageHandler()->setLogLevel(3);
+      _cbc_model->setLogLevel(3);
+      break;
+    }
+
+    _cbc_model->initialSolve();
+    _cbc_model->solver()->setHintParam(OsiDoReducePrint, true, OsiHintTry);
+
+    if (!_cbc_model->isInitialSolveAbandoned() &&
+        _cbc_model->isInitialSolveProvenOptimal() &&
+        !_cbc_model->isInitialSolveProvenPrimalInfeasible() &&
+        !_cbc_model->isInitialSolveProvenDualInfeasible()) {
+
+      CglProbing generator1;
+      generator1.setUsingObjective(true);
+      generator1.setMaxPass(3);
+      generator1.setMaxProbe(100);
+      generator1.setMaxLook(50);
+      generator1.setRowCuts(3);
+      _cbc_model->addCutGenerator(&generator1, -1, "Probing");
+
+      CglGomory generator2;
+      generator2.setLimit(300);
+      _cbc_model->addCutGenerator(&generator2, -1, "Gomory");
+
+      CglKnapsackCover generator3;
+      _cbc_model->addCutGenerator(&generator3, -1, "Knapsack");
+
+      CglOddHole generator4;
+      generator4.setMinimumViolation(0.005);
+      generator4.setMinimumViolationPer(0.00002);
+      generator4.setMaximumEntries(200);
+      _cbc_model->addCutGenerator(&generator4, -1, "OddHole");
+
+      CglClique generator5;
+      generator5.setStarCliqueReport(false);
+      generator5.setRowCliqueReport(false);
+      _cbc_model->addCutGenerator(&generator5, -1, "Clique");
+
+      CglMixedIntegerRounding mixedGen;
+      _cbc_model->addCutGenerator(&mixedGen, -1, "MixedIntegerRounding");
+
+      CglFlowCover flowGen;
+      _cbc_model->addCutGenerator(&flowGen, -1, "FlowCover");
+
+#ifdef COIN_HAS_CLP
+      OsiClpSolverInterface* osiclp =
+        dynamic_cast<OsiClpSolverInterface*>(_cbc_model->solver());
+      if (osiclp->getNumRows() < 300 && osiclp->getNumCols() < 500) {
+        osiclp->setupForRepeatedUse(2, 0);
+      }
+#endif
+
+      CbcRounding heuristic1(*_cbc_model);
+      heuristic1.setWhen(3);
+      _cbc_model->addHeuristic(&heuristic1);
+
+      CbcHeuristicLocal heuristic2(*_cbc_model);
+      heuristic2.setWhen(3);
+      _cbc_model->addHeuristic(&heuristic2);
+
+      CbcHeuristicGreedyCover heuristic3(*_cbc_model);
+      heuristic3.setAlgorithm(11);
+      heuristic3.setWhen(3);
+      _cbc_model->addHeuristic(&heuristic3);
+
+      CbcHeuristicFPump heuristic4(*_cbc_model);
+      heuristic4.setWhen(3);
+      _cbc_model->addHeuristic(&heuristic4);
+
+      CbcHeuristicRINS heuristic5(*_cbc_model);
+      heuristic5.setWhen(3);
+      _cbc_model->addHeuristic(&heuristic5);
+
+      if (_cbc_model->getNumCols() < 500) {
+        _cbc_model->setMaximumCutPassesAtRoot(-100);
+      } else if (_cbc_model->getNumCols() < 5000) {
+        _cbc_model->setMaximumCutPassesAtRoot(100);
+      } else {
+        _cbc_model->setMaximumCutPassesAtRoot(20);
+      }
+
+      if (_cbc_model->getNumCols() < 5000) {
+        _cbc_model->setNumberStrong(10);
+      }
+
+      _cbc_model->solver()->setIntParam(OsiMaxNumIterationHotStart, 100);
+      _cbc_model->branchAndBound();
+    }
+
+    if (_cbc_model->isAbandoned()) {
+      return UNSOLVED;
+    } else {
+      return SOLVED;
+    }
+  }
+
+  CbcMip::Value CbcMip::_getSol(int i) const {
+    return _cbc_model->getColSolution()[i];
+  }
+
+  CbcMip::Value CbcMip::_getSolValue() const {
+    return _cbc_model->getObjValue();
+  }
+
+  CbcMip::ProblemType CbcMip::_getType() const {
+    if (_cbc_model->isProvenOptimal()) {
+      return OPTIMAL;
+    } else if (_cbc_model->isContinuousUnbounded()) {
+      return UNBOUNDED;
+    }
+    return FEASIBLE;
+  }
+
+  void CbcMip::_setSense(Sense sense) {
+    switch (sense) {
+    case MIN:
+      _prob->setOptimizationDirection(1.0);
+      break;
+    case MAX:
+      _prob->setOptimizationDirection(- 1.0);
+      break;
+    }
+  }
+
+  CbcMip::Sense CbcMip::_getSense() const {
+    if (_prob->optimizationDirection() > 0.0) {
+      return MIN;
+    } else if (_prob->optimizationDirection() < 0.0) {
+      return MAX;
+    } else {
+      LEMON_ASSERT(false, "Wrong sense");
+      return CbcMip::Sense();
+    }
+  }
+
+  void CbcMip::_setColType(int i, CbcMip::ColTypes col_type) {
+    switch (col_type){
+    case INTEGER:
+      _prob->setInteger(i);
+      break;
+    case REAL:
+      _prob->setContinuous(i);
+      break;
+    default:;
+      LEMON_ASSERT(false, "Wrong sense");
+    }
+  }
+
+  CbcMip::ColTypes CbcMip::_getColType(int i) const {
+    return _prob->getColumnIsInteger(i) ? INTEGER : REAL;
+  }
+
+  void CbcMip::_clear() {
+    delete _prob;
+    if (_osi_solver) {
+      delete _osi_solver;
+      _osi_solver = 0;
+    }
+    if (_cbc_model) {
+      delete _cbc_model;
+      _cbc_model = 0;
+    }
+
+    _prob = new CoinModel();
+    rows.clear();
+    cols.clear();
+  }
+
+  void CbcMip::messageLevel(MessageLevel m) {
+    _message_level = m;
+  }
+
+} //END OF NAMESPACE LEMON
diff --git a/lemon/cbc.h b/lemon/cbc.h
new file mode 100644
--- /dev/null
+++ b/lemon/cbc.h
@@ -0,0 +1,150 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2009
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+// -*- C++ -*-
+#ifndef LEMON_CBC_H
+#define LEMON_CBC_H
+
+///\file
+///\brief Header of the LEMON-CBC mip solver interface.
+///\ingroup lp_group
+
+#include <lemon/lp_base.h>
+
+class CoinModel;
+class OsiSolverInterface;
+class CbcModel;
+
+namespace lemon {
+
+  /// \brief Interface for the CBC MIP solver
+  ///
+  /// This class implements an interface for the CBC MIP solver.
+  ///\ingroup lp_group
+  class CbcMip : public MipSolver {
+  protected:
+
+    CoinModel *_prob;
+    OsiSolverInterface *_osi_solver;
+    CbcModel *_cbc_model;
+
+  public:
+
+    /// \e
+    CbcMip();
+    /// \e
+    CbcMip(const CbcMip&);
+    /// \e
+    ~CbcMip();
+    /// \e
+    virtual CbcMip* newSolver() const;
+    /// \e
+    virtual CbcMip* cloneSolver() const;
+
+  protected:
+
+    virtual const char* _solverName() const;
+
+    virtual int _addCol();
+    virtual int _addRow();
+
+    virtual void _eraseCol(int i);
+    virtual void _eraseRow(int i);
+
+    virtual void _eraseColId(int i);
+    virtual void _eraseRowId(int i);
+
+    virtual void _getColName(int col, std::string& name) const;
+    virtual void _setColName(int col, const std::string& name);
+    virtual int _colByName(const std::string& name) const;
+
+    virtual void _getRowName(int row, std::string& name) const;
+    virtual void _setRowName(int row, const std::string& name);
+    virtual int _rowByName(const std::string& name) const;
+
+    virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e);
+    virtual void _getRowCoeffs(int i, InsertIterator b) const;
+
+    virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e);
+    virtual void _getColCoeffs(int i, InsertIterator b) const;
+
+    virtual void _setCoeff(int row, int col, Value value);
+    virtual Value _getCoeff(int row, int col) const;
+
+    virtual void _setColLowerBound(int i, Value value);
+    virtual Value _getColLowerBound(int i) const;
+    virtual void _setColUpperBound(int i, Value value);
+    virtual Value _getColUpperBound(int i) const;
+
+    virtual void _setRowLowerBound(int i, Value value);
+    virtual Value _getRowLowerBound(int i) const;
+    virtual void _setRowUpperBound(int i, Value value);
+    virtual Value _getRowUpperBound(int i) const;
+
+    virtual void _setObjCoeffs(ExprIterator b, ExprIterator e);
+    virtual void _getObjCoeffs(InsertIterator b) const;
+
+    virtual void _setObjCoeff(int i, Value obj_coef);
+    virtual Value _getObjCoeff(int i) const;
+
+    virtual void _setSense(Sense sense);
+    virtual Sense _getSense() const;
+
+    virtual ColTypes _getColType(int col) const;
+    virtual void _setColType(int col, ColTypes col_type);
+
+    virtual SolveExitStatus _solve();
+    virtual ProblemType _getType() const;
+    virtual Value _getSol(int i) const;
+    virtual Value _getSolValue() const;
+
+    virtual void _clear();
+
+  public:
+
+    ///Enum for \c messageLevel() parameter
+    enum MessageLevel {
+      /// no output (default value)
+      MESSAGE_NO_OUTPUT = 0,
+      /// error messages only
+      MESSAGE_ERROR_MESSAGE = 1,
+      /// normal output
+      MESSAGE_NORMAL_OUTPUT = 2,
+      /// full output (includes informational messages)
+      MESSAGE_FULL_OUTPUT = 3
+    };
+
+  private:
+
+    MessageLevel _message_level;
+
+  public:
+
+    ///Set the verbosity of the messages
+
+    ///Set the verbosity of the messages
+    ///
+    ///\param m is the level of the messages output by the solver routines.
+    void messageLevel(MessageLevel m);
+
+
+  };
+
+}
+
+#endif
diff --git a/lemon/config.h.in b/lemon/config.h.in
--- a/lemon/config.h.in
+++ b/lemon/config.h.in
@@ -18,3 +18,6 @@
 
 /* Define to 1 if you have CLP */
 #undef HAVE_CLP
+
+/* Define to 1 if you have CBC */
+#undef HAVE_CBC
diff --git a/m4/lx_check_cbc.m4 b/m4/lx_check_cbc.m4
new file mode 100644
--- /dev/null
+++ b/m4/lx_check_cbc.m4
@@ -0,0 +1,73 @@
+AC_DEFUN([LX_CHECK_CBC],
+[
+  AC_ARG_WITH([cbc],
+AS_HELP_STRING([--with-cbc@<:@=PREFIX@:>@], [search for CBC under PREFIX or under the default search paths if PREFIX is not given @<:@default@:>@])
+AS_HELP_STRING([--without-cbc], [disable checking for CBC]),
+              [], [with_cbc=yes])
+
+  AC_ARG_WITH([cbc-includedir],
+AS_HELP_STRING([--with-cbc-includedir=DIR], [search for CBC headers in DIR]),
+              [], [with_cbc_includedir=no])
+
+  AC_ARG_WITH([cbc-libdir],
+AS_HELP_STRING([--with-cbc-libdir=DIR], [search for CBC libraries in DIR]),
+              [], [with_cbc_libdir=no])
+
+  lx_cbc_found=no
+  if test x"$with_cbc" != x"no"; then
+    AC_MSG_CHECKING([for CBC])
+
+    if test x"$with_cbc_includedir" != x"no"; then
+      CBC_CXXFLAGS="-I$with_cbc_includedir"
+    elif test x"$with_cbc" != x"yes"; then
+      CBC_CXXFLAGS="-I$with_cbc/include"
+    fi
+
+    if test x"$with_cbc_libdir" != x"no"; then
+      CBC_LDFLAGS="-L$with_cbc_libdir"
+    elif test x"$with_cbc" != x"yes"; then
+      CBC_LDFLAGS="-L$with_cbc/lib"
+    fi
+    CBC_LIBS="-lOsi -lCbc -lOsiCbc -lCbcSolver -lClp -lOsiClp -lCoinUtils -lVol -lOsiVol -lCgl -lm -llapack -lblas"
+
+    lx_save_cxxflags="$CXXFLAGS"
+    lx_save_ldflags="$LDFLAGS"
+    lx_save_libs="$LIBS"
+    CXXFLAGS="$CBC_CXXFLAGS"
+    LDFLAGS="$CBC_LDFLAGS"
+    LIBS="$CBC_LIBS"
+
+    lx_cbc_test_prog='
+      #include <coin/CbcModel.hpp>
+
+      int main(int argc, char** argv)
+      {
+        CbcModel cbc;
+        return 0;
+      }'
+
+    AC_LANG_PUSH(C++)
+    AC_LINK_IFELSE([$lx_cbc_test_prog], [lx_cbc_found=yes], [lx_cbc_found=no])
+    AC_LANG_POP(C++)
+
+    CXXFLAGS="$lx_save_cxxflags"
+    LDFLAGS="$lx_save_ldflags"
+    LIBS="$lx_save_libs"
+
+    if test x"$lx_cbc_found" = x"yes"; then
+      AC_DEFINE([HAVE_CBC], [1], [Define to 1 if you have CBC.])
+      lx_lp_found=yes
+      AC_DEFINE([HAVE_LP], [1], [Define to 1 if you have any LP solver.])
+      AC_MSG_RESULT([yes])
+    else
+      CBC_CXXFLAGS=""
+      CBC_LDFLAGS=""
+      CBC_LIBS=""
+      AC_MSG_RESULT([no])
+    fi
+  fi
+  CBC_LIBS="$CBC_LDFLAGS $CBC_LIBS"
+  AC_SUBST(CBC_CXXFLAGS)
+  AC_SUBST(CBC_LIBS)
+  AM_CONDITIONAL([HAVE_CBC], [test x"$lx_cbc_found" = x"yes"])
+])
diff --git a/test/mip_test.cc b/test/mip_test.cc
--- a/test/mip_test.cc
+++ b/test/mip_test.cc
@@ -18,7 +18,6 @@
 
 #include "test_tools.h"
 
-
 #ifdef HAVE_CONFIG_H
 #include <lemon/config.h>
 #endif
@@ -31,6 +30,10 @@
 #include <lemon/glpk.h>
 #endif
 
+#ifdef HAVE_CBC
+#include <lemon/cbc.h>
+#endif
+
 
 using namespace lemon;
 
@@ -57,14 +60,13 @@
 
 void aTest(MipSolver& mip)
 {
- //The following example is very simple
+  //The following example is very simple
 
 
   typedef MipSolver::Row Row;
   typedef MipSolver::Col Col;
 
 
-
   Col x1 = mip.addCol();
   Col x2 = mip.addCol();
 
@@ -74,23 +76,24 @@
 
   mip.max();
 
-
   //Unconstrained optimization
   mip.solve();
   //Check it out!
 
   //Constraints
-  mip.addRow(2*x1+x2 <=2);
-  mip.addRow(x1-2*x2 <=0);
+  mip.addRow(2 * x1 + x2 <= 2);
+  Row y2 = mip.addRow(x1 - 2 * x2 <= 0);
 
   //Nonnegativity of the variable x1
   mip.colLowerBound(x1, 0);
 
+
   //Maximization of x1
   //over the triangle with vertices (0,0),(4/5,2/5),(0,2)
   double expected_opt=4.0/5.0;
   solveAndCheck(mip, MipSolver::OPTIMAL, expected_opt);
 
+
   //Restrict x2 to integer
   mip.colType(x2,MipSolver::INTEGER);
   expected_opt=1.0/2.0;
@@ -102,10 +105,15 @@
   expected_opt=0;
   solveAndCheck(mip, MipSolver::OPTIMAL, expected_opt);
 
-
+  //Erase a variable
+  mip.erase(x2);
+  mip.rowUpperBound(y2, 8);
+  expected_opt=1;
+  solveAndCheck(mip, MipSolver::OPTIMAL, expected_opt);
 
 }
 
+
 template<class MIP>
 void cloneTest()
 {
@@ -144,6 +152,14 @@
   }
 #endif
 
+#ifdef HAVE_CBC
+  {
+    CbcMip mip1;
+    aTest(mip1);
+    cloneTest<CbcMip>();
+  }
+#endif
+
   return 0;
 
 }