LEMON/LEMON-main Changeset - r746:e4554cd6b2bf

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r746:e4554cd6b2bf

« 745:68792f

747:a42f46 »

r746:e4554cd6b2bf

Sun, 04 Oct 2009 00:28:42

[Not Reviewed]

0 comments (0 inline)

deba@inf.elte.hu
deba@inf.elte.hu

Faster add row operation (#203) One virtual function call instead of more

0 13 0

default

13 files changed with 137 insertions and 4 deletions:

lemon/cbc.cc

lemon/cbc.h

lemon/clp.cc

lemon/clp.h

lemon/cplex.cc

lemon/cplex.h

lemon/glpk.cc

lemon/glpk.h

lemon/lp_base.h

lemon/lp_skeleton.cc

lemon/lp_skeleton.h

lemon/soplex.cc

lemon/soplex.h

↑ Collapse diff ↑

lemon/cbc.cc

Show inline comments

 		/* -*- 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;
 		    messageLevel(MESSAGE_NOTHING);
+		  }
 		  CbcMip::CbcMip(const CbcMip& other) {
 		    _prob = new CoinModel(*other._prob);
 		    _prob->setProblemName("LEMON");
 		    _osi_solver = 0;
 		    _cbc_model = 0;
 		    messageLevel(MESSAGE_NOTHING);
+		  }
 		  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;
+		  }
 		  int CbcMip::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
 		    std::vector<int> indexes;
 		    std::vector<Value> values;
 		    for(ExprIterator it = b; it != e; ++it) {
 		      indexes.push_back(it->first);
 		      values.push_back(it->second);
+		    }
 		    _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
 		    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);
 		    _osi_solver->messageHandler()->setLogLevel(_message_level);
 		    _cbc_model->setLogLevel(_message_level);
 		    _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 level) {
 		    switch (level) {
 		    case MESSAGE_NOTHING:
 		      _message_level = 0;
 		      break;
 		    case MESSAGE_ERROR:
 		      _message_level = 1;
 		      break;
 		    case MESSAGE_WARNING:
 		      _message_level = 1;
 		      break;
 		    case MESSAGE_NORMAL:
 		      _message_level = 2;
 		      break;
 		    case MESSAGE_VERBOSE:
 		      _message_level = 3;
 		      break;
+		    }
+		  }
 		} //END OF NAMESPACE LEMON

lemon/cbc.h

Show inline comments

 		/* -*- 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 int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
 		    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();
 		    virtual void _messageLevel(MessageLevel level);
 		    void _applyMessageLevel();
 		    int _message_level;
 		  };
+		}
 		#endif

lemon/clp.cc

Show inline comments

/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 2003-2008
 * 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.
 *
 */

#include <lemon/clp.h>
#include <coin/ClpSimplex.hpp>

namespace lemon {

  ClpLp::ClpLp() {
    _prob = new ClpSimplex();
    _init_temporals();
    messageLevel(MESSAGE_NOTHING);
  }

  ClpLp::ClpLp(const ClpLp& other) {
    _prob = new ClpSimplex(*other._prob);
    rows = other.rows;
    cols = other.cols;
    _init_temporals();
    messageLevel(MESSAGE_NOTHING);
  }

  ClpLp::~ClpLp() {
    delete _prob;
    _clear_temporals();
  }

  void ClpLp::_init_temporals() {
    _primal_ray = 0;
    _dual_ray = 0;
  }

  void ClpLp::_clear_temporals() {
    if (_primal_ray) {
      delete[] _primal_ray;
      _primal_ray = 0;
    }
    if (_dual_ray) {
      delete[] _dual_ray;
      _dual_ray = 0;
    }
  }

  ClpLp* ClpLp::newSolver() const {
    ClpLp* newlp = new ClpLp;
    return newlp;
  }

  ClpLp* ClpLp::cloneSolver() const {
    ClpLp* copylp = new ClpLp(*this);
    return copylp;
  }

  const char* ClpLp::_solverName() const { return "ClpLp"; }

  int ClpLp::_addCol() {
    _prob->addColumn(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX, 0.0);
    return _prob->numberColumns() - 1;
  }

  int ClpLp::_addRow() {
    _prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX);
    return _prob->numberRows() - 1;
  }

  int ClpLp::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
    std::vector<int> indexes;
    std::vector<Value> values;

    for(ExprIterator it = b; it != e; ++it) {
      indexes.push_back(it->first);
      values.push_back(it->second);
    }

    _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
    return _prob->numberRows() - 1;
  }


  void ClpLp::_eraseCol(int c) {
    _col_names_ref.erase(_prob->getColumnName(c));
    _prob->deleteColumns(1, &c);
  }

  void ClpLp::_eraseRow(int r) {
    _row_names_ref.erase(_prob->getRowName(r));
    _prob->deleteRows(1, &r);
  }

  void ClpLp::_eraseColId(int i) {
    cols.eraseIndex(i);
    cols.shiftIndices(i);
  }

  void ClpLp::_eraseRowId(int i) {
    rows.eraseIndex(i);
    rows.shiftIndices(i);
  }

  void ClpLp::_getColName(int c, std::string& name) const {
    name = _prob->getColumnName(c);
  }

  void ClpLp::_setColName(int c, const std::string& name) {
    _prob->setColumnName(c, const_cast<std::string&>(name));
    _col_names_ref[name] = c;
  }

  int ClpLp::_colByName(const std::string& name) const {
    std::map<std::string, int>::const_iterator it = _col_names_ref.find(name);
    return it != _col_names_ref.end() ? it->second : -1;
  }

  void ClpLp::_getRowName(int r, std::string& name) const {
    name = _prob->getRowName(r);
  }

  void ClpLp::_setRowName(int r, const std::string& name) {
    _prob->setRowName(r, const_cast<std::string&>(name));
    _row_names_ref[name] = r;
  }

  int ClpLp::_rowByName(const std::string& name) const {
    std::map<std::string, int>::const_iterator it = _row_names_ref.find(name);
    return it != _row_names_ref.end() ? it->second : -1;
  }


  void ClpLp::_setRowCoeffs(int ix, ExprIterator b, ExprIterator e) {
    std::map<int, Value> coeffs;

    int n = _prob->clpMatrix()->getNumCols();

    const int* indices = _prob->clpMatrix()->getIndices();
    const double* elements = _prob->clpMatrix()->getElements();

    for (int i = 0; i < n; ++i) {
      CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i];
      CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i];

      const int* it = std::lower_bound(indices + begin, indices + end, ix);
      if (it != indices + end && *it == ix && elements[it - indices] != 0.0) {
        coeffs[i] = 0.0;
      }
    }

    for (ExprIterator it = b; it != e; ++it) {
      coeffs[it->first] = it->second;
    }

    for (std::map<int, Value>::iterator it = coeffs.begin();
         it != coeffs.end(); ++it) {
      _prob->modifyCoefficient(ix, it->first, it->second);
    }
  }

  void ClpLp::_getRowCoeffs(int ix, InsertIterator b) const {
    int n = _prob->clpMatrix()->getNumCols();

    const int* indices = _prob->clpMatrix()->getIndices();
    const double* elements = _prob->clpMatrix()->getElements();

    for (int i = 0; i < n; ++i) {
      CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i];
      CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i];

      const int* it = std::lower_bound(indices + begin, indices + end, ix);
      if (it != indices + end && *it == ix) {
        *b = std::make_pair(i, elements[it - indices]);
      }
    }
  }

  void ClpLp::_setColCoeffs(int ix, ExprIterator b, ExprIterator e) {
    std::map<int, Value> coeffs;

    CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];
    CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];

    const int* indices = _prob->clpMatrix()->getIndices();
    const double* elements = _prob->clpMatrix()->getElements();

    for (CoinBigIndex i = begin; i != end; ++i) {
      if (elements[i] != 0.0) {
        coeffs[indices[i]] = 0.0;
      }
    }
    for (ExprIterator it = b; it != e; ++it) {
      coeffs[it->first] = it->second;
    }
    for (std::map<int, Value>::iterator it = coeffs.begin();
         it != coeffs.end(); ++it) {
      _prob->modifyCoefficient(it->first, ix, it->second);
    }
  }

  void ClpLp::_getColCoeffs(int ix, InsertIterator b) const {
    CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];
    CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];

    const int* indices = _prob->clpMatrix()->getIndices();
    const double* elements = _prob->clpMatrix()->getElements();

    for (CoinBigIndex i = begin; i != end; ++i) {
      *b = std::make_pair(indices[i], elements[i]);
      ++b;
    }
  }

  void ClpLp::_setCoeff(int ix, int jx, Value value) {
    _prob->modifyCoefficient(ix, jx, value);
  }

  ClpLp::Value ClpLp::_getCoeff(int ix, int jx) const {
    CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];
    CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];

    const int* indices = _prob->clpMatrix()->getIndices();
    const double* elements = _prob->clpMatrix()->getElements();

    const int* it = std::lower_bound(indices + begin, indices + end, jx);
    if (it != indices + end && *it == jx) {
      return elements[it - indices];
    } else {
      return 0.0;
    }
  }

  void ClpLp::_setColLowerBound(int i, Value lo) {
    _prob->setColumnLower(i, lo == - INF ? - COIN_DBL_MAX : lo);
  }

  ClpLp::Value ClpLp::_getColLowerBound(int i) const {
    double val = _prob->getColLower()[i];
    return val == - COIN_DBL_MAX ? - INF : val;
  }

  void ClpLp::_setColUpperBound(int i, Value up) {
    _prob->setColumnUpper(i, up == INF ? COIN_DBL_MAX : up);
  }

  ClpLp::Value ClpLp::_getColUpperBound(int i) const {
    double val = _prob->getColUpper()[i];
    return val == COIN_DBL_MAX ? INF : val;
  }

  void ClpLp::_setRowLowerBound(int i, Value lo) {
    _prob->setRowLower(i, lo == - INF ? - COIN_DBL_MAX : lo);
  }

  ClpLp::Value ClpLp::_getRowLowerBound(int i) const {
    double val = _prob->getRowLower()[i];
    return val == - COIN_DBL_MAX ? - INF : val;
  }

  void ClpLp::_setRowUpperBound(int i, Value up) {
    _prob->setRowUpper(i, up == INF ? COIN_DBL_MAX : up);
  }

  ClpLp::Value ClpLp::_getRowUpperBound(int i) const {
    double val = _prob->getRowUpper()[i];
    return val == COIN_DBL_MAX ? INF : val;
  }

  void ClpLp::_setObjCoeffs(ExprIterator b, ExprIterator e) {
    int num = _prob->clpMatrix()->getNumCols();
    for (int i = 0; i < num; ++i) {
      _prob->setObjectiveCoefficient(i, 0.0);
    }
    for (ExprIterator it = b; it != e; ++it) {
      _prob->setObjectiveCoefficient(it->first, it->second);
    }
  }

  void ClpLp::_getObjCoeffs(InsertIterator b) const {
    int num = _prob->clpMatrix()->getNumCols();
    for (int i = 0; i < num; ++i) {
      Value coef = _prob->getObjCoefficients()[i];
      if (coef != 0.0) {
        *b = std::make_pair(i, coef);
        ++b;
      }
    }
  }

  void ClpLp::_setObjCoeff(int i, Value obj_coef) {
    _prob->setObjectiveCoefficient(i, obj_coef);
  }

  ClpLp::Value ClpLp::_getObjCoeff(int i) const {
    return _prob->getObjCoefficients()[i];
  }

  ClpLp::SolveExitStatus ClpLp::_solve() {
    return _prob->primal() >= 0 ? SOLVED : UNSOLVED;
  }

  ClpLp::SolveExitStatus ClpLp::solvePrimal() {
    return _prob->primal() >= 0 ? SOLVED : UNSOLVED;
  }

  ClpLp::SolveExitStatus ClpLp::solveDual() {
    return _prob->dual() >= 0 ? SOLVED : UNSOLVED;
  }

  ClpLp::SolveExitStatus ClpLp::solveBarrier() {
    return _prob->barrier() >= 0 ? SOLVED : UNSOLVED;
  }

  ClpLp::Value ClpLp::_getPrimal(int i) const {
    return _prob->primalColumnSolution()[i];
  }
  ClpLp::Value ClpLp::_getPrimalValue() const {
    return _prob->objectiveValue();
  }

  ClpLp::Value ClpLp::_getDual(int i) const {
    return _prob->dualRowSolution()[i];
  }

  ClpLp::Value ClpLp::_getPrimalRay(int i) const {
    if (!_primal_ray) {
      _primal_ray = _prob->unboundedRay();
      LEMON_ASSERT(_primal_ray != 0, "Primal ray is not provided");
    }
    return _primal_ray[i];
  }

  ClpLp::Value ClpLp::_getDualRay(int i) const {
    if (!_dual_ray) {
      _dual_ray = _prob->infeasibilityRay();
      LEMON_ASSERT(_dual_ray != 0, "Dual ray is not provided");
    }
    return _dual_ray[i];
  }

  ClpLp::VarStatus ClpLp::_getColStatus(int i) const {
    switch (_prob->getColumnStatus(i)) {
    case ClpSimplex::basic:
      return BASIC;
    case ClpSimplex::isFree:
      return FREE;
    case ClpSimplex::atUpperBound:
      return UPPER;
    case ClpSimplex::atLowerBound:
      return LOWER;
    case ClpSimplex::isFixed:
      return FIXED;
    case ClpSimplex::superBasic:
      return FREE;
    default:
      LEMON_ASSERT(false, "Wrong column status");
      return VarStatus();
    }
  }

  ClpLp::VarStatus ClpLp::_getRowStatus(int i) const {
    switch (_prob->getColumnStatus(i)) {
    case ClpSimplex::basic:
      return BASIC;
    case ClpSimplex::isFree:
      return FREE;
    case ClpSimplex::atUpperBound:
      return UPPER;
    case ClpSimplex::atLowerBound:
      return LOWER;
    case ClpSimplex::isFixed:
      return FIXED;
    case ClpSimplex::superBasic:
      return FREE;
    default:
      LEMON_ASSERT(false, "Wrong row status");
      return VarStatus();
    }
  }


  ClpLp::ProblemType ClpLp::_getPrimalType() const {
    if (_prob->isProvenOptimal()) {
      return OPTIMAL;
    } else if (_prob->isProvenPrimalInfeasible()) {
      return INFEASIBLE;
    } else if (_prob->isProvenDualInfeasible()) {
      return UNBOUNDED;
    } else {
      return UNDEFINED;
    }
  }

  ClpLp::ProblemType ClpLp::_getDualType() const {
    if (_prob->isProvenOptimal()) {
      return OPTIMAL;
    } else if (_prob->isProvenDualInfeasible()) {
      return INFEASIBLE;
    } else if (_prob->isProvenPrimalInfeasible()) {
      return INFEASIBLE;
    } else {
      return UNDEFINED;
    }
  }

  void ClpLp::_setSense(ClpLp::Sense sense) {
    switch (sense) {
    case MIN:
      _prob->setOptimizationDirection(1);
      break;
    case MAX:
      _prob->setOptimizationDirection(-1);
      break;
    }
  }

  ClpLp::Sense ClpLp::_getSense() const {
    double dir = _prob->optimizationDirection();
    if (dir > 0.0) {
      return MIN;
    } else {
      return MAX;
    }
  }

  void ClpLp::_clear() {
    delete _prob;
    _prob = new ClpSimplex();
    rows.clear();
    cols.clear();
    _col_names_ref.clear();
    _clear_temporals();
  }

  void ClpLp::_messageLevel(MessageLevel level) {
    switch (level) {
    case MESSAGE_NOTHING:
      _prob->setLogLevel(0);
      break;
    case MESSAGE_ERROR:
      _prob->setLogLevel(1);
      break;
    case MESSAGE_WARNING:
      _prob->setLogLevel(2);
      break;
    case MESSAGE_NORMAL:
      _prob->setLogLevel(3);
      break;
    case MESSAGE_VERBOSE:
      _prob->setLogLevel(4);
      break;
    }
  }

} //END OF NAMESPACE LEMON

lemon/clp.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * 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.
+		 *
 		 */
 		#ifndef LEMON_CLP_H
 		#define LEMON_CLP_H
 		///\file
 		///\brief Header of the LEMON-CLP lp solver interface.
 		#include <vector>
 		#include <string>
 		#include <lemon/lp_base.h>
 		class ClpSimplex;
 		namespace lemon {
 		  /// \ingroup lp_group
 		  ///
 		  /// \brief Interface for the CLP solver
 		  ///
 		  /// This class implements an interface for the Clp LP solver.  The
 		  /// Clp library is an object oriented lp solver library developed at
 		  /// the IBM. The CLP is part of the COIN-OR package and it can be
 		  /// used with Common Public License.
 		  class ClpLp : public LpSolver {
 		  protected:
 		    ClpSimplex* _prob;
 		    std::map<std::string, int> _col_names_ref;
 		    std::map<std::string, int> _row_names_ref;
 		  public:
 		    /// \e
 		    ClpLp();
 		    /// \e
 		    ClpLp(const ClpLp&);
 		    /// \e
 		    ~ClpLp();
 		    /// \e
 		    virtual ClpLp* newSolver() const;
 		    /// \e
 		    virtual ClpLp* cloneSolver() const;
 		  protected:
 		    mutable double* _primal_ray;
 		    mutable double* _dual_ray;
 		    void _init_temporals();
 		    void _clear_temporals();
 		  protected:
 		    virtual const char* _solverName() const;
 		    virtual int _addCol();
 		    virtual int _addRow();
 		    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
 		    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, ExprIterator);
 		    virtual void _getObjCoeffs(InsertIterator) 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 SolveExitStatus _solve();
 		    virtual Value _getPrimal(int i) const;
 		    virtual Value _getDual(int i) const;
 		    virtual Value _getPrimalValue() const;
 		    virtual Value _getPrimalRay(int i) const;
 		    virtual Value _getDualRay(int i) const;
 		    virtual VarStatus _getColStatus(int i) const;
 		    virtual VarStatus _getRowStatus(int i) const;
 		    virtual ProblemType _getPrimalType() const;
 		    virtual ProblemType _getDualType() const;
 		    virtual void _clear();
 		    virtual void _messageLevel(MessageLevel);
 		  public:
 		    ///Solves LP with primal simplex method.
 		    SolveExitStatus solvePrimal();
 		    ///Solves LP with dual simplex method.
 		    SolveExitStatus solveDual();
 		    ///Solves LP with barrier method.
 		    SolveExitStatus solveBarrier();
 		    ///Returns the constraint identifier understood by CLP.
 		    int clpRow(Row r) const { return rows(id(r)); }
 		    ///Returns the variable identifier understood by CLP.
 		    int clpCol(Col c) const { return cols(id(c)); }
 		  };
 		} //END OF NAMESPACE LEMON
 		#endif //LEMON_CLP_H

lemon/cplex.cc

Show inline comments

 		/* -*- 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.
+		 *
 		 */
 		#include <iostream>
 		#include <vector>
 		#include <cstring>
 		#include <lemon/cplex.h>
 		extern "C" {
 		#include <ilcplex/cplex.h>
+		}
 		///\file
 		///\brief Implementation of the LEMON-CPLEX lp solver interface.
 		namespace lemon {
 		  CplexEnv::LicenseError::LicenseError(int status) {
 		    if (!CPXgeterrorstring(0, status, _message)) {
 		      std::strcpy(_message, "Cplex unknown error");
+		    }
+		  }
 		  CplexEnv::CplexEnv() {
 		    int status;
 		    _cnt = new int;
 		    _env = CPXopenCPLEX(&status);
 		    if (_env == 0) {
 		      delete _cnt;
 		      _cnt = 0;
 		      throw LicenseError(status);
+		    }
+		  }
 		  CplexEnv::CplexEnv(const CplexEnv& other) {
 		    _env = other._env;
 		    _cnt = other._cnt;
 		    ++(*_cnt);
+		  }
 		  CplexEnv& CplexEnv::operator=(const CplexEnv& other) {
 		    _env = other._env;
 		    _cnt = other._cnt;
 		    ++(*_cnt);
 		    return *this;
+		  }
 		  CplexEnv::~CplexEnv() {
 		    --(*_cnt);
 		    if (*_cnt == 0) {
 		      delete _cnt;
 		      CPXcloseCPLEX(&_env);
+		    }
+		  }
 		  CplexBase::CplexBase() : LpBase() {
 		    int status;
 		    _prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem");
 		    messageLevel(MESSAGE_NOTHING);
+		  }
 		  CplexBase::CplexBase(const CplexEnv& env)
 		    : LpBase(), _env(env) {
 		    int status;
 		    _prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem");
 		    messageLevel(MESSAGE_NOTHING);
+		  }
 		  CplexBase::CplexBase(const CplexBase& cplex)
 		    : LpBase() {
 		    int status;
 		    _prob = CPXcloneprob(cplexEnv(), cplex._prob, &status);
 		    rows = cplex.rows;
 		    cols = cplex.cols;
 		    messageLevel(MESSAGE_NOTHING);
+		  }
 		  CplexBase::~CplexBase() {
 		    CPXfreeprob(cplexEnv(),&_prob);
+		  }
 		  int CplexBase::_addCol() {
 		    int i = CPXgetnumcols(cplexEnv(), _prob);
 		    double lb = -INF, ub = INF;
 		    CPXnewcols(cplexEnv(), _prob, 1, 0, &lb, &ub, 0, 0);
 		    return i;
+		  }
 		  int CplexBase::_addRow() {
 		    int i = CPXgetnumrows(cplexEnv(), _prob);
 		    const double ub = INF;
 		    const char s = 'L';
 		    CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0);
 		    return i;
+		  }
 		  int CplexBase::_addRow(Value lb, ExprIterator b,
 		                         ExprIterator e, Value ub) {
 		    int i = CPXgetnumrows(cplexEnv(), _prob);
 		    if (lb == -INF) {
 		      const char s = 'L';
 		      CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0);
 		    } else if (ub == INF) {
 		      const char s = 'G';
 		      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
 		    } else if (lb == ub){
 		      const char s = 'E';
 		      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
 		    } else {
 		      const char s = 'R';
 		      double len = ub - lb;
 		      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, &len, 0);
+		    }
 		    std::vector<int> indices;
 		    std::vector<int> rowlist;
 		    std::vector<Value> values;
 		    for(ExprIterator it=b; it!=e; ++it) {
 		      indices.push_back(it->first);
 		      values.push_back(it->second);
 		      rowlist.push_back(i);
+		    }
 		    CPXchgcoeflist(cplexEnv(), _prob, values.size(),
 		                   &rowlist.front(), &indices.front(), &values.front());
 		    return i;
+		  }
 		  void CplexBase::_eraseCol(int i) {
 		    CPXdelcols(cplexEnv(), _prob, i, i);
+		  }
 		  void CplexBase::_eraseRow(int i) {
 		    CPXdelrows(cplexEnv(), _prob, i, i);
+		  }
 		  void CplexBase::_eraseColId(int i) {
 		    cols.eraseIndex(i);
 		    cols.shiftIndices(i);
+		  }
 		  void CplexBase::_eraseRowId(int i) {
 		    rows.eraseIndex(i);
 		    rows.shiftIndices(i);
+		  }
 		  void CplexBase::_getColName(int col, std::string &name) const {
 		    int size;
 		    CPXgetcolname(cplexEnv(), _prob, 0, 0, 0, &size, col, col);
 		    if (size == 0) {
 		      name.clear();
 		      return;
+		    }
 		    size *= -1;
 		    std::vector<char> buf(size);
 		    char *cname;
 		    int tmp;
 		    CPXgetcolname(cplexEnv(), _prob, &cname, &buf.front(), size,
 		                  &tmp, col, col);
 		    name = cname;
+		  }
 		  void CplexBase::_setColName(int col, const std::string &name) {
 		    char *cname;
 		    cname = const_cast<char*>(name.c_str());
 		    CPXchgcolname(cplexEnv(), _prob, 1, &col, &cname);
+		  }
 		  int CplexBase::_colByName(const std::string& name) const {
 		    int index;
 		    if (CPXgetcolindex(cplexEnv(), _prob,
 		                       const_cast<char*>(name.c_str()), &index) == 0) {
 		      return index;
+		    }
 		    return -1;
+		  }
 		  void CplexBase::_getRowName(int row, std::string &name) const {
 		    int size;
 		    CPXgetrowname(cplexEnv(), _prob, 0, 0, 0, &size, row, row);
 		    if (size == 0) {
 		      name.clear();
 		      return;
+		    }
 		    size *= -1;
 		    std::vector<char> buf(size);
 		    char *cname;
 		    int tmp;
 		    CPXgetrowname(cplexEnv(), _prob, &cname, &buf.front(), size,
 		                  &tmp, row, row);
 		    name = cname;
+		  }
 		  void CplexBase::_setRowName(int row, const std::string &name) {
 		    char *cname;
 		    cname = const_cast<char*>(name.c_str());
 		    CPXchgrowname(cplexEnv(), _prob, 1, &row, &cname);
+		  }
 		  int CplexBase::_rowByName(const std::string& name) const {
 		    int index;
 		    if (CPXgetrowindex(cplexEnv(), _prob,
 		                       const_cast<char*>(name.c_str()), &index) == 0) {
 		      return index;
+		    }
 		    return -1;
+		  }
 		  void CplexBase::_setRowCoeffs(int i, ExprIterator b,
 		                                      ExprIterator e)
+		  {
 		    std::vector<int> indices;
 		    std::vector<int> rowlist;
 		    std::vector<Value> values;
 		    for(ExprIterator it=b; it!=e; ++it) {
 		      indices.push_back(it->first);
 		      values.push_back(it->second);
 		      rowlist.push_back(i);
+		    }
 		    CPXchgcoeflist(cplexEnv(), _prob, values.size(),
 		                   &rowlist.front(), &indices.front(), &values.front());
+		  }
 		  void CplexBase::_getRowCoeffs(int i, InsertIterator b) const {
 		    int tmp1, tmp2, tmp3, length;
 		    CPXgetrows(cplexEnv(), _prob, &tmp1, &tmp2, 0, 0, 0, &length, i, i);
 		    length = -length;
 		    std::vector<int> indices(length);
 		    std::vector<double> values(length);
 		    CPXgetrows(cplexEnv(), _prob, &tmp1, &tmp2,
 		               &indices.front(), &values.front(),
 		               length, &tmp3, i, i);
 		    for (int i = 0; i < length; ++i) {
 		      *b = std::make_pair(indices[i], values[i]);
 		      ++b;
+		    }
+		  }
 		  void CplexBase::_setColCoeffs(int i, ExprIterator b, ExprIterator e) {
 		    std::vector<int> indices;
 		    std::vector<int> collist;
 		    std::vector<Value> values;
 		    for(ExprIterator it=b; it!=e; ++it) {
 		      indices.push_back(it->first);
 		      values.push_back(it->second);
 		      collist.push_back(i);
+		    }
 		    CPXchgcoeflist(cplexEnv(), _prob, values.size(),
 		                   &indices.front(), &collist.front(), &values.front());
+		  }
 		  void CplexBase::_getColCoeffs(int i, InsertIterator b) const {
 		    int tmp1, tmp2, tmp3, length;
 		    CPXgetcols(cplexEnv(), _prob, &tmp1, &tmp2, 0, 0, 0, &length, i, i);
 		    length = -length;
 		    std::vector<int> indices(length);
 		    std::vector<double> values(length);
 		    CPXgetcols(cplexEnv(), _prob, &tmp1, &tmp2,
 		               &indices.front(), &values.front(),
 		               length, &tmp3, i, i);
 		    for (int i = 0; i < length; ++i) {
 		      *b = std::make_pair(indices[i], values[i]);
 		      ++b;
+		    }
+		  }
 		  void CplexBase::_setCoeff(int row, int col, Value value) {
 		    CPXchgcoef(cplexEnv(), _prob, row, col, value);
+		  }
 		  CplexBase::Value CplexBase::_getCoeff(int row, int col) const {
 		    CplexBase::Value value;
 		    CPXgetcoef(cplexEnv(), _prob, row, col, &value);
 		    return value;
+		  }
 		  void CplexBase::_setColLowerBound(int i, Value value) {
 		    const char s = 'L';
 		    CPXchgbds(cplexEnv(), _prob, 1, &i, &s, &value);
+		  }
 		  CplexBase::Value CplexBase::_getColLowerBound(int i) const {
 		    CplexBase::Value res;
 		    CPXgetlb(cplexEnv(), _prob, &res, i, i);
 		    return res <= -CPX_INFBOUND ? -INF : res;
+		  }
 		  void CplexBase::_setColUpperBound(int i, Value value)
+		  {
 		    const char s = 'U';
 		    CPXchgbds(cplexEnv(), _prob, 1, &i, &s, &value);
+		  }
 		  CplexBase::Value CplexBase::_getColUpperBound(int i) const {
 		    CplexBase::Value res;
 		    CPXgetub(cplexEnv(), _prob, &res, i, i);
 		    return res >= CPX_INFBOUND ? INF : res;
+		  }
 		  CplexBase::Value CplexBase::_getRowLowerBound(int i) const {
 		    char s;
 		    CPXgetsense(cplexEnv(), _prob, &s, i, i);
 		    CplexBase::Value res;
 		    switch (s) {
 		    case 'G':
 		    case 'R':
 		    case 'E':
 		      CPXgetrhs(cplexEnv(), _prob, &res, i, i);
 		      return res <= -CPX_INFBOUND ? -INF : res;
 		    default:
 		      return -INF;
+		    }
+		  }
 		  CplexBase::Value CplexBase::_getRowUpperBound(int i) const {
 		    char s;
 		    CPXgetsense(cplexEnv(), _prob, &s, i, i);
 		    CplexBase::Value res;
 		    switch (s) {
 		    case 'L':
 		    case 'E':
 		      CPXgetrhs(cplexEnv(), _prob, &res, i, i);
 		      return res >= CPX_INFBOUND ? INF : res;
 		    case 'R':
 		      CPXgetrhs(cplexEnv(), _prob, &res, i, i);
+		      {
 		        double rng;
 		        CPXgetrngval(cplexEnv(), _prob, &rng, i, i);
 		        res += rng;
+		      }
 		      return res >= CPX_INFBOUND ? INF : res;
 		    default:
 		      return INF;
+		    }
+		  }
 		  //This is easier to implement
 		  void CplexBase::_set_row_bounds(int i, Value lb, Value ub) {
 		    if (lb == -INF) {
 		      const char s = 'L';
 		      CPXchgsense(cplexEnv(), _prob, 1, &i, &s);
 		      CPXchgrhs(cplexEnv(), _prob, 1, &i, &ub);
 		    } else if (ub == INF) {
 		      const char s = 'G';
 		      CPXchgsense(cplexEnv(), _prob, 1, &i, &s);
 		      CPXchgrhs(cplexEnv(), _prob, 1, &i, &lb);
 		    } else if (lb == ub){
 		      const char s = 'E';
 		      CPXchgsense(cplexEnv(), _prob, 1, &i, &s);
 		      CPXchgrhs(cplexEnv(), _prob, 1, &i, &lb);
 		    } else {
 		      const char s = 'R';
 		      CPXchgsense(cplexEnv(), _prob, 1, &i, &s);
 		      CPXchgrhs(cplexEnv(), _prob, 1, &i, &lb);
 		      double len = ub - lb;
 		      CPXchgrngval(cplexEnv(), _prob, 1, &i, &len);
+		    }
+		  }
 		  void CplexBase::_setRowLowerBound(int i, Value lb)
+		  {
 		    LEMON_ASSERT(lb != INF, "Invalid bound");
 		    _set_row_bounds(i, lb, CplexBase::_getRowUpperBound(i));
+		  }
 		  void CplexBase::_setRowUpperBound(int i, Value ub)
+		  {
 		    LEMON_ASSERT(ub != -INF, "Invalid bound");
 		    _set_row_bounds(i, CplexBase::_getRowLowerBound(i), ub);
+		  }
 		  void CplexBase::_setObjCoeffs(ExprIterator b, ExprIterator e)
+		  {
 		    std::vector<int> indices;
 		    std::vector<Value> values;
 		    for(ExprIterator it=b; it!=e; ++it) {
 		      indices.push_back(it->first);
 		      values.push_back(it->second);
+		    }
 		    CPXchgobj(cplexEnv(), _prob, values.size(),
 		              &indices.front(), &values.front());
+		  }
 		  void CplexBase::_getObjCoeffs(InsertIterator b) const
+		  {
 		    int num = CPXgetnumcols(cplexEnv(), _prob);
 		    std::vector<Value> x(num);
 		    CPXgetobj(cplexEnv(), _prob, &x.front(), 0, num - 1);
 		    for (int i = 0; i < num; ++i) {
 		      if (x[i] != 0.0) {
 		        *b = std::make_pair(i, x[i]);
 		        ++b;
+		      }
+		    }
+		  }
 		  void CplexBase::_setObjCoeff(int i, Value obj_coef)
+		  {
 		    CPXchgobj(cplexEnv(), _prob, 1, &i, &obj_coef);
+		  }
 		  CplexBase::Value CplexBase::_getObjCoeff(int i) const
+		  {
 		    Value x;
 		    CPXgetobj(cplexEnv(), _prob, &x, i, i);
 		    return x;
+		  }
 		  void CplexBase::_setSense(CplexBase::Sense sense) {
 		    switch (sense) {
 		    case MIN:
 		      CPXchgobjsen(cplexEnv(), _prob, CPX_MIN);
 		      break;
 		    case MAX:
 		      CPXchgobjsen(cplexEnv(), _prob, CPX_MAX);
 		      break;
+		    }
+		  }
 		  CplexBase::Sense CplexBase::_getSense() const {
 		    switch (CPXgetobjsen(cplexEnv(), _prob)) {
 		    case CPX_MIN:
 		      return MIN;
 		    case CPX_MAX:
 		      return MAX;
 		    default:
 		      LEMON_ASSERT(false, "Invalid sense");
 		      return CplexBase::Sense();
+		    }
+		  }
 		  void CplexBase::_clear() {
 		    CPXfreeprob(cplexEnv(),&_prob);
 		    int status;
 		    _prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem");
 		    rows.clear();
 		    cols.clear();
+		  }
 		  void CplexBase::_messageLevel(MessageLevel level) {
 		    switch (level) {
 		    case MESSAGE_NOTHING:
 		      _message_enabled = false;
 		      break;
 		    case MESSAGE_ERROR:
 		    case MESSAGE_WARNING:
 		    case MESSAGE_NORMAL:
 		    case MESSAGE_VERBOSE:
 		      _message_enabled = true;
 		      break;
+		    }
+		  }
 		  void CplexBase::_applyMessageLevel() {
 		    CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND,
 		                   _message_enabled ? CPX_ON : CPX_OFF);
+		  }
 		  // CplexLp members
 		  CplexLp::CplexLp()
 		    : LpBase(), LpSolver(), CplexBase() {}
 		  CplexLp::CplexLp(const CplexEnv& env)
 		    : LpBase(), LpSolver(), CplexBase(env) {}
 		  CplexLp::CplexLp(const CplexLp& other)
 		    : LpBase(), LpSolver(), CplexBase(other) {}
 		  CplexLp::~CplexLp() {}
 		  CplexLp* CplexLp::newSolver() const { return new CplexLp; }
 		  CplexLp* CplexLp::cloneSolver() const {return new CplexLp(*this); }
 		  const char* CplexLp::_solverName() const { return "CplexLp"; }
 		  void CplexLp::_clear_temporals() {
 		    _col_status.clear();
 		    _row_status.clear();
 		    _primal_ray.clear();
 		    _dual_ray.clear();
+		  }
 		  // The routine returns zero unless an error occurred during the
 		  // optimization. Examples of errors include exhausting available
 		  // memory (CPXERR_NO_MEMORY) or encountering invalid data in the
 		  // CPLEX problem object (CPXERR_NO_PROBLEM). Exceeding a
 		  // user-specified CPLEX limit, or proving the model infeasible or
 		  // unbounded, are not considered errors. Note that a zero return
 		  // value does not necessarily mean that a solution exists. Use query
 		  // routines CPXsolninfo, CPXgetstat, and CPXsolution to obtain
 		  // further information about the status of the optimization.
 		  CplexLp::SolveExitStatus CplexLp::convertStatus(int status) {
 		#if CPX_VERSION >= 800
 		    if (status == 0) {
 		      switch (CPXgetstat(cplexEnv(), _prob)) {
 		      case CPX_STAT_OPTIMAL:
 		      case CPX_STAT_INFEASIBLE:
 		      case CPX_STAT_UNBOUNDED:
 		        return SOLVED;
 		      default:
 		        return UNSOLVED;
+		      }
 		    } else {
 		      return UNSOLVED;
+		    }
 		#else
 		    if (status == 0) {
 		      //We want to exclude some cases
 		      switch (CPXgetstat(cplexEnv(), _prob)) {
 		      case CPX_OBJ_LIM:
 		      case CPX_IT_LIM_FEAS:
 		      case CPX_IT_LIM_INFEAS:
 		      case CPX_TIME_LIM_FEAS:
 		      case CPX_TIME_LIM_INFEAS:
 		        return UNSOLVED;
 		      default:
 		        return SOLVED;
+		      }
 		    } else {
 		      return UNSOLVED;
+		    }
 		#endif
+		  }
 		  CplexLp::SolveExitStatus CplexLp::_solve() {
 		    _clear_temporals();
 		    _applyMessageLevel();
 		    return convertStatus(CPXlpopt(cplexEnv(), _prob));
+		  }
 		  CplexLp::SolveExitStatus CplexLp::solvePrimal() {
 		    _clear_temporals();
 		    _applyMessageLevel();
 		    return convertStatus(CPXprimopt(cplexEnv(), _prob));
+		  }
 		  CplexLp::SolveExitStatus CplexLp::solveDual() {
 		    _clear_temporals();
 		    _applyMessageLevel();
 		    return convertStatus(CPXdualopt(cplexEnv(), _prob));
+		  }
 		  CplexLp::SolveExitStatus CplexLp::solveBarrier() {
 		    _clear_temporals();
 		    _applyMessageLevel();
 		    return convertStatus(CPXbaropt(cplexEnv(), _prob));
+		  }
 		  CplexLp::Value CplexLp::_getPrimal(int i) const {
 		    Value x;
 		    CPXgetx(cplexEnv(), _prob, &x, i, i);
 		    return x;
+		  }
 		  CplexLp::Value CplexLp::_getDual(int i) const {
 		    Value y;
 		    CPXgetpi(cplexEnv(), _prob, &y, i, i);
 		    return y;
+		  }
 		  CplexLp::Value CplexLp::_getPrimalValue() const {
 		    Value objval;
 		    CPXgetobjval(cplexEnv(), _prob, &objval);
 		    return objval;
+		  }
 		  CplexLp::VarStatus CplexLp::_getColStatus(int i) const {
 		    if (_col_status.empty()) {
 		      _col_status.resize(CPXgetnumcols(cplexEnv(), _prob));
 		      CPXgetbase(cplexEnv(), _prob, &_col_status.front(), 0);
+		    }
 		    switch (_col_status[i]) {
 		    case CPX_BASIC:
 		      return BASIC;
 		    case CPX_FREE_SUPER:
 		      return FREE;
 		    case CPX_AT_LOWER:
 		      return LOWER;
 		    case CPX_AT_UPPER:
 		      return UPPER;
 		    default:
 		      LEMON_ASSERT(false, "Wrong column status");
 		      return CplexLp::VarStatus();
+		    }
+		  }
 		  CplexLp::VarStatus CplexLp::_getRowStatus(int i) const {
 		    if (_row_status.empty()) {
 		      _row_status.resize(CPXgetnumrows(cplexEnv(), _prob));
 		      CPXgetbase(cplexEnv(), _prob, 0, &_row_status.front());
+		    }
 		    switch (_row_status[i]) {
 		    case CPX_BASIC:
 		      return BASIC;
 		    case CPX_AT_LOWER:
+		      {
 		        char s;
 		        CPXgetsense(cplexEnv(), _prob, &s, i, i);
 		        return s != 'L' ? LOWER : UPPER;
+		      }
 		    case CPX_AT_UPPER:
 		      return UPPER;
 		    default:
 		      LEMON_ASSERT(false, "Wrong row status");
 		      return CplexLp::VarStatus();
+		    }
+		  }
 		  CplexLp::Value CplexLp::_getPrimalRay(int i) const {
 		    if (_primal_ray.empty()) {
 		      _primal_ray.resize(CPXgetnumcols(cplexEnv(), _prob));
 		      CPXgetray(cplexEnv(), _prob, &_primal_ray.front());
+		    }
 		    return _primal_ray[i];
+		  }
 		  CplexLp::Value CplexLp::_getDualRay(int i) const {
 		    if (_dual_ray.empty()) {
+		    }

lemon/cplex.h

Show inline comments

 		/* -*- 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.
+		 *
 		 */
 		#ifndef LEMON_CPLEX_H
 		#define LEMON_CPLEX_H
 		///\file
 		///\brief Header of the LEMON-CPLEX lp solver interface.
 		#include <lemon/lp_base.h>
 		struct cpxenv;
 		struct cpxlp;
 		namespace lemon {
 		  /// \brief Reference counted wrapper around cpxenv pointer
 		  ///
 		  /// The cplex uses environment object which is responsible for
 		  /// checking the proper license usage. This class provides a simple
 		  /// interface for share the environment object between different
 		  /// problems.
 		  class CplexEnv {
 		    friend class CplexBase;
 		  private:
 		    cpxenv* _env;
 		    mutable int* _cnt;
 		  public:
 		    /// \brief This exception is thrown when the license check is not
 		    /// sufficient
 		    class LicenseError : public Exception {
 		      friend class CplexEnv;
 		    private:
 		      LicenseError(int status);
 		      char _message[510];
 		    public:
 		      /// The short error message
 		      virtual const char* what() const throw() {
 		        return _message;
+		      }
 		    };
 		    /// Constructor
 		    CplexEnv();
 		    /// Shallow copy constructor
 		    CplexEnv(const CplexEnv&);
 		    /// Shallow assignement
 		    CplexEnv& operator=(const CplexEnv&);
 		    /// Destructor
 		    virtual ~CplexEnv();
 		  protected:
 		    cpxenv* cplexEnv() { return _env; }
 		    const cpxenv* cplexEnv() const { return _env; }
 		  };
 		  /// \brief Base interface for the CPLEX LP and MIP solver
 		  ///
 		  /// This class implements the common interface of the CPLEX LP and
 		  /// MIP solvers.
 		  /// \ingroup lp_group
 		  class CplexBase : virtual public LpBase {
 		  protected:
 		    CplexEnv _env;
 		    cpxlp* _prob;
 		    CplexBase();
 		    CplexBase(const CplexEnv&);
 		    CplexBase(const CplexBase &);
 		    virtual ~CplexBase();
 		    virtual int _addCol();
 		    virtual int _addRow();
 		    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
 		    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;
 		  private:
 		    void _set_row_bounds(int i, Value lb, Value ub);
 		  protected:
 		    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 void _clear();
 		    virtual void _messageLevel(MessageLevel level);
 		    void _applyMessageLevel();
 		    bool _message_enabled;
 		  public:
 		    /// Returns the used \c CplexEnv instance
 		    const CplexEnv& env() const { return _env; }
 		    /// \brief Returns the const cpxenv pointer
 		    ///
 		    /// \note The cpxenv might be destructed with the solver.
 		    const cpxenv* cplexEnv() const { return _env.cplexEnv(); }
 		    /// \brief Returns the const cpxenv pointer
 		    ///
 		    /// \note The cpxenv might be destructed with the solver.
 		    cpxenv* cplexEnv() { return _env.cplexEnv(); }
 		    /// Returns the cplex problem object
 		    cpxlp* cplexLp() { return _prob; }
 		    /// Returns the cplex problem object
 		    const cpxlp* cplexLp() const { return _prob; }
 		  };
 		  /// \brief Interface for the CPLEX LP solver
 		  ///
 		  /// This class implements an interface for the CPLEX LP solver.
 		  ///\ingroup lp_group
 		  class CplexLp : public LpSolver, public CplexBase {
 		  public:
 		    /// \e
 		    CplexLp();
 		    /// \e
 		    CplexLp(const CplexEnv&);
 		    /// \e
 		    CplexLp(const CplexLp&);
 		    /// \e
 		    virtual ~CplexLp();
 		    /// \e
 		    virtual CplexLp* cloneSolver() const;
 		    /// \e
 		    virtual CplexLp* newSolver() const;
 		  private:
 		    // these values cannot retrieved element by element
 		    mutable std::vector<int> _col_status;
 		    mutable std::vector<int> _row_status;
 		    mutable std::vector<Value> _primal_ray;
 		    mutable std::vector<Value> _dual_ray;
 		    void _clear_temporals();
 		    SolveExitStatus convertStatus(int status);
 		  protected:
 		    virtual const char* _solverName() const;
 		    virtual SolveExitStatus _solve();
 		    virtual Value _getPrimal(int i) const;
 		    virtual Value _getDual(int i) const;
 		    virtual Value _getPrimalValue() const;
 		    virtual VarStatus _getColStatus(int i) const;
 		    virtual VarStatus _getRowStatus(int i) const;
 		    virtual Value _getPrimalRay(int i) const;
 		    virtual Value _getDualRay(int i) const;
 		    virtual ProblemType _getPrimalType() const;
 		    virtual ProblemType _getDualType() const;
 		  public:
 		    /// Solve with primal simplex method
 		    SolveExitStatus solvePrimal();
 		    /// Solve with dual simplex method
 		    SolveExitStatus solveDual();
 		    /// Solve with barrier method
 		    SolveExitStatus solveBarrier();
 		  };
 		  /// \brief Interface for the CPLEX MIP solver
 		  ///
 		  /// This class implements an interface for the CPLEX MIP solver.
 		  ///\ingroup lp_group
 		  class CplexMip : public MipSolver, public CplexBase {
 		  public:
 		    /// \e
 		    CplexMip();
 		    /// \e
 		    CplexMip(const CplexEnv&);
 		    /// \e
 		    CplexMip(const CplexMip&);
 		    /// \e
 		    virtual ~CplexMip();
 		    /// \e
 		    virtual CplexMip* cloneSolver() const;
 		    /// \e
 		    virtual CplexMip* newSolver() const;
 		  protected:
 		    virtual const char* _solverName() 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;
 		  };
 		} //END OF NAMESPACE LEMON
 		#endif //LEMON_CPLEX_H

lemon/glpk.cc

Show inline comments

 		/* -*- 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 LEMON GLPK LP and MIP solver interface.
 		#include <lemon/glpk.h>
 		#include <glpk.h>
 		#include <lemon/assert.h>
 		namespace lemon {
 		  // GlpkBase members
 		  GlpkBase::GlpkBase() : LpBase() {
 		    lp = glp_create_prob();
 		    glp_create_index(lp);
 		    messageLevel(MESSAGE_NOTHING);
+		  }
 		  GlpkBase::GlpkBase(const GlpkBase &other) : LpBase() {
 		    lp = glp_create_prob();
 		    glp_copy_prob(lp, other.lp, GLP_ON);
 		    glp_create_index(lp);
 		    rows = other.rows;
 		    cols = other.cols;
 		    messageLevel(MESSAGE_NOTHING);
+		  }
 		  GlpkBase::~GlpkBase() {
 		    glp_delete_prob(lp);
+		  }
 		  int GlpkBase::_addCol() {
 		    int i = glp_add_cols(lp, 1);
 		    glp_set_col_bnds(lp, i, GLP_FR, 0.0, 0.0);
 		    return i;
+		  }
 		  int GlpkBase::_addRow() {
 		    int i = glp_add_rows(lp, 1);
 		    glp_set_row_bnds(lp, i, GLP_FR, 0.0, 0.0);
 		    return i;
+		  }
 		  int GlpkBase::_addRow(Value lo, ExprIterator b,
 		                        ExprIterator e, Value up) {
 		    int i = glp_add_rows(lp, 1);
 		    if (lo == -INF) {
 		      if (up == INF) {
 		        glp_set_row_bnds(lp, i, GLP_FR, lo, up);
 		      } else {
 		        glp_set_row_bnds(lp, i, GLP_UP, lo, up);
+		      }
 		    } else {
 		      if (up == INF) {
 		        glp_set_row_bnds(lp, i, GLP_LO, lo, up);
 		      } else if (lo != up) {
 		        glp_set_row_bnds(lp, i, GLP_DB, lo, up);
 		      } else {
 		        glp_set_row_bnds(lp, i, GLP_FX, lo, up);
+		      }
+		    }
 		    std::vector<int> indexes;
 		    std::vector<Value> values;
 		    indexes.push_back(0);
 		    values.push_back(0);
 		    for(ExprIterator it = b; it != e; ++it) {
 		      indexes.push_back(it->first);
 		      values.push_back(it->second);
+		    }
 		    glp_set_mat_row(lp, i, values.size() - 1,
 		                    &indexes.front(), &values.front());
 		    return i;
+		  }
 		  void GlpkBase::_eraseCol(int i) {
 		    int ca[2];
 		    ca[1] = i;
 		    glp_del_cols(lp, 1, ca);
+		  }
 		  void GlpkBase::_eraseRow(int i) {
 		    int ra[2];
 		    ra[1] = i;
 		    glp_del_rows(lp, 1, ra);
+		  }
 		  void GlpkBase::_eraseColId(int i) {
 		    cols.eraseIndex(i);
 		    cols.shiftIndices(i);
+		  }
 		  void GlpkBase::_eraseRowId(int i) {
 		    rows.eraseIndex(i);
 		    rows.shiftIndices(i);
+		  }
 		  void GlpkBase::_getColName(int c, std::string& name) const {
 		    const char *str = glp_get_col_name(lp, c);
 		    if (str) name = str;
 		    else name.clear();
+		  }
 		  void GlpkBase::_setColName(int c, const std::string & name) {
 		    glp_set_col_name(lp, c, const_cast<char*>(name.c_str()));
+		  }
 		  int GlpkBase::_colByName(const std::string& name) const {
 		    int k = glp_find_col(lp, const_cast<char*>(name.c_str()));
 		    return k > 0 ? k : -1;
+		  }
 		  void GlpkBase::_getRowName(int r, std::string& name) const {
 		    const char *str = glp_get_row_name(lp, r);
 		    if (str) name = str;
 		    else name.clear();
+		  }
 		  void GlpkBase::_setRowName(int r, const std::string & name) {
 		    glp_set_row_name(lp, r, const_cast<char*>(name.c_str()));
+		  }
 		  int GlpkBase::_rowByName(const std::string& name) const {
 		    int k = glp_find_row(lp, const_cast<char*>(name.c_str()));
 		    return k > 0 ? k : -1;
+		  }
 		  void GlpkBase::_setRowCoeffs(int i, ExprIterator b, ExprIterator e) {
 		    std::vector<int> indexes;
 		    std::vector<Value> values;
 		    indexes.push_back(0);
 		    values.push_back(0);
 		    for(ExprIterator it = b; it != e; ++it) {
 		      indexes.push_back(it->first);
 		      values.push_back(it->second);
+		    }
 		    glp_set_mat_row(lp, i, values.size() - 1,
 		                    &indexes.front(), &values.front());
+		  }
 		  void GlpkBase::_getRowCoeffs(int ix, InsertIterator b) const {
 		    int length = glp_get_mat_row(lp, ix, 0, 0);
 		    std::vector<int> indexes(length + 1);
 		    std::vector<Value> values(length + 1);
 		    glp_get_mat_row(lp, ix, &indexes.front(), &values.front());
 		    for (int i = 1; i <= length; ++i) {
 		      *b = std::make_pair(indexes[i], values[i]);
 		      ++b;
+		    }
+		  }
 		  void GlpkBase::_setColCoeffs(int ix, ExprIterator b,
 		                                     ExprIterator e) {
 		    std::vector<int> indexes;
 		    std::vector<Value> values;
 		    indexes.push_back(0);
 		    values.push_back(0);
 		    for(ExprIterator it = b; it != e; ++it) {
 		      indexes.push_back(it->first);
 		      values.push_back(it->second);
+		    }
 		    glp_set_mat_col(lp, ix, values.size() - 1,
 		                    &indexes.front(), &values.front());
+		  }
 		  void GlpkBase::_getColCoeffs(int ix, InsertIterator b) const {
 		    int length = glp_get_mat_col(lp, ix, 0, 0);
 		    std::vector<int> indexes(length + 1);
 		    std::vector<Value> values(length + 1);
 		    glp_get_mat_col(lp, ix, &indexes.front(), &values.front());
 		    for (int i = 1; i  <= length; ++i) {
 		      *b = std::make_pair(indexes[i], values[i]);
 		      ++b;
+		    }
+		  }
 		  void GlpkBase::_setCoeff(int ix, int jx, Value value) {
 		    if (glp_get_num_cols(lp) < glp_get_num_rows(lp)) {
 		      int length = glp_get_mat_row(lp, ix, 0, 0);
 		      std::vector<int> indexes(length + 2);
 		      std::vector<Value> values(length + 2);
 		      glp_get_mat_row(lp, ix, &indexes.front(), &values.front());
 		      //The following code does not suppose that the elements of the
 		      //array indexes are sorted
 		      bool found = false;
 		      for (int i = 1; i  <= length; ++i) {
 		        if (indexes[i] == jx) {
 		          found = true;
 		          values[i] = value;
 		          break;
+		        }
+		      }
 		      if (!found) {
 		        ++length;
 		        indexes[length] = jx;
 		        values[length] = value;
+		      }
 		      glp_set_mat_row(lp, ix, length, &indexes.front(), &values.front());
 		    } else {
 		      int length = glp_get_mat_col(lp, jx, 0, 0);
 		      std::vector<int> indexes(length + 2);
 		      std::vector<Value> values(length + 2);
 		      glp_get_mat_col(lp, jx, &indexes.front(), &values.front());
 		      //The following code does not suppose that the elements of the
 		      //array indexes are sorted
 		      bool found = false;
 		      for (int i = 1; i <= length; ++i) {
 		        if (indexes[i] == ix) {
 		          found = true;
 		          values[i] = value;
 		          break;
+		        }
+		      }
 		      if (!found) {
 		        ++length;
 		        indexes[length] = ix;
 		        values[length] = value;
+		      }
 		      glp_set_mat_col(lp, jx, length, &indexes.front(), &values.front());
+		    }
+		  }
 		  GlpkBase::Value GlpkBase::_getCoeff(int ix, int jx) const {
 		    int length = glp_get_mat_row(lp, ix, 0, 0);
 		    std::vector<int> indexes(length + 1);
 		    std::vector<Value> values(length + 1);
 		    glp_get_mat_row(lp, ix, &indexes.front(), &values.front());
 		    for (int i = 1; i  <= length; ++i) {
 		      if (indexes[i] == jx) {
 		        return values[i];
+		      }
+		    }
 		    return 0;
+		  }
 		  void GlpkBase::_setColLowerBound(int i, Value lo) {
 		    LEMON_ASSERT(lo != INF, "Invalid bound");
 		    int b = glp_get_col_type(lp, i);
 		    double up = glp_get_col_ub(lp, i);
 		    if (lo == -INF) {
 		      switch (b) {
 		      case GLP_FR:
 		      case GLP_LO:
 		        glp_set_col_bnds(lp, i, GLP_FR, lo, up);
 		        break;
 		      case GLP_UP:
 		        break;
 		      case GLP_DB:
 		      case GLP_FX:
 		        glp_set_col_bnds(lp, i, GLP_UP, lo, up);
 		        break;
 		      default:
 		        break;
+		      }
 		    } else {
 		      switch (b) {
 		      case GLP_FR:
 		      case GLP_LO:
 		        glp_set_col_bnds(lp, i, GLP_LO, lo, up);
 		        break;
 		      case GLP_UP:
 		      case GLP_DB:
 		      case GLP_FX:
 		        if (lo == up)
 		          glp_set_col_bnds(lp, i, GLP_FX, lo, up);
 		        else
 		          glp_set_col_bnds(lp, i, GLP_DB, lo, up);
 		        break;
 		      default:
 		        break;
+		      }
+		    }
+		  }
 		  GlpkBase::Value GlpkBase::_getColLowerBound(int i) const {
 		    int b = glp_get_col_type(lp, i);
 		    switch (b) {
 		    case GLP_LO:
 		    case GLP_DB:
 		    case GLP_FX:
 		      return glp_get_col_lb(lp, i);
 		    default:
 		      return -INF;
+		    }
+		  }
 		  void GlpkBase::_setColUpperBound(int i, Value up) {
 		    LEMON_ASSERT(up != -INF, "Invalid bound");
 		    int b = glp_get_col_type(lp, i);
 		    double lo = glp_get_col_lb(lp, i);
 		    if (up == INF) {
 		      switch (b) {
 		      case GLP_FR:
 		      case GLP_LO:
 		        break;
 		      case GLP_UP:
 		        glp_set_col_bnds(lp, i, GLP_FR, lo, up);
 		        break;
 		      case GLP_DB:
 		      case GLP_FX:
 		        glp_set_col_bnds(lp, i, GLP_LO, lo, up);
 		        break;
 		      default:
 		        break;
+		      }
 		    } else {
 		      switch (b) {
 		      case GLP_FR:
 		        glp_set_col_bnds(lp, i, GLP_UP, lo, up);
 		        break;
 		      case GLP_UP:
 		        glp_set_col_bnds(lp, i, GLP_UP, lo, up);
 		        break;
 		      case GLP_LO:
 		      case GLP_DB:
 		      case GLP_FX:
 		        if (lo == up)
 		          glp_set_col_bnds(lp, i, GLP_FX, lo, up);
 		        else
 		          glp_set_col_bnds(lp, i, GLP_DB, lo, up);
 		        break;
 		      default:
 		        break;
+		      }
+		    }
+		  }
 		  GlpkBase::Value GlpkBase::_getColUpperBound(int i) const {
 		    int b = glp_get_col_type(lp, i);
 		      switch (b) {
 		      case GLP_UP:
 		      case GLP_DB:
 		      case GLP_FX:
 		        return glp_get_col_ub(lp, i);
 		      default:
 		        return INF;
+		      }
+		  }
 		  void GlpkBase::_setRowLowerBound(int i, Value lo) {
 		    LEMON_ASSERT(lo != INF, "Invalid bound");
 		    int b = glp_get_row_type(lp, i);
 		    double up = glp_get_row_ub(lp, i);
 		    if (lo == -INF) {
 		      switch (b) {
 		      case GLP_FR:
 		      case GLP_LO:
 		        glp_set_row_bnds(lp, i, GLP_FR, lo, up);
 		        break;
 		      case GLP_UP:
 		        break;
 		      case GLP_DB:
 		      case GLP_FX:
 		        glp_set_row_bnds(lp, i, GLP_UP, lo, up);
 		        break;
 		      default:
 		        break;
+		      }
 		    } else {
 		      switch (b) {
 		      case GLP_FR:
 		      case GLP_LO:
 		        glp_set_row_bnds(lp, i, GLP_LO, lo, up);
 		        break;
 		      case GLP_UP:
 		      case GLP_DB:
 		      case GLP_FX:
 		        if (lo == up)
 		          glp_set_row_bnds(lp, i, GLP_FX, lo, up);
 		        else
 		          glp_set_row_bnds(lp, i, GLP_DB, lo, up);
 		        break;
 		      default:
 		        break;
+		      }
+		    }
+		  }
 		  GlpkBase::Value GlpkBase::_getRowLowerBound(int i) const {
 		    int b = glp_get_row_type(lp, i);
 		    switch (b) {
 		    case GLP_LO:
 		    case GLP_DB:
 		    case GLP_FX:
 		      return glp_get_row_lb(lp, i);
 		    default:
 		      return -INF;
+		    }
+		  }
 		  void GlpkBase::_setRowUpperBound(int i, Value up) {
 		    LEMON_ASSERT(up != -INF, "Invalid bound");
 		    int b = glp_get_row_type(lp, i);
 		    double lo = glp_get_row_lb(lp, i);
 		    if (up == INF) {
 		      switch (b) {
 		      case GLP_FR:
 		      case GLP_LO:
 		        break;
 		      case GLP_UP:
 		        glp_set_row_bnds(lp, i, GLP_FR, lo, up);
 		        break;
 		      case GLP_DB:
 		      case GLP_FX:
 		        glp_set_row_bnds(lp, i, GLP_LO, lo, up);
 		        break;
 		      default:
 		        break;
+		      }
 		    } else {
 		      switch (b) {
 		      case GLP_FR:
 		        glp_set_row_bnds(lp, i, GLP_UP, lo, up);
 		        break;
 		      case GLP_UP:
 		        glp_set_row_bnds(lp, i, GLP_UP, lo, up);
 		        break;
 		      case GLP_LO:
 		      case GLP_DB:
 		      case GLP_FX:
 		        if (lo == up)
 		          glp_set_row_bnds(lp, i, GLP_FX, lo, up);
 		        else
 		          glp_set_row_bnds(lp, i, GLP_DB, lo, up);
 		        break;
 		      default:
 		        break;
+		      }
+		    }
+		  }
 		  GlpkBase::Value GlpkBase::_getRowUpperBound(int i) const {
 		    int b = glp_get_row_type(lp, i);
 		    switch (b) {
 		    case GLP_UP:
 		    case GLP_DB:
 		    case GLP_FX:
 		      return glp_get_row_ub(lp, i);
 		    default:
 		      return INF;
+		    }
+		  }
 		  void GlpkBase::_setObjCoeffs(ExprIterator b, ExprIterator e) {
 		    for (int i = 1; i <= glp_get_num_cols(lp); ++i) {
 		      glp_set_obj_coef(lp, i, 0.0);
+		    }
 		    for (ExprIterator it = b; it != e; ++it) {
 		      glp_set_obj_coef(lp, it->first, it->second);
+		    }
+		  }
 		  void GlpkBase::_getObjCoeffs(InsertIterator b) const {
 		    for (int i = 1; i <= glp_get_num_cols(lp); ++i) {
 		      Value val = glp_get_obj_coef(lp, i);
 		      if (val != 0.0) {
 		        *b = std::make_pair(i, val);
 		        ++b;
+		      }
+		    }
+		  }
 		  void GlpkBase::_setObjCoeff(int i, Value obj_coef) {
 		    //i = 0 means the constant term (shift)
 		    glp_set_obj_coef(lp, i, obj_coef);
+		  }
 		  GlpkBase::Value GlpkBase::_getObjCoeff(int i) const {
 		    //i = 0 means the constant term (shift)
 		    return glp_get_obj_coef(lp, i);
+		  }
 		  void GlpkBase::_setSense(GlpkBase::Sense sense) {
 		    switch (sense) {
 		    case MIN:
 		      glp_set_obj_dir(lp, GLP_MIN);
 		      break;
 		    case MAX:
 		      glp_set_obj_dir(lp, GLP_MAX);
 		      break;
+		    }
+		  }
 		  GlpkBase::Sense GlpkBase::_getSense() const {
 		    switch(glp_get_obj_dir(lp)) {
 		    case GLP_MIN:
 		      return MIN;
 		    case GLP_MAX:
 		      return MAX;
 		    default:
 		      LEMON_ASSERT(false, "Wrong sense");
 		      return GlpkBase::Sense();
+		    }
+		  }
 		  void GlpkBase::_clear() {
 		    glp_erase_prob(lp);
 		    rows.clear();
 		    cols.clear();
+		  }
 		  void GlpkBase::freeEnv() {
 		    glp_free_env();
+		  }
 		  void GlpkBase::_messageLevel(MessageLevel level) {
 		    switch (level) {
 		    case MESSAGE_NOTHING:
 		      _message_level = GLP_MSG_OFF;
 		      break;
 		    case MESSAGE_ERROR:
 		      _message_level = GLP_MSG_ERR;
 		      break;
 		    case MESSAGE_WARNING:
 		      _message_level = GLP_MSG_ERR;
 		      break;
 		    case MESSAGE_NORMAL:
 		      _message_level = GLP_MSG_ON;
 		      break;
 		    case MESSAGE_VERBOSE:
 		      _message_level = GLP_MSG_ALL;
 		      break;
+		    }
+		  }
 		  GlpkBase::FreeEnvHelper GlpkBase::freeEnvHelper;
 		  // GlpkLp members
 		  GlpkLp::GlpkLp()
 		    : LpBase(), LpSolver(), GlpkBase() {
 		    presolver(false);
+		  }
 		  GlpkLp::GlpkLp(const GlpkLp& other)
 		    : LpBase(other), LpSolver(other), GlpkBase(other) {
 		    presolver(false);
+		  }
 		  GlpkLp* GlpkLp::newSolver() const { return new GlpkLp; }
 		  GlpkLp* GlpkLp::cloneSolver() const { return new GlpkLp(*this); }
 		  const char* GlpkLp::_solverName() const { return "GlpkLp"; }
 		  void GlpkLp::_clear_temporals() {
 		    _primal_ray.clear();
 		    _dual_ray.clear();
+		  }

lemon/glpk.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * 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.
+		 *
 		 */
 		#ifndef LEMON_GLPK_H
 		#define LEMON_GLPK_H
 		///\file
 		///\brief Header of the LEMON-GLPK lp solver interface.
 		///\ingroup lp_group
 		#include <lemon/lp_base.h>
 		// forward declaration
 		#if !defined _GLP_PROB && !defined GLP_PROB
 		#define _GLP_PROB
 		#define GLP_PROB
 		typedef struct { double _opaque_prob; } glp_prob;
 		/* LP/MIP problem object */
 		#endif
 		namespace lemon {
 		  /// \brief Base interface for the GLPK LP and MIP solver
 		  ///
 		  /// This class implements the common interface of the GLPK LP and MIP solver.
 		  /// \ingroup lp_group
 		  class GlpkBase : virtual public LpBase {
 		  protected:
 		    typedef glp_prob LPX;
 		    glp_prob* lp;
 		    GlpkBase();
 		    GlpkBase(const GlpkBase&);
 		    virtual ~GlpkBase();
 		  protected:
 		    virtual int _addCol();
 		    virtual int _addRow();
 		    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
 		    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);
 		    virtual Sense _getSense() const;
 		    virtual void _clear();
 		    virtual void _messageLevel(MessageLevel level);
 		  private:
 		    static void freeEnv();
 		    struct FreeEnvHelper {
 		      ~FreeEnvHelper() {
 		        freeEnv();
+		      }
 		    };
 		    static FreeEnvHelper freeEnvHelper;
 		  protected:
 		    int _message_level;
 		  public:
 		    ///Pointer to the underlying GLPK data structure.
 		    LPX *lpx() {return lp;}
 		    ///Const pointer to the underlying GLPK data structure.
 		    const LPX *lpx() const {return lp;}
 		    ///Returns the constraint identifier understood by GLPK.
 		    int lpxRow(Row r) const { return rows(id(r)); }
 		    ///Returns the variable identifier understood by GLPK.
 		    int lpxCol(Col c) const { return cols(id(c)); }
 		  };
 		  /// \brief Interface for the GLPK LP solver
 		  ///
 		  /// This class implements an interface for the GLPK LP solver.
 		  ///\ingroup lp_group
 		  class GlpkLp : public LpSolver, public GlpkBase {
 		  public:
 		    ///\e
 		    GlpkLp();
 		    ///\e
 		    GlpkLp(const GlpkLp&);
 		    ///\e
 		    virtual GlpkLp* cloneSolver() const;
 		    ///\e
 		    virtual GlpkLp* newSolver() const;
 		  private:
 		    mutable std::vector<double> _primal_ray;
 		    mutable std::vector<double> _dual_ray;
 		    void _clear_temporals();
 		  protected:
 		    virtual const char* _solverName() const;
 		    virtual SolveExitStatus _solve();
 		    virtual Value _getPrimal(int i) const;
 		    virtual Value _getDual(int i) const;
 		    virtual Value _getPrimalValue() const;
 		    virtual VarStatus _getColStatus(int i) const;
 		    virtual VarStatus _getRowStatus(int i) const;
 		    virtual Value _getPrimalRay(int i) const;
 		    virtual Value _getDualRay(int i) const;
 		    virtual ProblemType _getPrimalType() const;
 		    virtual ProblemType _getDualType() const;
 		  public:
 		    ///Solve with primal simplex
 		    SolveExitStatus solvePrimal();
 		    ///Solve with dual simplex
 		    SolveExitStatus solveDual();
 		  private:
 		    bool _presolve;
 		  public:
 		    ///Turns on or off the presolver
 		    ///Turns on (\c b is \c true) or off (\c b is \c false) the presolver
 		    ///
 		    ///The presolver is off by default.
 		    void presolver(bool presolve);
 		  };
 		  /// \brief Interface for the GLPK MIP solver
 		  ///
 		  /// This class implements an interface for the GLPK MIP solver.
 		  ///\ingroup lp_group
 		  class GlpkMip : public MipSolver, public GlpkBase {
 		  public:
 		    ///\e
 		    GlpkMip();
 		    ///\e
 		    GlpkMip(const GlpkMip&);
 		    virtual GlpkMip* cloneSolver() const;
 		    virtual GlpkMip* newSolver() const;
 		  protected:
 		    virtual const char* _solverName() 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;
 		  };
 		} //END OF NAMESPACE LEMON
 		#endif //LEMON_GLPK_H

lemon/lp_base.h

Show inline comments

@@ -434,1300 +434,1314 @@
 		      Expr &operator*=(const Value &v) {
 		        for (std::map<int, Value>::iterator it=comps.begin();
 		             it!=comps.end(); ++it)
 		          it->second*=v;
 		        const_comp*=v;
 		        return *this;
+		      }
 		      ///Division with a constant
 		      Expr &operator/=(const Value &c) {
 		        for (std::map<int, Value>::iterator it=comps.begin();
 		             it!=comps.end(); ++it)
 		          it->second/=c;
 		        const_comp/=c;
 		        return *this;
+		      }
 		      ///Iterator over the expression
 		      ///The iterator iterates over the terms of the expression.
 		      ///
 		      ///\code
 		      ///double s=0;
 		      ///for(LpBase::Expr::CoeffIt i(e);i!=INVALID;++i)
 		      ///  s+= *i * primal(i);
 		      ///\endcode
 		      class CoeffIt {
 		      private:
 		        std::map<int, Value>::iterator _it, _end;
 		      public:
 		        /// Sets the iterator to the first term
 		        /// Sets the iterator to the first term of the expression.
 		        ///
 		        CoeffIt(Expr& e)
 		          : _it(e.comps.begin()), _end(e.comps.end()){}
 		        /// Convert the iterator to the column of the term
 		        operator Col() const {
 		          return colFromId(_it->first);
+		        }
 		        /// Returns the coefficient of the term
 		        Value& operator*() { return _it->second; }
 		        /// Returns the coefficient of the term
 		        const Value& operator*() const { return _it->second; }
 		        /// Next term
 		        /// Assign the iterator to the next term.
 		        ///
 		        CoeffIt& operator++() { ++_it; return *this; }
 		        /// Equality operator
 		        bool operator==(Invalid) const { return _it == _end; }
 		        /// Inequality operator
 		        bool operator!=(Invalid) const { return _it != _end; }
 		      };
 		      /// Const iterator over the expression
 		      ///The iterator iterates over the terms of the expression.
 		      ///
 		      ///\code
 		      ///double s=0;
 		      ///for(LpBase::Expr::ConstCoeffIt i(e);i!=INVALID;++i)
 		      ///  s+=*i * primal(i);
 		      ///\endcode
 		      class ConstCoeffIt {
 		      private:
 		        std::map<int, Value>::const_iterator _it, _end;
 		      public:
 		        /// Sets the iterator to the first term
 		        /// Sets the iterator to the first term of the expression.
 		        ///
 		        ConstCoeffIt(const Expr& e)
 		          : _it(e.comps.begin()), _end(e.comps.end()){}
 		        /// Convert the iterator to the column of the term
 		        operator Col() const {
 		          return colFromId(_it->first);
+		        }
 		        /// Returns the coefficient of the term
 		        const Value& operator*() const { return _it->second; }
 		        /// Next term
 		        /// Assign the iterator to the next term.
 		        ///
 		        ConstCoeffIt& operator++() { ++_it; return *this; }
 		        /// Equality operator
 		        bool operator==(Invalid) const { return _it == _end; }
 		        /// Inequality operator
 		        bool operator!=(Invalid) const { return _it != _end; }
 		      };
 		    };
 		    ///Linear constraint
 		    ///This data stucture represents a linear constraint in the LP.
 		    ///Basically it is a linear expression with a lower or an upper bound
 		    ///(or both). These parts of the constraint can be obtained by the member
 		    ///functions \ref expr(), \ref lowerBound() and \ref upperBound(),
 		    ///respectively.
 		    ///There are two ways to construct a constraint.
 		    ///- You can set the linear expression and the bounds directly
 		    ///  by the functions above.
 		    ///- The operators <tt>\<=</tt>, <tt>==</tt> and  <tt>\>=</tt>
 		    ///  are defined between expressions, or even between constraints whenever
 		    ///  it makes sense. Therefore if \c e and \c f are linear expressions and
 		    ///  \c s and \c t are numbers, then the followings are valid expressions
 		    ///  and thus they can be used directly e.g. in \ref addRow() whenever
 		    ///  it makes sense.
 		    ///\code
 		    ///  e<=s
 		    ///  e<=f
 		    ///  e==f
 		    ///  s<=e<=t
 		    ///  e>=t
 		    ///\endcode
 		    ///\warning The validity of a constraint is checked only at run
 		    ///time, so e.g. \ref addRow(<tt>x[1]\<=x[2]<=5</tt>) will
 		    ///compile, but will fail an assertion.
 		    class Constr
+		    {
 		    public:
 		      typedef LpBase::Expr Expr;
 		      typedef Expr::Key Key;
 		      typedef Expr::Value Value;
 		    protected:
 		      Expr _expr;
 		      Value _lb,_ub;
 		    public:
 		      ///\e
 		      Constr() : _expr(), _lb(NaN), _ub(NaN) {}
 		      ///\e
 		      Constr(Value lb, const Expr &e, Value ub) :
 		        _expr(e), _lb(lb), _ub(ub) {}
 		      Constr(const Expr &e) :
 		        _expr(e), _lb(NaN), _ub(NaN) {}
 		      ///\e
 		      void clear()
+		      {
 		        _expr.clear();
 		        _lb=_ub=NaN;
+		      }
 		      ///Reference to the linear expression
 		      Expr &expr() { return _expr; }
 		      ///Cont reference to the linear expression
 		      const Expr &expr() const { return _expr; }
 		      ///Reference to the lower bound.
 		      ///\return
 		      ///- \ref INF "INF": the constraint is lower unbounded.
 		      ///- \ref NaN "NaN": lower bound has not been set.
 		      ///- finite number: the lower bound
 		      Value &lowerBound() { return _lb; }
 		      ///The const version of \ref lowerBound()
 		      const Value &lowerBound() const { return _lb; }
 		      ///Reference to the upper bound.
 		      ///\return
 		      ///- \ref INF "INF": the constraint is upper unbounded.
 		      ///- \ref NaN "NaN": upper bound has not been set.
 		      ///- finite number: the upper bound
 		      Value &upperBound() { return _ub; }
 		      ///The const version of \ref upperBound()
 		      const Value &upperBound() const { return _ub; }
 		      ///Is the constraint lower bounded?
 		      bool lowerBounded() const {
 		        return _lb != -INF && !isNaN(_lb);
+		      }
 		      ///Is the constraint upper bounded?
 		      bool upperBounded() const {
 		        return _ub != INF && !isNaN(_ub);
+		      }
 		    };
 		    ///Linear expression of rows
 		    ///This data structure represents a column of the matrix,
 		    ///thas is it strores a linear expression of the dual variables
 		    ///(\ref Row "Row"s).
 		    ///
 		    ///There are several ways to access and modify the contents of this
 		    ///container.
 		    ///\code
 		    ///e[v]=5;
 		    ///e[v]+=12;
 		    ///e.erase(v);
 		    ///\endcode
 		    ///or you can also iterate through its elements.
 		    ///\code
 		    ///double s=0;
 		    ///for(LpBase::DualExpr::ConstCoeffIt i(e);i!=INVALID;++i)
 		    ///  s+=*i;
 		    ///\endcode
 		    ///(This code computes the sum of all coefficients).
 		    ///- Numbers (<tt>double</tt>'s)
 		    ///and variables (\ref Row "Row"s) directly convert to an
 		    ///\ref DualExpr and the usual linear operations are defined, so
 		    ///\code
 		    ///v+w
 		    ///2*v-3.12*(v-w/2)
 		    ///v*2.1+(3*v+(v*12+w)*3)/2
 		    ///\endcode
 		    ///are valid \ref DualExpr dual expressions.
 		    ///The usual assignment operations are also defined.
 		    ///\code
 		    ///e=v+w;
 		    ///e+=2*v-3.12*(v-w/2);
 		    ///e*=3.4;
 		    ///e/=5;
 		    ///\endcode
 		    ///
 		    ///\sa Expr
 		    class DualExpr {
 		      friend class LpBase;
 		    public:
 		      /// The key type of the expression
 		      typedef LpBase::Row Key;
 		      /// The value type of the expression
 		      typedef LpBase::Value Value;
 		    protected:
 		      std::map<int, Value> comps;
 		    public:
 		      typedef True SolverExpr;
 		      /// Default constructor
 		      /// Construct an empty expression, the coefficients are
 		      /// initialized to zero.
 		      DualExpr() {}
 		      /// Construct an expression from a row
 		      /// Construct an expression, which has a term with \c r dual
 		      /// variable and 1.0 coefficient.
 		      DualExpr(const Row &r) {
 		        typedef std::map<int, Value>::value_type pair_type;
 		        comps.insert(pair_type(id(r), 1));
+		      }
 		      /// Returns the coefficient of the row
 		      Value operator[](const Row& r) const {
 		        std::map<int, Value>::const_iterator it = comps.find(id(r));
 		        if (it != comps.end()) {
 		          return it->second;
 		        } else {
 		          return 0;
+		        }
+		      }
 		      /// Returns the coefficient of the row
 		      Value& operator[](const Row& r) {
 		        return comps[id(r)];
+		      }
 		      /// Sets the coefficient of the row
 		      void set(const Row &r, const Value &v) {
 		        if (v != 0.0) {
 		          typedef std::map<int, Value>::value_type pair_type;
 		          comps.insert(pair_type(id(r), v));
 		        } else {
 		          comps.erase(id(r));
+		        }
+		      }
 		      /// \brief Removes the coefficients which's absolute value does
 		      /// not exceed \c epsilon.
 		      void simplify(Value epsilon = 0.0) {
 		        std::map<int, Value>::iterator it=comps.begin();
 		        while (it != comps.end()) {
 		          std::map<int, Value>::iterator jt=it;
 		          ++jt;
 		          if (std::fabs((*it).second) <= epsilon) comps.erase(it);
 		          it=jt;
+		        }
+		      }
 		      void simplify(Value epsilon = 0.0) const {
 		        const_cast<DualExpr*>(this)->simplify(epsilon);
+		      }
 		      ///Sets all coefficients to 0.
 		      void clear() {
 		        comps.clear();
+		      }
 		      ///Compound assignment
 		      DualExpr &operator+=(const DualExpr &e) {
 		        for (std::map<int, Value>::const_iterator it=e.comps.begin();
 		             it!=e.comps.end(); ++it)
 		          comps[it->first]+=it->second;
 		        return *this;
+		      }
 		      ///Compound assignment
 		      DualExpr &operator-=(const DualExpr &e) {
 		        for (std::map<int, Value>::const_iterator it=e.comps.begin();
 		             it!=e.comps.end(); ++it)
 		          comps[it->first]-=it->second;
 		        return *this;
+		      }
 		      ///Multiply with a constant
 		      DualExpr &operator*=(const Value &v) {
 		        for (std::map<int, Value>::iterator it=comps.begin();
 		             it!=comps.end(); ++it)
 		          it->second*=v;
 		        return *this;
+		      }
 		      ///Division with a constant
 		      DualExpr &operator/=(const Value &v) {
 		        for (std::map<int, Value>::iterator it=comps.begin();
 		             it!=comps.end(); ++it)
 		          it->second/=v;
 		        return *this;
+		      }
 		      ///Iterator over the expression
 		      ///The iterator iterates over the terms of the expression.
 		      ///
 		      ///\code
 		      ///double s=0;
 		      ///for(LpBase::DualExpr::CoeffIt i(e);i!=INVALID;++i)
 		      ///  s+= *i * dual(i);
 		      ///\endcode
 		      class CoeffIt {
 		      private:
 		        std::map<int, Value>::iterator _it, _end;
 		      public:
 		        /// Sets the iterator to the first term
 		        /// Sets the iterator to the first term of the expression.
 		        ///
 		        CoeffIt(DualExpr& e)
 		          : _it(e.comps.begin()), _end(e.comps.end()){}
 		        /// Convert the iterator to the row of the term
 		        operator Row() const {
 		          return rowFromId(_it->first);
+		        }
 		        /// Returns the coefficient of the term
 		        Value& operator*() { return _it->second; }
 		        /// Returns the coefficient of the term
 		        const Value& operator*() const { return _it->second; }
 		        /// Next term
 		        /// Assign the iterator to the next term.
 		        ///
 		        CoeffIt& operator++() { ++_it; return *this; }
 		        /// Equality operator
 		        bool operator==(Invalid) const { return _it == _end; }
 		        /// Inequality operator
 		        bool operator!=(Invalid) const { return _it != _end; }
 		      };
 		      ///Iterator over the expression
 		      ///The iterator iterates over the terms of the expression.
 		      ///
 		      ///\code
 		      ///double s=0;
 		      ///for(LpBase::DualExpr::ConstCoeffIt i(e);i!=INVALID;++i)
 		      ///  s+= *i * dual(i);
 		      ///\endcode
 		      class ConstCoeffIt {
 		      private:
 		        std::map<int, Value>::const_iterator _it, _end;
 		      public:
 		        /// Sets the iterator to the first term
 		        /// Sets the iterator to the first term of the expression.
 		        ///
 		        ConstCoeffIt(const DualExpr& e)
 		          : _it(e.comps.begin()), _end(e.comps.end()){}
 		        /// Convert the iterator to the row of the term
 		        operator Row() const {
 		          return rowFromId(_it->first);
+		        }
 		        /// Returns the coefficient of the term
 		        const Value& operator*() const { return _it->second; }
 		        /// Next term
 		        /// Assign the iterator to the next term.
 		        ///
 		        ConstCoeffIt& operator++() { ++_it; return *this; }
 		        /// Equality operator
 		        bool operator==(Invalid) const { return _it == _end; }
 		        /// Inequality operator
 		        bool operator!=(Invalid) const { return _it != _end; }
 		      };
 		    };
 		  protected:
 		    class InsertIterator {
 		    private:
 		      std::map<int, Value>& _host;
 		      const _solver_bits::VarIndex& _index;
 		    public:
 		      typedef std::output_iterator_tag iterator_category;
 		      typedef void difference_type;
 		      typedef void value_type;
 		      typedef void reference;
 		      typedef void pointer;
 		      InsertIterator(std::map<int, Value>& host,
 		                   const _solver_bits::VarIndex& index)
 		        : _host(host), _index(index) {}
 		      InsertIterator& operator=(const std::pair<int, Value>& value) {
 		        typedef std::map<int, Value>::value_type pair_type;
 		        _host.insert(pair_type(_index[value.first], value.second));
 		        return *this;
+		      }
 		      InsertIterator& operator*() { return *this; }
 		      InsertIterator& operator++() { return *this; }
 		      InsertIterator operator++(int) { return *this; }
 		    };
 		    class ExprIterator {
 		    private:
 		      std::map<int, Value>::const_iterator _host_it;
 		      const _solver_bits::VarIndex& _index;
 		    public:
 		      typedef std::bidirectional_iterator_tag iterator_category;
 		      typedef std::ptrdiff_t difference_type;
 		      typedef const std::pair<int, Value> value_type;
 		      typedef value_type reference;
 		      class pointer {
 		      public:
 		        pointer(value_type& _value) : value(_value) {}
 		        value_type* operator->() { return &value; }
 		      private:
 		        value_type value;
 		      };
 		      ExprIterator(const std::map<int, Value>::const_iterator& host_it,
 		                   const _solver_bits::VarIndex& index)
 		        : _host_it(host_it), _index(index) {}
 		      reference operator*() {
 		        return std::make_pair(_index(_host_it->first), _host_it->second);
+		      }
 		      pointer operator->() {
 		        return pointer(operator*());
+		      }
 		      ExprIterator& operator++() { ++_host_it; return *this; }
 		      ExprIterator operator++(int) {
 		        ExprIterator tmp(*this); ++_host_it; return tmp;
+		      }
 		      ExprIterator& operator--() { --_host_it; return *this; }
 		      ExprIterator operator--(int) {
 		        ExprIterator tmp(*this); --_host_it; return tmp;
+		      }
 		      bool operator==(const ExprIterator& it) const {
 		        return _host_it == it._host_it;
+		      }
 		      bool operator!=(const ExprIterator& it) const {
 		        return _host_it != it._host_it;
+		      }
 		    };
 		  protected:
 		    //Abstract virtual functions
 		    virtual int _addColId(int col) { return cols.addIndex(col); }
 		    virtual int _addRowId(int row) { return rows.addIndex(row); }
 		    virtual void _eraseColId(int col) { cols.eraseIndex(col); }
 		    virtual void _eraseRowId(int row) { rows.eraseIndex(row); }
 		    virtual int _addCol() = 0;
 		    virtual int _addRow() = 0;
 		    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
 		      int row = _addRow();
 		      _setRowCoeffs(row, b, e);
 		      _setRowLowerBound(row, l);
 		      _setRowUpperBound(row, u);
 		      return row;
+		    }
 		    virtual void _eraseCol(int col) = 0;
 		    virtual void _eraseRow(int row) = 0;
 		    virtual void _getColName(int col, std::string& name) const = 0;
 		    virtual void _setColName(int col, const std::string& name) = 0;
 		    virtual int _colByName(const std::string& name) const = 0;
 		    virtual void _getRowName(int row, std::string& name) const = 0;
 		    virtual void _setRowName(int row, const std::string& name) = 0;
 		    virtual int _rowByName(const std::string& name) const = 0;
 		    virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e) = 0;
 		    virtual void _getRowCoeffs(int i, InsertIterator b) const = 0;
 		    virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e) = 0;
 		    virtual void _getColCoeffs(int i, InsertIterator b) const = 0;
 		    virtual void _setCoeff(int row, int col, Value value) = 0;
 		    virtual Value _getCoeff(int row, int col) const = 0;
 		    virtual void _setColLowerBound(int i, Value value) = 0;
 		    virtual Value _getColLowerBound(int i) const = 0;
 		    virtual void _setColUpperBound(int i, Value value) = 0;
 		    virtual Value _getColUpperBound(int i) const = 0;
 		    virtual void _setRowLowerBound(int i, Value value) = 0;
 		    virtual Value _getRowLowerBound(int i) const = 0;
 		    virtual void _setRowUpperBound(int i, Value value) = 0;
 		    virtual Value _getRowUpperBound(int i) const = 0;
 		    virtual void _setObjCoeffs(ExprIterator b, ExprIterator e) = 0;
 		    virtual void _getObjCoeffs(InsertIterator b) const = 0;
 		    virtual void _setObjCoeff(int i, Value obj_coef) = 0;
 		    virtual Value _getObjCoeff(int i) const = 0;
 		    virtual void _setSense(Sense) = 0;
 		    virtual Sense _getSense() const = 0;
 		    virtual void _clear() = 0;
 		    virtual const char* _solverName() const = 0;
 		    virtual void _messageLevel(MessageLevel level) = 0;
 		    //Own protected stuff
 		    //Constant component of the objective function
 		    Value obj_const_comp;
 		    LpBase() : rows(), cols(), obj_const_comp(0) {}
 		  public:
 		    /// Virtual destructor
 		    virtual ~LpBase() {}
 		    ///Gives back the name of the solver.
 		    const char* solverName() const {return _solverName();}
 		    ///\name Build Up and Modify the LP
 		    ///@{
 		    ///Add a new empty column (i.e a new variable) to the LP
 		    Col addCol() { Col c; c._id = _addColId(_addCol()); return c;}
 		    ///\brief Adds several new columns (i.e variables) at once
 		    ///
 		    ///This magic function takes a container as its argument and fills
 		    ///its elements with new columns (i.e. variables)
 		    ///\param t can be
 		    ///- a standard STL compatible iterable container with
 		    ///\ref Col as its \c values_type like
 		    ///\code
 		    ///std::vector<LpBase::Col>
 		    ///std::list<LpBase::Col>
 		    ///\endcode
 		    ///- a standard STL compatible iterable container with
 		    ///\ref Col as its \c mapped_type like
 		    ///\code
 		    ///std::map<AnyType,LpBase::Col>
 		    ///\endcode
 		    ///- an iterable lemon \ref concepts::WriteMap "write map" like
 		    ///\code
 		    ///ListGraph::NodeMap<LpBase::Col>
 		    ///ListGraph::ArcMap<LpBase::Col>
 		    ///\endcode
 		    ///\return The number of the created column.
 		#ifdef DOXYGEN
 		    template<class T>
 		    int addColSet(T &t) { return 0;}
 		#else
 		    template<class T>
 		    typename enable_if<typename T::value_type::LpCol,int>::type
 		    addColSet(T &t,dummy<0> = 0) {
 		      int s=0;
 		      for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;}
 		      return s;
+		    }
 		    template<class T>
 		    typename enable_if<typename T::value_type::second_type::LpCol,
 		                       int>::type
 		    addColSet(T &t,dummy<1> = 1) {
 		      int s=0;
 		      for(typename T::iterator i=t.begin();i!=t.end();++i) {
 		        i->second=addCol();
 		        s++;
+		      }
 		      return s;
+		    }
 		    template<class T>
 		    typename enable_if<typename T::MapIt::Value::LpCol,
 		                       int>::type
 		    addColSet(T &t,dummy<2> = 2) {
 		      int s=0;
 		      for(typename T::MapIt i(t); i!=INVALID; ++i)
+		        {
 		          i.set(addCol());
 		          s++;
+		        }
 		      return s;
+		    }
 		#endif
 		    ///Set a column (i.e a dual constraint) of the LP
 		    ///\param c is the column to be modified
 		    ///\param e is a dual linear expression (see \ref DualExpr)
 		    ///a better one.
 		    void col(Col c, const DualExpr &e) {
 		      e.simplify();
 		      _setColCoeffs(cols(id(c)), ExprIterator(e.comps.begin(), rows),
 		                    ExprIterator(e.comps.end(), rows));
+		    }
 		    ///Get a column (i.e a dual constraint) of the LP
 		    ///\param c is the column to get
 		    ///\return the dual expression associated to the column
 		    DualExpr col(Col c) const {
 		      DualExpr e;
 		      _getColCoeffs(cols(id(c)), InsertIterator(e.comps, rows));
 		      return e;
+		    }
 		    ///Add a new column to the LP
 		    ///\param e is a dual linear expression (see \ref DualExpr)
 		    ///\param o is the corresponding component of the objective
 		    ///function. It is 0 by default.
 		    ///\return The created column.
 		    Col addCol(const DualExpr &e, Value o = 0) {
 		      Col c=addCol();
 		      col(c,e);
 		      objCoeff(c,o);
 		      return c;
+		    }
 		    ///Add a new empty row (i.e a new constraint) to the LP
 		    ///This function adds a new empty row (i.e a new constraint) to the LP.
 		    ///\return The created row
 		    Row addRow() { Row r; r._id = _addRowId(_addRow()); return r;}
 		    ///\brief Add several new rows (i.e constraints) at once
 		    ///
 		    ///This magic function takes a container as its argument and fills
 		    ///its elements with new row (i.e. variables)
 		    ///\param t can be
 		    ///- a standard STL compatible iterable container with
 		    ///\ref Row as its \c values_type like
 		    ///\code
 		    ///std::vector<LpBase::Row>
 		    ///std::list<LpBase::Row>
 		    ///\endcode
 		    ///- a standard STL compatible iterable container with
 		    ///\ref Row as its \c mapped_type like
 		    ///\code
 		    ///std::map<AnyType,LpBase::Row>
 		    ///\endcode
 		    ///- an iterable lemon \ref concepts::WriteMap "write map" like
 		    ///\code
 		    ///ListGraph::NodeMap<LpBase::Row>
 		    ///ListGraph::ArcMap<LpBase::Row>
 		    ///\endcode
 		    ///\return The number of rows created.
 		#ifdef DOXYGEN
 		    template<class T>
 		    int addRowSet(T &t) { return 0;}
 		#else
 		    template<class T>
 		    typename enable_if<typename T::value_type::LpRow,int>::type
 		    addRowSet(T &t, dummy<0> = 0) {
 		      int s=0;
 		      for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addRow();s++;}
 		      return s;
+		    }
 		    template<class T>
 		    typename enable_if<typename T::value_type::second_type::LpRow, int>::type
 		    addRowSet(T &t, dummy<1> = 1) {
 		      int s=0;
 		      for(typename T::iterator i=t.begin();i!=t.end();++i) {
 		        i->second=addRow();
 		        s++;
+		      }
 		      return s;
+		    }
 		    template<class T>
 		    typename enable_if<typename T::MapIt::Value::LpRow, int>::type
 		    addRowSet(T &t, dummy<2> = 2) {
 		      int s=0;
 		      for(typename T::MapIt i(t); i!=INVALID; ++i)
+		        {
 		          i.set(addRow());
 		          s++;
+		        }
 		      return s;
+		    }
 		#endif
 		    ///Set a row (i.e a constraint) of the LP
 		    ///\param r is the row to be modified
 		    ///\param l is lower bound (-\ref INF means no bound)
 		    ///\param e is a linear expression (see \ref Expr)
 		    ///\param u is the upper bound (\ref INF means no bound)
 		    void row(Row r, Value l, const Expr &e, Value u) {
 		      e.simplify();
 		      _setRowCoeffs(rows(id(r)), ExprIterator(e.comps.begin(), cols),
 		                    ExprIterator(e.comps.end(), cols));
 		      _setRowLowerBound(rows(id(r)),l - *e);
 		      _setRowUpperBound(rows(id(r)),u - *e);
+		    }
 		    ///Set a row (i.e a constraint) of the LP
 		    ///\param r is the row to be modified
 		    ///\param c is a linear expression (see \ref Constr)
 		    void row(Row r, const Constr &c) {
 		      row(r, c.lowerBounded()?c.lowerBound():-INF,
 		          c.expr(), c.upperBounded()?c.upperBound():INF);
+		    }
 		    ///Get a row (i.e a constraint) of the LP
 		    ///\param r is the row to get
 		    ///\return the expression associated to the row
 		    Expr row(Row r) const {
 		      Expr e;
 		      _getRowCoeffs(rows(id(r)), InsertIterator(e.comps, cols));
 		      return e;
+		    }
 		    ///Add a new row (i.e a new constraint) to the LP
 		    ///\param l is the lower bound (-\ref INF means no bound)
 		    ///\param e is a linear expression (see \ref Expr)
 		    ///\param u is the upper bound (\ref INF means no bound)
 		    ///\return The created row.
 		    Row addRow(Value l,const Expr &e, Value u) {
 		      Row r=addRow();
 		      row(r,l,e,u);
 		      Row r;
 		      e.simplify();
 		      r._id = _addRowId(_addRow(l - *e, ExprIterator(e.comps.begin(), cols),
 		                                ExprIterator(e.comps.end(), cols), u - *e));
 		      return r;
+		    }
 		    ///Add a new row (i.e a new constraint) to the LP
 		    ///\param c is a linear expression (see \ref Constr)
 		    ///\return The created row.
 		    Row addRow(const Constr &c) {
 		      Row r=addRow();
 		      row(r,c);
 		      Row r;
 		      c.expr().simplify();
 		      r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound():-INF,
 		                                ExprIterator(c.expr().comps.begin(), cols),
 		                                ExprIterator(c.expr().comps.end(), cols),
 		                                c.upperBounded()?c.upperBound():INF));
 		      return r;
+		    }
 		    ///Erase a column (i.e a variable) from the LP
 		    ///\param c is the column to be deleted
 		    void erase(Col c) {
 		      _eraseCol(cols(id(c)));
 		      _eraseColId(cols(id(c)));
+		    }
 		    ///Erase a row (i.e a constraint) from the LP
 		    ///\param r is the row to be deleted
 		    void erase(Row r) {
 		      _eraseRow(rows(id(r)));
 		      _eraseRowId(rows(id(r)));
+		    }
 		    /// Get the name of a column
 		    ///\param c is the coresponding column
 		    ///\return The name of the colunm
 		    std::string colName(Col c) const {
 		      std::string name;
 		      _getColName(cols(id(c)), name);
 		      return name;
+		    }
 		    /// Set the name of a column
 		    ///\param c is the coresponding column
 		    ///\param name The name to be given
 		    void colName(Col c, const std::string& name) {
 		      _setColName(cols(id(c)), name);
+		    }
 		    /// Get the column by its name
 		    ///\param name The name of the column
 		    ///\return the proper column or \c INVALID
 		    Col colByName(const std::string& name) const {
 		      int k = _colByName(name);
 		      return k != -1 ? Col(cols[k]) : Col(INVALID);
+		    }
 		    /// Get the name of a row
 		    ///\param r is the coresponding row
 		    ///\return The name of the row
 		    std::string rowName(Row r) const {
 		      std::string name;
 		      _getRowName(rows(id(r)), name);
 		      return name;
+		    }
 		    /// Set the name of a row
 		    ///\param r is the coresponding row
 		    ///\param name The name to be given
 		    void rowName(Row r, const std::string& name) {
 		      _setRowName(rows(id(r)), name);
+		    }
 		    /// Get the row by its name
 		    ///\param name The name of the row
 		    ///\return the proper row or \c INVALID
 		    Row rowByName(const std::string& name) const {
 		      int k = _rowByName(name);
 		      return k != -1 ? Row(rows[k]) : Row(INVALID);
+		    }
 		    /// Set an element of the coefficient matrix of the LP
 		    ///\param r is the row of the element to be modified
 		    ///\param c is the column of the element to be modified
 		    ///\param val is the new value of the coefficient
 		    void coeff(Row r, Col c, Value val) {
 		      _setCoeff(rows(id(r)),cols(id(c)), val);
+		    }
 		    /// Get an element of the coefficient matrix of the LP
 		    ///\param r is the row of the element
 		    ///\param c is the column of the element
 		    ///\return the corresponding coefficient
 		    Value coeff(Row r, Col c) const {
 		      return _getCoeff(rows(id(r)),cols(id(c)));
+		    }
 		    /// Set the lower bound of a column (i.e a variable)
 		    /// The lower bound of a variable (column) has to be given by an
 		    /// extended number of type Value, i.e. a finite number of type
 		    /// Value or -\ref INF.
 		    void colLowerBound(Col c, Value value) {
 		      _setColLowerBound(cols(id(c)),value);
+		    }
 		    /// Get the lower bound of a column (i.e a variable)
 		    /// This function returns the lower bound for column (variable) \c c
 		    /// (this might be -\ref INF as well).
 		    ///\return The lower bound for column \c c
 		    Value colLowerBound(Col c) const {
 		      return _getColLowerBound(cols(id(c)));
+		    }
 		    ///\brief Set the lower bound of  several columns
 		    ///(i.e variables) at once
 		    ///
 		    ///This magic function takes a container as its argument
 		    ///and applies the function on all of its elements.
 		    ///The lower bound of a variable (column) has to be given by an
 		    ///extended number of type Value, i.e. a finite number of type
 		    ///Value or -\ref INF.
 		#ifdef DOXYGEN
 		    template<class T>
 		    void colLowerBound(T &t, Value value) { return 0;}
 		#else
 		    template<class T>
 		    typename enable_if<typename T::value_type::LpCol,void>::type
 		    colLowerBound(T &t, Value value,dummy<0> = 0) {
 		      for(typename T::iterator i=t.begin();i!=t.end();++i) {
 		        colLowerBound(*i, value);
+		      }
+		    }
 		    template<class T>
 		    typename enable_if<typename T::value_type::second_type::LpCol,
 		                       void>::type
 		    colLowerBound(T &t, Value value,dummy<1> = 1) {
 		      for(typename T::iterator i=t.begin();i!=t.end();++i) {
 		        colLowerBound(i->second, value);
+		      }
+		    }
 		    template<class T>
 		    typename enable_if<typename T::MapIt::Value::LpCol,
 		                       void>::type
 		    colLowerBound(T &t, Value value,dummy<2> = 2) {
 		      for(typename T::MapIt i(t); i!=INVALID; ++i){
 		        colLowerBound(*i, value);
+		      }
+		    }
 		#endif
 		    /// Set the upper bound of a column (i.e a variable)
 		    /// The upper bound of a variable (column) has to be given by an
 		    /// extended number of type Value, i.e. a finite number of type
 		    /// Value or \ref INF.
 		    void colUpperBound(Col c, Value value) {
 		      _setColUpperBound(cols(id(c)),value);
 		    };
 		    /// Get the upper bound of a column (i.e a variable)
 		    /// This function returns the upper bound for column (variable) \c c
 		    /// (this might be \ref INF as well).
 		    /// \return The upper bound for column \c c
 		    Value colUpperBound(Col c) const {
 		      return _getColUpperBound(cols(id(c)));
+		    }
 		    ///\brief Set the upper bound of  several columns
 		    ///(i.e variables) at once
 		    ///
 		    ///This magic function takes a container as its argument
 		    ///and applies the function on all of its elements.
 		    ///The upper bound of a variable (column) has to be given by an
 		    ///extended number of type Value, i.e. a finite number of type
 		    ///Value or \ref INF.
 		#ifdef DOXYGEN
 		    template<class T>
 		    void colUpperBound(T &t, Value value) { return 0;}
 		#else
 		    template<class T1>
 		    typename enable_if<typename T1::value_type::LpCol,void>::type
 		    colUpperBound(T1 &t, Value value,dummy<0> = 0) {
 		      for(typename T1::iterator i=t.begin();i!=t.end();++i) {
 		        colUpperBound(*i, value);
+		      }
+		    }
 		    template<class T1>
 		    typename enable_if<typename T1::value_type::second_type::LpCol,
 		                       void>::type
 		    colUpperBound(T1 &t, Value value,dummy<1> = 1) {
 		      for(typename T1::iterator i=t.begin();i!=t.end();++i) {
 		        colUpperBound(i->second, value);
+		      }
+		    }
 		    template<class T1>
 		    typename enable_if<typename T1::MapIt::Value::LpCol,
 		                       void>::type
 		    colUpperBound(T1 &t, Value value,dummy<2> = 2) {
 		      for(typename T1::MapIt i(t); i!=INVALID; ++i){
 		        colUpperBound(*i, value);
+		      }
+		    }
 		#endif
 		    /// Set the lower and the upper bounds of a column (i.e a variable)
 		    /// The lower and the upper bounds of
 		    /// a variable (column) have to be given by an
 		    /// extended number of type Value, i.e. a finite number of type
 		    /// Value, -\ref INF or \ref INF.
 		    void colBounds(Col c, Value lower, Value upper) {
 		      _setColLowerBound(cols(id(c)),lower);
 		      _setColUpperBound(cols(id(c)),upper);
+		    }
 		    ///\brief Set the lower and the upper bound of several columns
 		    ///(i.e variables) at once
 		    ///
 		    ///This magic function takes a container as its argument
 		    ///and applies the function on all of its elements.
 		    /// The lower and the upper bounds of
 		    /// a variable (column) have to be given by an
 		    /// extended number of type Value, i.e. a finite number of type
 		    /// Value, -\ref INF or \ref INF.
 		#ifdef DOXYGEN
 		    template<class T>
 		    void colBounds(T &t, Value lower, Value upper) { return 0;}
 		#else
 		    template<class T2>
 		    typename enable_if<typename T2::value_type::LpCol,void>::type
 		    colBounds(T2 &t, Value lower, Value upper,dummy<0> = 0) {
 		      for(typename T2::iterator i=t.begin();i!=t.end();++i) {
 		        colBounds(*i, lower, upper);
+		      }
+		    }
 		    template<class T2>
 		    typename enable_if<typename T2::value_type::second_type::LpCol, void>::type
 		    colBounds(T2 &t, Value lower, Value upper,dummy<1> = 1) {
 		      for(typename T2::iterator i=t.begin();i!=t.end();++i) {
 		        colBounds(i->second, lower, upper);
+		      }
+		    }
 		    template<class T2>
 		    typename enable_if<typename T2::MapIt::Value::LpCol, void>::type
 		    colBounds(T2 &t, Value lower, Value upper,dummy<2> = 2) {
 		      for(typename T2::MapIt i(t); i!=INVALID; ++i){
 		        colBounds(*i, lower, upper);
+		      }
+		    }
 		#endif
 		    /// Set the lower bound of a row (i.e a constraint)
 		    /// The lower bound of a constraint (row) has to be given by an
 		    /// extended number of type Value, i.e. a finite number of type
 		    /// Value or -\ref INF.
 		    void rowLowerBound(Row r, Value value) {
 		      _setRowLowerBound(rows(id(r)),value);
+		    }
 		    /// Get the lower bound of a row (i.e a constraint)
 		    /// This function returns the lower bound for row (constraint) \c c
 		    /// (this might be -\ref INF as well).
 		    ///\return The lower bound for row \c r
 		    Value rowLowerBound(Row r) const {
 		      return _getRowLowerBound(rows(id(r)));
+		    }
 		    /// Set the upper bound of a row (i.e a constraint)
 		    /// The upper bound of a constraint (row) has to be given by an
 		    /// extended number of type Value, i.e. a finite number of type
 		    /// Value or -\ref INF.
 		    void rowUpperBound(Row r, Value value) {
 		      _setRowUpperBound(rows(id(r)),value);
+		    }
 		    /// Get the upper bound of a row (i.e a constraint)
 		    /// This function returns the upper bound for row (constraint) \c c
 		    /// (this might be -\ref INF as well).
 		    ///\return The upper bound for row \c r
 		    Value rowUpperBound(Row r) const {
 		      return _getRowUpperBound(rows(id(r)));
+		    }
 		    ///Set an element of the objective function
 		    void objCoeff(Col c, Value v) {_setObjCoeff(cols(id(c)),v); };
 		    ///Get an element of the objective function
 		    Value objCoeff(Col c) const { return _getObjCoeff(cols(id(c))); };
 		    ///Set the objective function
 		    ///\param e is a linear expression of type \ref Expr.
 		    ///
 		    void obj(const Expr& e) {
 		      _setObjCoeffs(ExprIterator(e.comps.begin(), cols),
 		                    ExprIterator(e.comps.end(), cols));
 		      obj_const_comp = *e;
+		    }
 		    ///Get the objective function
 		    ///\return the objective function as a linear expression of type
 		    ///Expr.
 		    Expr obj() const {
 		      Expr e;
 		      _getObjCoeffs(InsertIterator(e.comps, cols));
 		      *e = obj_const_comp;
 		      return e;
+		    }
 		    ///Set the direction of optimization
 		    void sense(Sense sense) { _setSense(sense); }
 		    ///Query the direction of the optimization
 		    Sense sense() const {return _getSense(); }
 		    ///Set the sense to maximization
 		    void max() { _setSense(MAX); }
 		    ///Set the sense to maximization
 		    void min() { _setSense(MIN); }
 		    ///Clears the problem
 		    void clear() { _clear(); }
 		    /// Sets the message level of the solver
 		    void messageLevel(MessageLevel level) { _messageLevel(level); }
 		    ///@}
 		  };
 		  /// Addition
 		  ///\relates LpBase::Expr
 		  ///
 		  inline LpBase::Expr operator+(const LpBase::Expr &a, const LpBase::Expr &b) {
 		    LpBase::Expr tmp(a);
 		    tmp+=b;
 		    return tmp;
+		  }
 		  ///Substraction
 		  ///\relates LpBase::Expr
 		  ///
 		  inline LpBase::Expr operator-(const LpBase::Expr &a, const LpBase::Expr &b) {
 		    LpBase::Expr tmp(a);
 		    tmp-=b;
 		    return tmp;
+		  }
 		  ///Multiply with constant
 		  ///\relates LpBase::Expr
 		  ///
 		  inline LpBase::Expr operator*(const LpBase::Expr &a, const LpBase::Value &b) {
 		    LpBase::Expr tmp(a);
 		    tmp*=b;
 		    return tmp;
+		  }
 		  ///Multiply with constant
 		  ///\relates LpBase::Expr
 		  ///
 		  inline LpBase::Expr operator*(const LpBase::Value &a, const LpBase::Expr &b) {
 		    LpBase::Expr tmp(b);
 		    tmp*=a;
 		    return tmp;
+		  }
 		  ///Divide with constant
 		  ///\relates LpBase::Expr
 		  ///
 		  inline LpBase::Expr operator/(const LpBase::Expr &a, const LpBase::Value &b) {
 		    LpBase::Expr tmp(a);
 		    tmp/=b;
 		    return tmp;
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator<=(const LpBase::Expr &e,
 		                                   const LpBase::Expr &f) {
 		    return LpBase::Constr(0, f - e, LpBase::INF);
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator<=(const LpBase::Value &e,
 		                                   const LpBase::Expr &f) {
 		    return LpBase::Constr(e, f, LpBase::NaN);
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator<=(const LpBase::Expr &e,
 		                                   const LpBase::Value &f) {
 		    return LpBase::Constr(- LpBase::INF, e, f);
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator>=(const LpBase::Expr &e,
 		                                   const LpBase::Expr &f) {
 		    return LpBase::Constr(0, e - f, LpBase::INF);
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator>=(const LpBase::Value &e,
 		                                   const LpBase::Expr &f) {
 		    return LpBase::Constr(LpBase::NaN, f, e);
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator>=(const LpBase::Expr &e,
 		                                   const LpBase::Value &f) {
 		    return LpBase::Constr(f, e, LpBase::INF);
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator==(const LpBase::Expr &e,
 		                                   const LpBase::Value &f) {
 		    return LpBase::Constr(f, e, f);
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator==(const LpBase::Expr &e,
 		                                   const LpBase::Expr &f) {
 		    return LpBase::Constr(0, f - e, 0);
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator<=(const LpBase::Value &n,
 		                                   const LpBase::Constr &c) {
 		    LpBase::Constr tmp(c);
 		    LEMON_ASSERT(isNaN(tmp.lowerBound()), "Wrong LP constraint");
 		    tmp.lowerBound()=n;
 		    return tmp;
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator<=(const LpBase::Constr &c,
 		                                   const LpBase::Value &n)
+		  {
 		    LpBase::Constr tmp(c);
 		    LEMON_ASSERT(isNaN(tmp.upperBound()), "Wrong LP constraint");
 		    tmp.upperBound()=n;
 		    return tmp;
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator>=(const LpBase::Value &n,
 		                                   const LpBase::Constr &c) {
 		    LpBase::Constr tmp(c);
 		    LEMON_ASSERT(isNaN(tmp.upperBound()), "Wrong LP constraint");
 		    tmp.upperBound()=n;
 		    return tmp;
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator>=(const LpBase::Constr &c,
 		                                   const LpBase::Value &n)
+		  {
 		    LpBase::Constr tmp(c);
 		    LEMON_ASSERT(isNaN(tmp.lowerBound()), "Wrong LP constraint");
 		    tmp.lowerBound()=n;
 		    return tmp;
+		  }
 		  ///Addition
 		  ///\relates LpBase::DualExpr
 		  ///
 		  inline LpBase::DualExpr operator+(const LpBase::DualExpr &a,
 		                                    const LpBase::DualExpr &b) {
 		    LpBase::DualExpr tmp(a);
 		    tmp+=b;
 		    return tmp;
+		  }
 		  ///Substraction

lemon/lp_skeleton.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * 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.
+		 *
 		 */
 		#include <lemon/lp_skeleton.h>
 		///\file
 		///\brief A skeleton file to implement LP solver interfaces
 		namespace lemon {
 		  int SkeletonSolverBase::_addCol()
+		  {
 		    return ++col_num;
+		  }
 		  int SkeletonSolverBase::_addRow()
+		  {
 		    return ++row_num;
+		  }
 		  int SkeletonSolverBase::_addRow(Value, ExprIterator, ExprIterator, Value)
+		  {
 		    return ++row_num;
+		  }
 		  void SkeletonSolverBase::_eraseCol(int) {}
 		  void SkeletonSolverBase::_eraseRow(int) {}
 		  void SkeletonSolverBase::_getColName(int, std::string &) const {}
 		  void SkeletonSolverBase::_setColName(int, const std::string &) {}
 		  int SkeletonSolverBase::_colByName(const std::string&) const { return -1; }
 		  void SkeletonSolverBase::_getRowName(int, std::string &) const {}
 		  void SkeletonSolverBase::_setRowName(int, const std::string &) {}
 		  int SkeletonSolverBase::_rowByName(const std::string&) const { return -1; }
 		  void SkeletonSolverBase::_setRowCoeffs(int, ExprIterator, ExprIterator) {}
 		  void SkeletonSolverBase::_getRowCoeffs(int, InsertIterator) const {}
 		  void SkeletonSolverBase::_setColCoeffs(int, ExprIterator, ExprIterator) {}
 		  void SkeletonSolverBase::_getColCoeffs(int, InsertIterator) const {}
 		  void SkeletonSolverBase::_setCoeff(int, int, Value) {}
 		  SkeletonSolverBase::Value SkeletonSolverBase::_getCoeff(int, int) const
 		  { return 0; }
 		  void SkeletonSolverBase::_setColLowerBound(int, Value) {}
 		  SkeletonSolverBase::Value SkeletonSolverBase::_getColLowerBound(int) const
 		  {  return 0; }
 		  void SkeletonSolverBase::_setColUpperBound(int, Value) {}
 		  SkeletonSolverBase::Value SkeletonSolverBase::_getColUpperBound(int) const
 		  {  return 0; }
 		  void SkeletonSolverBase::_setRowLowerBound(int, Value) {}
 		  SkeletonSolverBase::Value SkeletonSolverBase::_getRowLowerBound(int) const
 		  {  return 0; }
 		  void SkeletonSolverBase::_setRowUpperBound(int, Value) {}
 		  SkeletonSolverBase::Value SkeletonSolverBase::_getRowUpperBound(int) const
 		  {  return 0; }
 		  void SkeletonSolverBase::_setObjCoeffs(ExprIterator, ExprIterator) {}
 		  void SkeletonSolverBase::_getObjCoeffs(InsertIterator) const {};
 		  void SkeletonSolverBase::_setObjCoeff(int, Value) {}
 		  SkeletonSolverBase::Value SkeletonSolverBase::_getObjCoeff(int) const
 		  {  return 0; }
 		  void SkeletonSolverBase::_setSense(Sense) {}
 		  SkeletonSolverBase::Sense SkeletonSolverBase::_getSense() const
 		  { return MIN; }
 		  void SkeletonSolverBase::_clear() {
 		    row_num = col_num = 0;
+		  }
 		  void SkeletonSolverBase::_messageLevel(MessageLevel) {}
 		  LpSkeleton::SolveExitStatus LpSkeleton::_solve() { return SOLVED; }
 		  LpSkeleton::Value LpSkeleton::_getPrimal(int) const { return 0; }
 		  LpSkeleton::Value LpSkeleton::_getDual(int) const { return 0; }
 		  LpSkeleton::Value LpSkeleton::_getPrimalValue() const { return 0; }
 		  LpSkeleton::Value LpSkeleton::_getPrimalRay(int) const { return 0; }
 		  LpSkeleton::Value LpSkeleton::_getDualRay(int) const { return 0; }
 		  LpSkeleton::ProblemType LpSkeleton::_getPrimalType() const
 		  { return UNDEFINED; }
 		  LpSkeleton::ProblemType LpSkeleton::_getDualType() const
 		  { return UNDEFINED; }
 		  LpSkeleton::VarStatus LpSkeleton::_getColStatus(int) const
 		  { return BASIC; }
 		  LpSkeleton::VarStatus LpSkeleton::_getRowStatus(int) const
 		  { return BASIC; }
 		  LpSkeleton* LpSkeleton::newSolver() const
 		  { return static_cast<LpSkeleton*>(0); }
 		  LpSkeleton* LpSkeleton::cloneSolver() const
 		  { return static_cast<LpSkeleton*>(0); }
 		  const char* LpSkeleton::_solverName() const { return "LpSkeleton"; }
 		  MipSkeleton::SolveExitStatus MipSkeleton::_solve()
 		  { return SOLVED; }
 		  MipSkeleton::Value MipSkeleton::_getSol(int) const { return 0; }
 		  MipSkeleton::Value MipSkeleton::_getSolValue() const { return 0; }
 		  MipSkeleton::ProblemType MipSkeleton::_getType() const
 		  { return UNDEFINED; }
 		  MipSkeleton* MipSkeleton::newSolver() const
 		  { return static_cast<MipSkeleton*>(0); }
 		  MipSkeleton* MipSkeleton::cloneSolver() const
 		  { return static_cast<MipSkeleton*>(0); }
 		  const char* MipSkeleton::_solverName() const { return "MipSkeleton"; }
 		} //namespace lemon

lemon/lp_skeleton.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * 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.
+		 *
 		 */
 		#ifndef LEMON_LP_SKELETON_H
 		#define LEMON_LP_SKELETON_H
 		#include <lemon/lp_base.h>
 		///\file
 		///\brief Skeleton file to implement LP/MIP solver interfaces
 		///
 		///The classes in this file do nothing, but they can serve as skeletons when
 		///implementing an interface to new solvers.
 		namespace lemon {
 		  ///A skeleton class to implement LP/MIP solver base interface
 		  ///This class does nothing, but it can serve as a skeleton when
 		  ///implementing an interface to new solvers.
 		  class SkeletonSolverBase : public virtual LpBase {
 		    int col_num,row_num;
 		  protected:
 		    SkeletonSolverBase()
 		      : col_num(-1), row_num(-1) {}
 		    /// \e
 		    virtual int _addCol();
 		    /// \e
 		    virtual int _addRow();
 		    /// \e
 		    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
 		    /// \e
 		    virtual void _eraseCol(int i);
 		    /// \e
 		    virtual void _eraseRow(int i);
 		    /// \e
 		    virtual void _getColName(int col, std::string& name) const;
 		    /// \e
 		    virtual void _setColName(int col, const std::string& name);
 		    /// \e
 		    virtual int _colByName(const std::string& name) const;
 		    /// \e
 		    virtual void _getRowName(int row, std::string& name) const;
 		    /// \e
 		    virtual void _setRowName(int row, const std::string& name);
 		    /// \e
 		    virtual int _rowByName(const std::string& name) const;
 		    /// \e
 		    virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e);
 		    /// \e
 		    virtual void _getRowCoeffs(int i, InsertIterator b) const;
 		    /// \e
 		    virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e);
 		    /// \e
 		    virtual void _getColCoeffs(int i, InsertIterator b) const;
 		    /// Set one element of the coefficient matrix
 		    virtual void _setCoeff(int row, int col, Value value);
 		    /// Get one element of the coefficient matrix
 		    virtual Value _getCoeff(int row, int col) const;
 		    /// The lower bound of a variable (column) have to be given by an
 		    /// extended number of type Value, i.e. a finite number of type
 		    /// Value or -\ref INF.
 		    virtual void _setColLowerBound(int i, Value value);
 		    /// \e
 		    /// The lower bound of a variable (column) is an
 		    /// extended number of type Value, i.e. a finite number of type
 		    /// Value or -\ref INF.
 		    virtual Value _getColLowerBound(int i) const;
 		    /// The upper bound of a variable (column) have to be given by an
 		    /// extended number of type Value, i.e. a finite number of type
 		    /// Value or \ref INF.
 		    virtual void _setColUpperBound(int i, Value value);
 		    /// \e
 		    /// The upper bound of a variable (column) is an
 		    /// extended number of type Value, i.e. a finite number of type
 		    /// Value or \ref INF.
 		    virtual Value _getColUpperBound(int i) const;
 		    /// The lower bound of a constraint (row) have to be given by an
 		    /// extended number of type Value, i.e. a finite number of type
 		    /// Value or -\ref INF.
 		    virtual void _setRowLowerBound(int i, Value value);
 		    /// \e
 		    /// The lower bound of a constraint (row) is an
 		    /// extended number of type Value, i.e. a finite number of type
 		    /// Value or -\ref INF.
 		    virtual Value _getRowLowerBound(int i) const;
 		    /// The upper bound of a constraint (row) have to be given by an
 		    /// extended number of type Value, i.e. a finite number of type
 		    /// Value or \ref INF.
 		    virtual void _setRowUpperBound(int i, Value value);
 		    /// \e
 		    /// The upper bound of a constraint (row) is an
 		    /// extended number of type Value, i.e. a finite number of type
 		    /// Value or \ref INF.
 		    virtual Value _getRowUpperBound(int i) const;
 		    /// \e
 		    virtual void _setObjCoeffs(ExprIterator b, ExprIterator e);
 		    /// \e
 		    virtual void _getObjCoeffs(InsertIterator b) const;
 		    /// \e
 		    virtual void _setObjCoeff(int i, Value obj_coef);
 		    /// \e
 		    virtual Value _getObjCoeff(int i) const;
 		    ///\e
 		    virtual void _setSense(Sense);
 		    ///\e
 		    virtual Sense _getSense() const;
 		    ///\e
 		    virtual void _clear();
 		    ///\e
 		    virtual void _messageLevel(MessageLevel);
 		  };
 		  /// \brief Skeleton class for an LP solver interface
 		  ///
 		  ///This class does nothing, but it can serve as a skeleton when
 		  ///implementing an interface to new solvers.
 		  ///\ingroup lp_group
 		  class LpSkeleton : public LpSolver, public SkeletonSolverBase {
 		  public:
 		    ///\e
 		    LpSkeleton() : LpSolver(), SkeletonSolverBase() {}
 		    ///\e
 		    virtual LpSkeleton* newSolver() const;
 		    ///\e
 		    virtual LpSkeleton* cloneSolver() const;
 		  protected:
 		    ///\e
 		    virtual SolveExitStatus _solve();
 		    ///\e
 		    virtual Value _getPrimal(int i) const;
 		    ///\e
 		    virtual Value _getDual(int i) const;
 		    ///\e
 		    virtual Value _getPrimalValue() const;
 		    ///\e
 		    virtual Value _getPrimalRay(int i) const;
 		    ///\e
 		    virtual Value _getDualRay(int i) const;
 		    ///\e
 		    virtual ProblemType _getPrimalType() const;
 		    ///\e
 		    virtual ProblemType _getDualType() const;
 		    ///\e
 		    virtual VarStatus _getColStatus(int i) const;
 		    ///\e
 		    virtual VarStatus _getRowStatus(int i) const;
 		    ///\e
 		    virtual const char* _solverName() const;
 		  };
 		  /// \brief Skeleton class for a MIP solver interface
 		  ///
 		  ///This class does nothing, but it can serve as a skeleton when
 		  ///implementing an interface to new solvers.
 		  ///\ingroup lp_group
 		  class MipSkeleton : public MipSolver, public SkeletonSolverBase {
 		  public:
 		    ///\e
 		    MipSkeleton() : MipSolver(), SkeletonSolverBase() {}
 		    ///\e
 		    virtual MipSkeleton* newSolver() const;
 		    ///\e
 		    virtual MipSkeleton* cloneSolver() const;
 		  protected:
 		    ///\e
 		    virtual SolveExitStatus _solve();
 		    ///\e
 		    virtual Value _getSol(int i) const;
 		    ///\e
 		    virtual Value _getSolValue() const;
 		    ///\e
 		    virtual ProblemType _getType() const;
 		    ///\e
 		    virtual const char* _solverName() const;
 		  };
 		} //namespace lemon
 		#endif

lemon/soplex.cc

Show inline comments

/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 2003-2008
 * 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.
 *
 */

#include <iostream>
#include <lemon/soplex.h>

#include <soplex.h>
#include <spxout.h>


///\file
///\brief Implementation of the LEMON-SOPLEX lp solver interface.
namespace lemon {

  SoplexLp::SoplexLp() {
    soplex = new soplex::SoPlex;
    messageLevel(MESSAGE_NOTHING);
  }

  SoplexLp::~SoplexLp() {
    delete soplex;
  }

  SoplexLp::SoplexLp(const SoplexLp& lp) {
    rows = lp.rows;
    cols = lp.cols;

    soplex = new soplex::SoPlex;
    (*static_cast<soplex::SPxLP*>(soplex)) = *(lp.soplex);

    _col_names = lp._col_names;
    _col_names_ref = lp._col_names_ref;

    _row_names = lp._row_names;
    _row_names_ref = lp._row_names_ref;

    messageLevel(MESSAGE_NOTHING);
  }

  void SoplexLp::_clear_temporals() {
    _primal_values.clear();
    _dual_values.clear();
  }

  SoplexLp* SoplexLp::newSolver() const {
    SoplexLp* newlp = new SoplexLp();
    return newlp;
  }

  SoplexLp* SoplexLp::cloneSolver() const {
    SoplexLp* newlp = new SoplexLp(*this);
    return newlp;
  }

  const char* SoplexLp::_solverName() const { return "SoplexLp"; }

  int SoplexLp::_addCol() {
    soplex::LPCol c;
    c.setLower(-soplex::infinity);
    c.setUpper(soplex::infinity);
    soplex->addCol(c);

    _col_names.push_back(std::string());

    return soplex->nCols() - 1;
  }

  int SoplexLp::_addRow() {
    soplex::LPRow r;
    r.setLhs(-soplex::infinity);
    r.setRhs(soplex::infinity);
    soplex->addRow(r);

    _row_names.push_back(std::string());

    return soplex->nRows() - 1;
  }

  int SoplexLp::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
    soplex::DSVector v;
    for (ExprIterator it = b; it != e; ++it) {
      v.add(it->first, it->second);
    }
    soplex::LPRow r(l, v, u);
    soplex->addRow(r);

    _row_names.push_back(std::string());

    return soplex->nRows() - 1;
  }


  void SoplexLp::_eraseCol(int i) {
    soplex->removeCol(i);
    _col_names_ref.erase(_col_names[i]);
    _col_names[i] = _col_names.back();
    _col_names_ref[_col_names.back()] = i;
    _col_names.pop_back();
  }

  void SoplexLp::_eraseRow(int i) {
    soplex->removeRow(i);
    _row_names_ref.erase(_row_names[i]);
    _row_names[i] = _row_names.back();
    _row_names_ref[_row_names.back()] = i;
    _row_names.pop_back();
  }

  void SoplexLp::_eraseColId(int i) {
    cols.eraseIndex(i);
    cols.relocateIndex(i, cols.maxIndex());
  }
  void SoplexLp::_eraseRowId(int i) {
    rows.eraseIndex(i);
    rows.relocateIndex(i, rows.maxIndex());
  }

  void SoplexLp::_getColName(int c, std::string &name) const {
    name = _col_names[c];
  }

  void SoplexLp::_setColName(int c, const std::string &name) {
    _col_names_ref.erase(_col_names[c]);
    _col_names[c] = name;
    if (!name.empty()) {
      _col_names_ref.insert(std::make_pair(name, c));
    }
  }

  int SoplexLp::_colByName(const std::string& name) const {
    std::map<std::string, int>::const_iterator it =
      _col_names_ref.find(name);
    if (it != _col_names_ref.end()) {
      return it->second;
    } else {
      return -1;
    }
  }

  void SoplexLp::_getRowName(int r, std::string &name) const {
    name = _row_names[r];
  }

  void SoplexLp::_setRowName(int r, const std::string &name) {
    _row_names_ref.erase(_row_names[r]);
    _row_names[r] = name;
    if (!name.empty()) {
      _row_names_ref.insert(std::make_pair(name, r));
    }
  }

  int SoplexLp::_rowByName(const std::string& name) const {
    std::map<std::string, int>::const_iterator it =
      _row_names_ref.find(name);
    if (it != _row_names_ref.end()) {
      return it->second;
    } else {
      return -1;
    }
  }


  void SoplexLp::_setRowCoeffs(int i, ExprIterator b, ExprIterator e) {
    for (int j = 0; j < soplex->nCols(); ++j) {
      soplex->changeElement(i, j, 0.0);
    }
    for(ExprIterator it = b; it != e; ++it) {
      soplex->changeElement(i, it->first, it->second);
    }
  }

  void SoplexLp::_getRowCoeffs(int i, InsertIterator b) const {
    const soplex::SVector& vec = soplex->rowVector(i);
    for (int k = 0; k < vec.size(); ++k) {
      *b = std::make_pair(vec.index(k), vec.value(k));
      ++b;
    }
  }

  void SoplexLp::_setColCoeffs(int j, ExprIterator b, ExprIterator e) {
    for (int i = 0; i < soplex->nRows(); ++i) {
      soplex->changeElement(i, j, 0.0);
    }
    for(ExprIterator it = b; it != e; ++it) {
      soplex->changeElement(it->first, j, it->second);
    }
  }

  void SoplexLp::_getColCoeffs(int i, InsertIterator b) const {
    const soplex::SVector& vec = soplex->colVector(i);
    for (int k = 0; k < vec.size(); ++k) {
      *b = std::make_pair(vec.index(k), vec.value(k));
      ++b;
    }
  }

  void SoplexLp::_setCoeff(int i, int j, Value value) {
    soplex->changeElement(i, j, value);
  }

  SoplexLp::Value SoplexLp::_getCoeff(int i, int j) const {
    return soplex->rowVector(i)[j];
  }

  void SoplexLp::_setColLowerBound(int i, Value value) {
    LEMON_ASSERT(value != INF, "Invalid bound");
    soplex->changeLower(i, value != -INF ? value : -soplex::infinity);
  }

  SoplexLp::Value SoplexLp::_getColLowerBound(int i) const {
    double value = soplex->lower(i);
    return value != -soplex::infinity ? value : -INF;
  }

  void SoplexLp::_setColUpperBound(int i, Value value) {
    LEMON_ASSERT(value != -INF, "Invalid bound");
    soplex->changeUpper(i, value != INF ? value : soplex::infinity);
  }

  SoplexLp::Value SoplexLp::_getColUpperBound(int i) const {
    double value = soplex->upper(i);
    return value != soplex::infinity ? value : INF;
  }

  void SoplexLp::_setRowLowerBound(int i, Value lb) {
    LEMON_ASSERT(lb != INF, "Invalid bound");
    soplex->changeRange(i, lb != -INF ? lb : -soplex::infinity, soplex->rhs(i));
  }

  SoplexLp::Value SoplexLp::_getRowLowerBound(int i) const {
    double res = soplex->lhs(i);
    return res == -soplex::infinity ? -INF : res;
  }

  void SoplexLp::_setRowUpperBound(int i, Value ub) {
    LEMON_ASSERT(ub != -INF, "Invalid bound");
    soplex->changeRange(i, soplex->lhs(i), ub != INF ? ub : soplex::infinity);
  }

  SoplexLp::Value SoplexLp::_getRowUpperBound(int i) const {
    double res = soplex->rhs(i);
    return res == soplex::infinity ? INF : res;
  }

  void SoplexLp::_setObjCoeffs(ExprIterator b, ExprIterator e) {
    for (int j = 0; j < soplex->nCols(); ++j) {
      soplex->changeObj(j, 0.0);
    }
    for (ExprIterator it = b; it != e; ++it) {
      soplex->changeObj(it->first, it->second);
    }
  }

  void SoplexLp::_getObjCoeffs(InsertIterator b) const {
    for (int j = 0; j < soplex->nCols(); ++j) {
      Value coef = soplex->obj(j);
      if (coef != 0.0) {
        *b = std::make_pair(j, coef);
        ++b;
      }
    }
  }

  void SoplexLp::_setObjCoeff(int i, Value obj_coef) {
    soplex->changeObj(i, obj_coef);
  }

  SoplexLp::Value SoplexLp::_getObjCoeff(int i) const {
    return soplex->obj(i);
  }

  SoplexLp::SolveExitStatus SoplexLp::_solve() {

    _clear_temporals();
    
    _applyMessageLevel();

    soplex::SPxSolver::Status status = soplex->solve();

    switch (status) {
    case soplex::SPxSolver::OPTIMAL:
    case soplex::SPxSolver::INFEASIBLE:
    case soplex::SPxSolver::UNBOUNDED:
      return SOLVED;
    default:
      return UNSOLVED;
    }
  }

  SoplexLp::Value SoplexLp::_getPrimal(int i) const {
    if (_primal_values.empty()) {
      _primal_values.resize(soplex->nCols());
      soplex::Vector pv(_primal_values.size(), &_primal_values.front());
      soplex->getPrimal(pv);
    }
    return _primal_values[i];
  }

  SoplexLp::Value SoplexLp::_getDual(int i) const {
    if (_dual_values.empty()) {
      _dual_values.resize(soplex->nRows());
      soplex::Vector dv(_dual_values.size(), &_dual_values.front());
      soplex->getDual(dv);
    }
    return _dual_values[i];
  }

  SoplexLp::Value SoplexLp::_getPrimalValue() const {
    return soplex->objValue();
  }

  SoplexLp::VarStatus SoplexLp::_getColStatus(int i) const {
    switch (soplex->getBasisColStatus(i)) {
    case soplex::SPxSolver::BASIC:
      return BASIC;
    case soplex::SPxSolver::ON_UPPER:
      return UPPER;
    case soplex::SPxSolver::ON_LOWER:
      return LOWER;
    case soplex::SPxSolver::FIXED:
      return FIXED;
    case soplex::SPxSolver::ZERO:
      return FREE;
    default:
      LEMON_ASSERT(false, "Wrong column status");
      return VarStatus();
    }
  }

  SoplexLp::VarStatus SoplexLp::_getRowStatus(int i) const {
    switch (soplex->getBasisRowStatus(i)) {
    case soplex::SPxSolver::BASIC:
      return BASIC;
    case soplex::SPxSolver::ON_UPPER:
      return UPPER;
    case soplex::SPxSolver::ON_LOWER:
      return LOWER;
    case soplex::SPxSolver::FIXED:
      return FIXED;
    case soplex::SPxSolver::ZERO:
      return FREE;
    default:
      LEMON_ASSERT(false, "Wrong row status");
      return VarStatus();
    }
  }

  SoplexLp::Value SoplexLp::_getPrimalRay(int i) const {
    if (_primal_ray.empty()) {
      _primal_ray.resize(soplex->nCols());
      soplex::Vector pv(_primal_ray.size(), &_primal_ray.front());
      soplex->getDualfarkas(pv);
    }
    return _primal_ray[i];
  }

  SoplexLp::Value SoplexLp::_getDualRay(int i) const {
    if (_dual_ray.empty()) {
      _dual_ray.resize(soplex->nRows());
      soplex::Vector dv(_dual_ray.size(), &_dual_ray.front());
      soplex->getDualfarkas(dv);
    }
    return _dual_ray[i];
  }

  SoplexLp::ProblemType SoplexLp::_getPrimalType() const {
    switch (soplex->status()) {
    case soplex::SPxSolver::OPTIMAL:
      return OPTIMAL;
    case soplex::SPxSolver::UNBOUNDED:
      return UNBOUNDED;
    case soplex::SPxSolver::INFEASIBLE:
      return INFEASIBLE;
    default:
      return UNDEFINED;
    }
  }

  SoplexLp::ProblemType SoplexLp::_getDualType() const {
    switch (soplex->status()) {
    case soplex::SPxSolver::OPTIMAL:
      return OPTIMAL;
    case soplex::SPxSolver::UNBOUNDED:
      return UNBOUNDED;
    case soplex::SPxSolver::INFEASIBLE:
      return INFEASIBLE;
    default:
      return UNDEFINED;
    }
  }

  void SoplexLp::_setSense(Sense sense) {
    switch (sense) {
    case MIN:
      soplex->changeSense(soplex::SPxSolver::MINIMIZE);
      break;
    case MAX:
      soplex->changeSense(soplex::SPxSolver::MAXIMIZE);
    }
  }

  SoplexLp::Sense SoplexLp::_getSense() const {
    switch (soplex->spxSense()) {
    case soplex::SPxSolver::MAXIMIZE:
      return MAX;
    case soplex::SPxSolver::MINIMIZE:
      return MIN;
    default:
      LEMON_ASSERT(false, "Wrong sense.");
      return SoplexLp::Sense();
    }
  }

  void SoplexLp::_clear() {
    soplex->clear();
    _col_names.clear();
    _col_names_ref.clear();
    _row_names.clear();
    _row_names_ref.clear();
    cols.clear();
    rows.clear();
    _clear_temporals();
  }

  void SoplexLp::_messageLevel(MessageLevel level) {
    switch (level) {
    case MESSAGE_NOTHING:
      _message_level = -1;
      break;
    case MESSAGE_ERROR:
      _message_level = soplex::SPxOut::ERROR;
      break;
    case MESSAGE_WARNING:
      _message_level = soplex::SPxOut::WARNING;
      break;
    case MESSAGE_NORMAL:
      _message_level = soplex::SPxOut::INFO2;
      break;
    case MESSAGE_VERBOSE:
      _message_level = soplex::SPxOut::DEBUG;
      break;
    }
  }

  void SoplexLp::_applyMessageLevel() {
    soplex::Param::setVerbose(_message_level);
  }

} //namespace lemon


lemon/soplex.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * 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.
+		 *
 		 */
 		#ifndef LEMON_SOPLEX_H
 		#define LEMON_SOPLEX_H
 		///\file
 		///\brief Header of the LEMON-SOPLEX lp solver interface.
 		#include <vector>
 		#include <string>
 		#include <lemon/lp_base.h>
 		// Forward declaration
 		namespace soplex {
 		  class SoPlex;
+		}
 		namespace lemon {
 		  /// \ingroup lp_group
 		  ///
 		  /// \brief Interface for the SOPLEX solver
 		  ///
 		  /// This class implements an interface for the SoPlex LP solver.
 		  /// The SoPlex library is an object oriented lp solver library
 		  /// developed at the Konrad-Zuse-Zentrum f�r Informationstechnik
 		  /// Berlin (ZIB). You can find detailed information about it at the
 		  /// <tt>http://soplex.zib.de</tt> address.
 		  class SoplexLp : public LpSolver {
 		  private:
 		    soplex::SoPlex* soplex;
 		    std::vector<std::string> _col_names;
 		    std::map<std::string, int> _col_names_ref;
 		    std::vector<std::string> _row_names;
 		    std::map<std::string, int> _row_names_ref;
 		  private:
 		    // these values cannot be retrieved element by element
 		    mutable std::vector<Value> _primal_values;
 		    mutable std::vector<Value> _dual_values;
 		    mutable std::vector<Value> _primal_ray;
 		    mutable std::vector<Value> _dual_ray;
 		    void _clear_temporals();
 		  public:
 		    /// \e
 		    SoplexLp();
 		    /// \e
 		    SoplexLp(const SoplexLp&);
 		    /// \e
 		    ~SoplexLp();
 		    /// \e
 		    virtual SoplexLp* newSolver() const;
 		    /// \e
 		    virtual SoplexLp* cloneSolver() const;
 		  protected:
 		    virtual const char* _solverName() const;
 		    virtual int _addCol();
 		    virtual int _addRow();
 		    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
 		    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 SolveExitStatus _solve();
 		    virtual Value _getPrimal(int i) const;
 		    virtual Value _getDual(int i) const;
 		    virtual Value _getPrimalValue() const;
 		    virtual Value _getPrimalRay(int i) const;
 		    virtual Value _getDualRay(int i) const;
 		    virtual VarStatus _getColStatus(int i) const;
 		    virtual VarStatus _getRowStatus(int i) const;
 		    virtual ProblemType _getPrimalType() const;
 		    virtual ProblemType _getDualType() const;
 		    virtual void _clear();
 		    void _messageLevel(MessageLevel m);
 		    void _applyMessageLevel();
 		    int _message_level;
 		  };
 		} //END OF NAMESPACE LEMON
 		#endif //LEMON_SOPLEX_H

0 comments (0 inline)

RhodeCode

Login to your account

1	1	/* -- mode: C++; indent-tabs-mode: nil; --
2	2	*
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5	5	* Copyright (C) 2003-2008
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
8	8	*
9	9	* Permission to use, modify and distribute this software is granted
10	10	* provided that this copyright notice appears in all copies. For
11	11	* precise terms see the accompanying LICENSE file.
12	12	*
13	13	* This software is provided "AS IS" with no warranty of any kind,
14	14	* express or implied, and with no claim as to its suitability for any
15	15	* purpose.
16	16	*
17	17	*/
18	18
19	19	#include <lemon/clp.h>
20	20	#include <coin/ClpSimplex.hpp>
21	21
22	22	namespace lemon {
23	23
24	24	ClpLp::ClpLp() {
25	25	_prob = new ClpSimplex();
26	26	_init_temporals();
27	27	messageLevel(MESSAGE_NOTHING);
28	28	}
29	29
30	30	ClpLp::ClpLp(const ClpLp& other) {
31	31	_prob = new ClpSimplex(*other._prob);
32	32	rows = other.rows;
33	33	cols = other.cols;
34	34	_init_temporals();
35	35	messageLevel(MESSAGE_NOTHING);
36	36	}
37	37
38	38	ClpLp::~ClpLp() {
39	39	delete _prob;
40	40	_clear_temporals();
41	41	}
42	42
43	43	void ClpLp::_init_temporals() {
44	44	_primal_ray = 0;
45	45	_dual_ray = 0;
46	46	}
47	47
48	48	void ClpLp::_clear_temporals() {
49	49	if (_primal_ray) {
50	50	delete[] _primal_ray;
51	51	_primal_ray = 0;
52	52	}
53	53	if (_dual_ray) {
54	54	delete[] _dual_ray;
55	55	_dual_ray = 0;
56	56	}
57	57	}
58	58
59	59	ClpLp* ClpLp::newSolver() const {
60	60	ClpLp* newlp = new ClpLp;
61	61	return newlp;
62	62	}
63	63
64	64	ClpLp* ClpLp::cloneSolver() const {
65	65	ClpLp* copylp = new ClpLp(*this);
66	66	return copylp;
67	67	}
68	68
69	69	const char* ClpLp::_solverName() const { return "ClpLp"; }
70	70
71	71	int ClpLp::_addCol() {
72	72	_prob->addColumn(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX, 0.0);
73	73	return _prob->numberColumns() - 1;
74	74	}
75	75
76	76	int ClpLp::_addRow() {
77	77	_prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX);
78	78	return _prob->numberRows() - 1;
79	79	}
80	80
	81	int ClpLp::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
	82	std::vector<int> indexes;
	83	std::vector<Value> values;
	84
	85	for(ExprIterator it = b; it != e; ++it) {
	86	indexes.push_back(it->first);
	87	values.push_back(it->second);
	88	}
	89
	90	_prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
	91	return _prob->numberRows() - 1;
	92	}
	93
81	94
82	95	void ClpLp::_eraseCol(int c) {
83	96	_col_names_ref.erase(_prob->getColumnName(c));
84	97	_prob->deleteColumns(1, &c);
85	98	}
86	99
87	100	void ClpLp::_eraseRow(int r) {
88	101	_row_names_ref.erase(_prob->getRowName(r));
89	102	_prob->deleteRows(1, &r);
90	103	}
91	104
92	105	void ClpLp::_eraseColId(int i) {
93	106	cols.eraseIndex(i);
94	107	cols.shiftIndices(i);
95	108	}
96	109
97	110	void ClpLp::_eraseRowId(int i) {
98	111	rows.eraseIndex(i);
99	112	rows.shiftIndices(i);
100	113	}
101	114
102	115	void ClpLp::_getColName(int c, std::string& name) const {
103	116	name = _prob->getColumnName(c);
104	117	}
105	118
106	119	void ClpLp::_setColName(int c, const std::string& name) {
107	120	_prob->setColumnName(c, const_cast<std::string&>(name));
108	121	_col_names_ref[name] = c;
109	122	}
110	123
111	124	int ClpLp::_colByName(const std::string& name) const {
112	125	std::map<std::string, int>::const_iterator it = _col_names_ref.find(name);
113	126	return it != _col_names_ref.end() ? it->second : -1;
114	127	}
115	128
116	129	void ClpLp::_getRowName(int r, std::string& name) const {
117	130	name = _prob->getRowName(r);
118	131	}
119	132
120	133	void ClpLp::_setRowName(int r, const std::string& name) {
121	134	_prob->setRowName(r, const_cast<std::string&>(name));
122	135	_row_names_ref[name] = r;
123	136	}
124	137
125	138	int ClpLp::_rowByName(const std::string& name) const {
126	139	std::map<std::string, int>::const_iterator it = _row_names_ref.find(name);
127	140	return it != _row_names_ref.end() ? it->second : -1;
128	141	}
129	142
130	143
131	144	void ClpLp::_setRowCoeffs(int ix, ExprIterator b, ExprIterator e) {
132	145	std::map<int, Value> coeffs;
133	146
134	147	int n = _prob->clpMatrix()->getNumCols();
135	148
136	149	const int* indices = _prob->clpMatrix()->getIndices();
137	150	const double* elements = _prob->clpMatrix()->getElements();
138	151
139	152	for (int i = 0; i < n; ++i) {
140	153	CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i];
141	154	CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i];
142	155
143	156	const int* it = std::lower_bound(indices + begin, indices + end, ix);
144	157	if (it != indices + end && *it == ix && elements[it - indices] != 0.0) {
145	158	coeffs[i] = 0.0;
146	159	}
147	160	}
148	161
149	162	for (ExprIterator it = b; it != e; ++it) {
150	163	coeffs[it->first] = it->second;
151	164	}
152	165
153	166	for (std::map<int, Value>::iterator it = coeffs.begin();
154	167	it != coeffs.end(); ++it) {
155	168	_prob->modifyCoefficient(ix, it->first, it->second);
156	169	}
157	170	}
158	171
159	172	void ClpLp::_getRowCoeffs(int ix, InsertIterator b) const {
160	173	int n = _prob->clpMatrix()->getNumCols();
161	174
162	175	const int* indices = _prob->clpMatrix()->getIndices();
163	176	const double* elements = _prob->clpMatrix()->getElements();
164	177
165	178	for (int i = 0; i < n; ++i) {
166	179	CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i];
167	180	CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i];
168	181
169	182	const int* it = std::lower_bound(indices + begin, indices + end, ix);
170	183	if (it != indices + end && *it == ix) {
171	184	*b = std::make_pair(i, elements[it - indices]);
172	185	}
173	186	}
174	187	}
175	188
176	189	void ClpLp::_setColCoeffs(int ix, ExprIterator b, ExprIterator e) {
177	190	std::map<int, Value> coeffs;
178	191
179	192	CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];
180	193	CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];
181	194
182	195	const int* indices = _prob->clpMatrix()->getIndices();
183	196	const double* elements = _prob->clpMatrix()->getElements();
184	197
185	198	for (CoinBigIndex i = begin; i != end; ++i) {
186	199	if (elements[i] != 0.0) {
187	200	coeffs[indices[i]] = 0.0;
188	201	}
189	202	}
190	203	for (ExprIterator it = b; it != e; ++it) {
191	204	coeffs[it->first] = it->second;
192	205	}
193	206	for (std::map<int, Value>::iterator it = coeffs.begin();
194	207	it != coeffs.end(); ++it) {
195	208	_prob->modifyCoefficient(it->first, ix, it->second);
196	209	}
197	210	}
198	211
199	212	void ClpLp::_getColCoeffs(int ix, InsertIterator b) const {
200	213	CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];
201	214	CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];
202	215
203	216	const int* indices = _prob->clpMatrix()->getIndices();
204	217	const double* elements = _prob->clpMatrix()->getElements();
205	218
206	219	for (CoinBigIndex i = begin; i != end; ++i) {
207	220	*b = std::make_pair(indices[i], elements[i]);
208	221	++b;
209	222	}
210	223	}
211	224
212	225	void ClpLp::_setCoeff(int ix, int jx, Value value) {
213	226	_prob->modifyCoefficient(ix, jx, value);
214	227	}
215	228
216	229	ClpLp::Value ClpLp::_getCoeff(int ix, int jx) const {
217	230	CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];
218	231	CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];
219	232
220	233	const int* indices = _prob->clpMatrix()->getIndices();
221	234	const double* elements = _prob->clpMatrix()->getElements();
222	235
223	236	const int* it = std::lower_bound(indices + begin, indices + end, jx);
224	237	if (it != indices + end && *it == jx) {
225	238	return elements[it - indices];
226	239	} else {
227	240	return 0.0;
228	241	}
229	242	}
230	243
231	244	void ClpLp::_setColLowerBound(int i, Value lo) {
232	245	_prob->setColumnLower(i, lo == - INF ? - COIN_DBL_MAX : lo);
233	246	}
234	247
235	248	ClpLp::Value ClpLp::_getColLowerBound(int i) const {
236	249	double val = _prob->getColLower()[i];
237	250	return val == - COIN_DBL_MAX ? - INF : val;
238	251	}
239	252
240	253	void ClpLp::_setColUpperBound(int i, Value up) {
241	254	_prob->setColumnUpper(i, up == INF ? COIN_DBL_MAX : up);
242	255	}
243	256
244	257	ClpLp::Value ClpLp::_getColUpperBound(int i) const {
245	258	double val = _prob->getColUpper()[i];
246	259	return val == COIN_DBL_MAX ? INF : val;
247	260	}
248	261
249	262	void ClpLp::_setRowLowerBound(int i, Value lo) {
250	263	_prob->setRowLower(i, lo == - INF ? - COIN_DBL_MAX : lo);
251	264	}
252	265
253	266	ClpLp::Value ClpLp::_getRowLowerBound(int i) const {
254	267	double val = _prob->getRowLower()[i];
255	268	return val == - COIN_DBL_MAX ? - INF : val;
256	269	}
257	270
258	271	void ClpLp::_setRowUpperBound(int i, Value up) {
259	272	_prob->setRowUpper(i, up == INF ? COIN_DBL_MAX : up);
260	273	}
261	274
262	275	ClpLp::Value ClpLp::_getRowUpperBound(int i) const {
263	276	double val = _prob->getRowUpper()[i];
264	277	return val == COIN_DBL_MAX ? INF : val;
265	278	}
266	279
267	280	void ClpLp::_setObjCoeffs(ExprIterator b, ExprIterator e) {
268	281	int num = _prob->clpMatrix()->getNumCols();
269	282	for (int i = 0; i < num; ++i) {
270	283	_prob->setObjectiveCoefficient(i, 0.0);
271	284	}
272	285	for (ExprIterator it = b; it != e; ++it) {
273	286	_prob->setObjectiveCoefficient(it->first, it->second);
274	287	}
275	288	}
276	289
277	290	void ClpLp::_getObjCoeffs(InsertIterator b) const {
278	291	int num = _prob->clpMatrix()->getNumCols();
279	292	for (int i = 0; i < num; ++i) {
280	293	Value coef = _prob->getObjCoefficients()[i];
281	294	if (coef != 0.0) {
282	295	*b = std::make_pair(i, coef);
283	296	++b;
284	297	}
285	298	}
286	299	}
287	300
288	301	void ClpLp::_setObjCoeff(int i, Value obj_coef) {
289	302	_prob->setObjectiveCoefficient(i, obj_coef);
290	303	}
291	304
292	305	ClpLp::Value ClpLp::_getObjCoeff(int i) const {
293	306	return _prob->getObjCoefficients()[i];
294	307	}
295	308
296	309	ClpLp::SolveExitStatus ClpLp::_solve() {
297	310	return _prob->primal() >= 0 ? SOLVED : UNSOLVED;
298	311	}
299	312
300	313	ClpLp::SolveExitStatus ClpLp::solvePrimal() {
301	314	return _prob->primal() >= 0 ? SOLVED : UNSOLVED;
302	315	}
303	316
304	317	ClpLp::SolveExitStatus ClpLp::solveDual() {
305	318	return _prob->dual() >= 0 ? SOLVED : UNSOLVED;
306	319	}
307	320
308	321	ClpLp::SolveExitStatus ClpLp::solveBarrier() {
309	322	return _prob->barrier() >= 0 ? SOLVED : UNSOLVED;
310	323	}
311	324
312	325	ClpLp::Value ClpLp::_getPrimal(int i) const {
313	326	return _prob->primalColumnSolution()[i];
314	327	}
315	328	ClpLp::Value ClpLp::_getPrimalValue() const {
316	329	return _prob->objectiveValue();
317	330	}
318	331
319	332	ClpLp::Value ClpLp::_getDual(int i) const {
320	333	return _prob->dualRowSolution()[i];
321	334	}
322	335
323	336	ClpLp::Value ClpLp::_getPrimalRay(int i) const {
324	337	if (!_primal_ray) {
325	338	_primal_ray = _prob->unboundedRay();
326	339	LEMON_ASSERT(_primal_ray != 0, "Primal ray is not provided");
327	340	}
328	341	return _primal_ray[i];
329	342	}
330	343
331	344	ClpLp::Value ClpLp::_getDualRay(int i) const {
332	345	if (!_dual_ray) {
333	346	_dual_ray = _prob->infeasibilityRay();
334	347	LEMON_ASSERT(_dual_ray != 0, "Dual ray is not provided");
335	348	}
336	349	return _dual_ray[i];
337	350	}
338	351
339	352	ClpLp::VarStatus ClpLp::_getColStatus(int i) const {
340	353	switch (_prob->getColumnStatus(i)) {
341	354	case ClpSimplex::basic:
342	355	return BASIC;
343	356	case ClpSimplex::isFree:
344	357	return FREE;
345	358	case ClpSimplex::atUpperBound:
346	359	return UPPER;
347	360	case ClpSimplex::atLowerBound:
348	361	return LOWER;
349	362	case ClpSimplex::isFixed:
350	363	return FIXED;
351	364	case ClpSimplex::superBasic:
352	365	return FREE;
353	366	default:
354	367	LEMON_ASSERT(false, "Wrong column status");
355	368	return VarStatus();
356	369	}
357	370	}
358	371
359	372	ClpLp::VarStatus ClpLp::_getRowStatus(int i) const {
360	373	switch (_prob->getColumnStatus(i)) {
361	374	case ClpSimplex::basic:
362	375	return BASIC;
363	376	case ClpSimplex::isFree:
364	377	return FREE;
365	378	case ClpSimplex::atUpperBound:
366	379	return UPPER;
367	380	case ClpSimplex::atLowerBound:
368	381	return LOWER;
369	382	case ClpSimplex::isFixed:
370	383	return FIXED;
371	384	case ClpSimplex::superBasic:
372	385	return FREE;
373	386	default:
374	387	LEMON_ASSERT(false, "Wrong row status");
375	388	return VarStatus();
376	389	}
377	390	}
378	391
379	392
380	393	ClpLp::ProblemType ClpLp::_getPrimalType() const {
381	394	if (_prob->isProvenOptimal()) {
382	395	return OPTIMAL;
383	396	} else if (_prob->isProvenPrimalInfeasible()) {
384	397	return INFEASIBLE;
385	398	} else if (_prob->isProvenDualInfeasible()) {
386	399	return UNBOUNDED;
387	400	} else {
388	401	return UNDEFINED;
389	402	}
390	403	}
391	404
392	405	ClpLp::ProblemType ClpLp::_getDualType() const {
393	406	if (_prob->isProvenOptimal()) {
394	407	return OPTIMAL;
395	408	} else if (_prob->isProvenDualInfeasible()) {
396	409	return INFEASIBLE;
397	410	} else if (_prob->isProvenPrimalInfeasible()) {
398	411	return INFEASIBLE;
399	412	} else {
400	413	return UNDEFINED;
401	414	}
402	415	}
403	416
404	417	void ClpLp::_setSense(ClpLp::Sense sense) {
405	418	switch (sense) {
406	419	case MIN:
407	420	_prob->setOptimizationDirection(1);
408	421	break;
409	422	case MAX:
410	423	_prob->setOptimizationDirection(-1);
411	424	break;
412	425	}
413	426	}
414	427
415	428	ClpLp::Sense ClpLp::_getSense() const {
416	429	double dir = _prob->optimizationDirection();
417	430	if (dir > 0.0) {
418	431	return MIN;
419	432	} else {
420	433	return MAX;
421	434	}
422	435	}
423	436
424	437	void ClpLp::_clear() {
425	438	delete _prob;
426	439	_prob = new ClpSimplex();
427	440	rows.clear();
428	441	cols.clear();
429	442	_col_names_ref.clear();
430	443	_clear_temporals();
431	444	}
432	445
433	446	void ClpLp::_messageLevel(MessageLevel level) {
434	447	switch (level) {
435	448	case MESSAGE_NOTHING:
436	449	_prob->setLogLevel(0);
437	450	break;
438	451	case MESSAGE_ERROR:
439	452	_prob->setLogLevel(1);
440	453	break;
441	454	case MESSAGE_WARNING:
442	455	_prob->setLogLevel(2);
443	456	break;
444	457	case MESSAGE_NORMAL:
445	458	_prob->setLogLevel(3);
446	459	break;
447	460	case MESSAGE_VERBOSE:
448	461	_prob->setLogLevel(4);
449	462	break;
450	463	}
451	464	}
452	465
453	466	} //END OF NAMESPACE LEMON