# HG changeset patch # User Alpar Juttner # Date 2009-01-12 13:26:01 # Node ID 08d495d480899a56e5065a17058edb9e9ad325fc # Parent 76ec7bd57026964284fe00990441ced0ea3faa5e Remove lp_ prefix from the solver's header name diff --git a/lemon/Makefile.am b/lemon/Makefile.am --- a/lemon/Makefile.am +++ b/lemon/Makefile.am @@ -28,19 +28,19 @@ $(CLP_LIBS) if HAVE_GLPK -lemon_libemon_la_SOURCES += lemon/lp_glpk.cc +lemon_libemon_la_SOURCES += lemon/glpk.cc endif if HAVE_CPLEX -lemon_libemon_la_SOURCES += lemon/lp_cplex.cc +lemon_libemon_la_SOURCES += lemon/cplex.cc endif if HAVE_SOPLEX -lemon_libemon_la_SOURCES += lemon/lp_soplex.cc +lemon_libemon_la_SOURCES += lemon/soplex.cc endif if HAVE_CLP -lemon_libemon_la_SOURCES += lemon/lp_clp.cc +lemon_libemon_la_SOURCES += lemon/clp.cc endif lemon_HEADERS += \ @@ -50,10 +50,12 @@ lemon/bfs.h \ lemon/bin_heap.h \ lemon/circulation.h \ + lemon/clp.h \ lemon/color.h \ lemon/concept_check.h \ lemon/counter.h \ lemon/core.h \ + lemon/cplex.h \ lemon/dfs.h \ lemon/dijkstra.h \ lemon/dim2.h \ @@ -61,6 +63,7 @@ lemon/elevator.h \ lemon/error.h \ lemon/full_graph.h \ + lemon/glpk.h \ lemon/graph_to_eps.h \ lemon/grid_graph.h \ lemon/hypercube_graph.h \ @@ -71,11 +74,7 @@ lemon/list_graph.h \ lemon/lp.h \ lemon/lp_base.h \ - lemon/lp_clp.h \ - lemon/lp_cplex.h \ - lemon/lp_glpk.h \ lemon/lp_skeleton.h \ - lemon/lp_soplex.h \ lemon/list_graph.h \ lemon/maps.h \ lemon/math.h \ @@ -86,6 +85,7 @@ lemon/radix_sort.h \ lemon/random.h \ lemon/smart_graph.h \ + lemon/soplex.h \ lemon/suurballe.h \ lemon/time_measure.h \ lemon/tolerance.h \ diff --git a/lemon/clp.cc b/lemon/clp.cc new file mode 100644 --- /dev/null +++ b/lemon/clp.cc @@ -0,0 +1,437 @@ +/* -*- 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 +#include + +namespace lemon { + + LpClp::LpClp() { + _prob = new ClpSimplex(); + _init_temporals(); + messageLevel(MESSAGE_NO_OUTPUT); + } + + LpClp::LpClp(const LpClp& other) { + _prob = new ClpSimplex(*other._prob); + rows = other.rows; + cols = other.cols; + _init_temporals(); + messageLevel(MESSAGE_NO_OUTPUT); + } + + LpClp::~LpClp() { + delete _prob; + _clear_temporals(); + } + + void LpClp::_init_temporals() { + _primal_ray = 0; + _dual_ray = 0; + } + + void LpClp::_clear_temporals() { + if (_primal_ray) { + delete[] _primal_ray; + _primal_ray = 0; + } + if (_dual_ray) { + delete[] _dual_ray; + _dual_ray = 0; + } + } + + LpClp* LpClp::_newSolver() const { + LpClp* newlp = new LpClp; + return newlp; + } + + LpClp* LpClp::_cloneSolver() const { + LpClp* copylp = new LpClp(*this); + return copylp; + } + + const char* LpClp::_solverName() const { return "LpClp"; } + + int LpClp::_addCol() { + _prob->addColumn(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX, 0.0); + return _prob->numberColumns() - 1; + } + + int LpClp::_addRow() { + _prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX); + return _prob->numberRows() - 1; + } + + + void LpClp::_eraseCol(int c) { + _col_names_ref.erase(_prob->getColumnName(c)); + _prob->deleteColumns(1, &c); + } + + void LpClp::_eraseRow(int r) { + _row_names_ref.erase(_prob->getRowName(r)); + _prob->deleteRows(1, &r); + } + + void LpClp::_eraseColId(int i) { + cols.eraseIndex(i); + cols.shiftIndices(i); + } + + void LpClp::_eraseRowId(int i) { + rows.eraseIndex(i); + rows.shiftIndices(i); + } + + void LpClp::_getColName(int c, std::string& name) const { + name = _prob->getColumnName(c); + } + + void LpClp::_setColName(int c, const std::string& name) { + _prob->setColumnName(c, const_cast(name)); + _col_names_ref[name] = c; + } + + int LpClp::_colByName(const std::string& name) const { + std::map::const_iterator it = _col_names_ref.find(name); + return it != _col_names_ref.end() ? it->second : -1; + } + + void LpClp::_getRowName(int r, std::string& name) const { + name = _prob->getRowName(r); + } + + void LpClp::_setRowName(int r, const std::string& name) { + _prob->setRowName(r, const_cast(name)); + _row_names_ref[name] = r; + } + + int LpClp::_rowByName(const std::string& name) const { + std::map::const_iterator it = _row_names_ref.find(name); + return it != _row_names_ref.end() ? it->second : -1; + } + + + void LpClp::_setRowCoeffs(int ix, ExprIterator b, ExprIterator e) { + std::map 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::iterator it = coeffs.begin(); + it != coeffs.end(); ++it) { + _prob->modifyCoefficient(ix, it->first, it->second); + } + } + + void LpClp::_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 LpClp::_setColCoeffs(int ix, ExprIterator b, ExprIterator e) { + std::map 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::iterator it = coeffs.begin(); + it != coeffs.end(); ++it) { + _prob->modifyCoefficient(it->first, ix, it->second); + } + } + + void LpClp::_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 LpClp::_setCoeff(int ix, int jx, Value value) { + _prob->modifyCoefficient(ix, jx, value); + } + + LpClp::Value LpClp::_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 LpClp::_setColLowerBound(int i, Value lo) { + _prob->setColumnLower(i, lo == - INF ? - COIN_DBL_MAX : lo); + } + + LpClp::Value LpClp::_getColLowerBound(int i) const { + double val = _prob->getColLower()[i]; + return val == - COIN_DBL_MAX ? - INF : val; + } + + void LpClp::_setColUpperBound(int i, Value up) { + _prob->setColumnUpper(i, up == INF ? COIN_DBL_MAX : up); + } + + LpClp::Value LpClp::_getColUpperBound(int i) const { + double val = _prob->getColUpper()[i]; + return val == COIN_DBL_MAX ? INF : val; + } + + void LpClp::_setRowLowerBound(int i, Value lo) { + _prob->setRowLower(i, lo == - INF ? - COIN_DBL_MAX : lo); + } + + LpClp::Value LpClp::_getRowLowerBound(int i) const { + double val = _prob->getRowLower()[i]; + return val == - COIN_DBL_MAX ? - INF : val; + } + + void LpClp::_setRowUpperBound(int i, Value up) { + _prob->setRowUpper(i, up == INF ? COIN_DBL_MAX : up); + } + + LpClp::Value LpClp::_getRowUpperBound(int i) const { + double val = _prob->getRowUpper()[i]; + return val == COIN_DBL_MAX ? INF : val; + } + + void LpClp::_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 LpClp::_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 LpClp::_setObjCoeff(int i, Value obj_coef) { + _prob->setObjectiveCoefficient(i, obj_coef); + } + + LpClp::Value LpClp::_getObjCoeff(int i) const { + return _prob->getObjCoefficients()[i]; + } + + LpClp::SolveExitStatus LpClp::_solve() { + return _prob->primal() >= 0 ? SOLVED : UNSOLVED; + } + + LpClp::SolveExitStatus LpClp::solvePrimal() { + return _prob->primal() >= 0 ? SOLVED : UNSOLVED; + } + + LpClp::SolveExitStatus LpClp::solveDual() { + return _prob->dual() >= 0 ? SOLVED : UNSOLVED; + } + + LpClp::SolveExitStatus LpClp::solveBarrier() { + return _prob->barrier() >= 0 ? SOLVED : UNSOLVED; + } + + LpClp::Value LpClp::_getPrimal(int i) const { + return _prob->primalColumnSolution()[i]; + } + LpClp::Value LpClp::_getPrimalValue() const { + return _prob->objectiveValue(); + } + + LpClp::Value LpClp::_getDual(int i) const { + return _prob->dualRowSolution()[i]; + } + + LpClp::Value LpClp::_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]; + } + + LpClp::Value LpClp::_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]; + } + + LpClp::VarStatus LpClp::_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(); + } + } + + LpClp::VarStatus LpClp::_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(); + } + } + + + LpClp::ProblemType LpClp::_getPrimalType() const { + if (_prob->isProvenOptimal()) { + return OPTIMAL; + } else if (_prob->isProvenPrimalInfeasible()) { + return INFEASIBLE; + } else if (_prob->isProvenDualInfeasible()) { + return UNBOUNDED; + } else { + return UNDEFINED; + } + } + + LpClp::ProblemType LpClp::_getDualType() const { + if (_prob->isProvenOptimal()) { + return OPTIMAL; + } else if (_prob->isProvenDualInfeasible()) { + return INFEASIBLE; + } else if (_prob->isProvenPrimalInfeasible()) { + return INFEASIBLE; + } else { + return UNDEFINED; + } + } + + void LpClp::_setSense(LpClp::Sense sense) { + switch (sense) { + case MIN: + _prob->setOptimizationDirection(1); + break; + case MAX: + _prob->setOptimizationDirection(-1); + break; + } + } + + LpClp::Sense LpClp::_getSense() const { + double dir = _prob->optimizationDirection(); + if (dir > 0.0) { + return MIN; + } else { + return MAX; + } + } + + void LpClp::_clear() { + delete _prob; + _prob = new ClpSimplex(); + rows.clear(); + cols.clear(); + _col_names_ref.clear(); + _clear_temporals(); + } + + void LpClp::messageLevel(MessageLevel m) { + _prob->setLogLevel(static_cast(m)); + } + +} //END OF NAMESPACE LEMON diff --git a/lemon/clp.h b/lemon/clp.h new file mode 100644 --- /dev/null +++ b/lemon/clp.h @@ -0,0 +1,179 @@ +/* -*- 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 +#include + +#include + +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 LpClp : public LpSolver { + protected: + + ClpSimplex* _prob; + + std::map _col_names_ref; + std::map _row_names_ref; + + public: + + /// \e + LpClp(); + /// \e + LpClp(const LpClp&); + /// \e + ~LpClp(); + + protected: + + mutable double* _primal_ray; + mutable double* _dual_ray; + + void _init_temporals(); + void _clear_temporals(); + + protected: + + virtual LpClp* _newSolver() const; + virtual LpClp* _cloneSolver() const; + + virtual const char* _solverName() const; + + virtual int _addCol(); + virtual int _addRow(); + + virtual void _eraseCol(int i); + virtual void _eraseRow(int i); + + virtual void _eraseColId(int i); + virtual void _eraseRowId(int i); + + virtual void _getColName(int col, std::string& name) const; + virtual void _setColName(int col, const std::string& name); + virtual int _colByName(const std::string& name) const; + + virtual void _getRowName(int row, std::string& name) const; + virtual void _setRowName(int row, const std::string& name); + virtual int _rowByName(const std::string& name) const; + + virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e); + virtual void _getRowCoeffs(int i, InsertIterator b) const; + + virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e); + virtual void _getColCoeffs(int i, InsertIterator b) const; + + virtual void _setCoeff(int row, int col, Value value); + virtual Value _getCoeff(int row, int col) const; + + virtual void _setColLowerBound(int i, Value value); + virtual Value _getColLowerBound(int i) const; + virtual void _setColUpperBound(int i, Value value); + virtual Value _getColUpperBound(int i) const; + + virtual void _setRowLowerBound(int i, Value value); + virtual Value _getRowLowerBound(int i) const; + virtual void _setRowUpperBound(int i, Value value); + virtual Value _getRowUpperBound(int i) const; + + virtual void _setObjCoeffs(ExprIterator, 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(); + + 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)); } + + ///Enum for \c messageLevel() parameter + enum MessageLevel { + /// no output (default value) + MESSAGE_NO_OUTPUT = 0, + /// print final solution + MESSAGE_FINAL_SOLUTION = 1, + /// print factorization + MESSAGE_FACTORIZATION = 2, + /// normal output + MESSAGE_NORMAL_OUTPUT = 3, + /// verbose output + MESSAGE_VERBOSE_OUTPUT = 4 + }; + ///Set the verbosity of the messages + + ///Set the verbosity of the messages + /// + ///\param m is the level of the messages output by the solver routines. + void messageLevel(MessageLevel m); + + }; + +} //END OF NAMESPACE LEMON + +#endif //LEMON_CLP_H + diff --git a/lemon/cplex.cc b/lemon/cplex.cc new file mode 100644 --- /dev/null +++ b/lemon/cplex.cc @@ -0,0 +1,925 @@ +/* -*- 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 +#include +#include + +#include + +extern "C" { +#include +} + + +///\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"); + } + + CplexBase::CplexBase(const CplexEnv& env) + : LpBase(), _env(env) { + int status; + _prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem"); + } + + CplexBase::CplexBase(const CplexBase& cplex) + : LpBase() { + int status; + _prob = CPXcloneprob(cplexEnv(), cplex._prob, &status); + rows = cplex.rows; + cols = cplex.cols; + } + + 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; + } + + + 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 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(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(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 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(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(name.c_str()), &index) == 0) { + return index; + } + return -1; + } + + void CplexBase::_setRowCoeffs(int i, ExprIterator b, + ExprIterator e) + { + std::vector indices; + std::vector rowlist; + std::vector 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 indices(length); + std::vector 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 indices; + std::vector collist; + std::vector 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 indices(length); + std::vector 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 indices; + std::vector 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 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(); + } + + // LpCplex members + + LpCplex::LpCplex() + : LpBase(), CplexBase(), LpSolver() {} + + LpCplex::LpCplex(const CplexEnv& env) + : LpBase(), CplexBase(env), LpSolver() {} + + LpCplex::LpCplex(const LpCplex& other) + : LpBase(), CplexBase(other), LpSolver() {} + + LpCplex::~LpCplex() {} + + LpCplex* LpCplex::_newSolver() const { return new LpCplex; } + LpCplex* LpCplex::_cloneSolver() const {return new LpCplex(*this); } + + const char* LpCplex::_solverName() const { return "LpCplex"; } + + void LpCplex::_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. + LpCplex::SolveExitStatus LpCplex::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 + } + + LpCplex::SolveExitStatus LpCplex::_solve() { + _clear_temporals(); + return convertStatus(CPXlpopt(cplexEnv(), _prob)); + } + + LpCplex::SolveExitStatus LpCplex::solvePrimal() { + _clear_temporals(); + return convertStatus(CPXprimopt(cplexEnv(), _prob)); + } + + LpCplex::SolveExitStatus LpCplex::solveDual() { + _clear_temporals(); + return convertStatus(CPXdualopt(cplexEnv(), _prob)); + } + + LpCplex::SolveExitStatus LpCplex::solveBarrier() { + _clear_temporals(); + return convertStatus(CPXbaropt(cplexEnv(), _prob)); + } + + LpCplex::Value LpCplex::_getPrimal(int i) const { + Value x; + CPXgetx(cplexEnv(), _prob, &x, i, i); + return x; + } + + LpCplex::Value LpCplex::_getDual(int i) const { + Value y; + CPXgetpi(cplexEnv(), _prob, &y, i, i); + return y; + } + + LpCplex::Value LpCplex::_getPrimalValue() const { + Value objval; + CPXgetobjval(cplexEnv(), _prob, &objval); + return objval; + } + + LpCplex::VarStatus LpCplex::_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 LpCplex::VarStatus(); + } + } + + LpCplex::VarStatus LpCplex::_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 LpCplex::VarStatus(); + } + } + + LpCplex::Value LpCplex::_getPrimalRay(int i) const { + if (_primal_ray.empty()) { + _primal_ray.resize(CPXgetnumcols(cplexEnv(), _prob)); + CPXgetray(cplexEnv(), _prob, &_primal_ray.front()); + } + return _primal_ray[i]; + } + + LpCplex::Value LpCplex::_getDualRay(int i) const { + if (_dual_ray.empty()) { + + } + return _dual_ray[i]; + } + + //7.5-os cplex statusai (Vigyazat: a 9.0-asei masok!) + // This table lists the statuses, returned by the CPXgetstat() + // routine, for solutions to LP problems or mixed integer problems. If + // no solution exists, the return value is zero. + + // For Simplex, Barrier + // 1 CPX_OPTIMAL + // Optimal solution found + // 2 CPX_INFEASIBLE + // Problem infeasible + // 3 CPX_UNBOUNDED + // Problem unbounded + // 4 CPX_OBJ_LIM + // Objective limit exceeded in Phase II + // 5 CPX_IT_LIM_FEAS + // Iteration limit exceeded in Phase II + // 6 CPX_IT_LIM_INFEAS + // Iteration limit exceeded in Phase I + // 7 CPX_TIME_LIM_FEAS + // Time limit exceeded in Phase II + // 8 CPX_TIME_LIM_INFEAS + // Time limit exceeded in Phase I + // 9 CPX_NUM_BEST_FEAS + // Problem non-optimal, singularities in Phase II + // 10 CPX_NUM_BEST_INFEAS + // Problem non-optimal, singularities in Phase I + // 11 CPX_OPTIMAL_INFEAS + // Optimal solution found, unscaled infeasibilities + // 12 CPX_ABORT_FEAS + // Aborted in Phase II + // 13 CPX_ABORT_INFEAS + // Aborted in Phase I + // 14 CPX_ABORT_DUAL_INFEAS + // Aborted in barrier, dual infeasible + // 15 CPX_ABORT_PRIM_INFEAS + // Aborted in barrier, primal infeasible + // 16 CPX_ABORT_PRIM_DUAL_INFEAS + // Aborted in barrier, primal and dual infeasible + // 17 CPX_ABORT_PRIM_DUAL_FEAS + // Aborted in barrier, primal and dual feasible + // 18 CPX_ABORT_CROSSOVER + // Aborted in crossover + // 19 CPX_INForUNBD + // Infeasible or unbounded + // 20 CPX_PIVOT + // User pivot used + // + // Ezeket hova tegyem: + // ??case CPX_ABORT_DUAL_INFEAS + // ??case CPX_ABORT_CROSSOVER + // ??case CPX_INForUNBD + // ??case CPX_PIVOT + + //Some more interesting stuff: + + // CPX_PARAM_PROBMETHOD 1062 int LPMETHOD + // 0 Automatic + // 1 Primal Simplex + // 2 Dual Simplex + // 3 Network Simplex + // 4 Standard Barrier + // Default: 0 + // Description: Method for linear optimization. + // Determines which algorithm is used when CPXlpopt() (or "optimize" + // in the Interactive Optimizer) is called. Currently the behavior of + // the "Automatic" setting is that CPLEX simply invokes the dual + // simplex method, but this capability may be expanded in the future + // so that CPLEX chooses the method based on problem characteristics +#if CPX_VERSION < 900 + void statusSwitch(CPXENVptr cplexEnv(),int& stat){ + int lpmethod; + CPXgetintparam (cplexEnv(),CPX_PARAM_PROBMETHOD,&lpmethod); + if (lpmethod==2){ + if (stat==CPX_UNBOUNDED){ + stat=CPX_INFEASIBLE; + } + else{ + if (stat==CPX_INFEASIBLE) + stat=CPX_UNBOUNDED; + } + } + } +#else + void statusSwitch(CPXENVptr,int&){} +#endif + + LpCplex::ProblemType LpCplex::_getPrimalType() const { + // Unboundedness not treated well: the following is from cplex 9.0 doc + // About Unboundedness + + // The treatment of models that are unbounded involves a few + // subtleties. Specifically, a declaration of unboundedness means that + // ILOG CPLEX has determined that the model has an unbounded + // ray. Given any feasible solution x with objective z, a multiple of + // the unbounded ray can be added to x to give a feasible solution + // with objective z-1 (or z+1 for maximization models). Thus, if a + // feasible solution exists, then the optimal objective is + // unbounded. Note that ILOG CPLEX has not necessarily concluded that + // a feasible solution exists. Users can call the routine CPXsolninfo + // to determine whether ILOG CPLEX has also concluded that the model + // has a feasible solution. + + int stat = CPXgetstat(cplexEnv(), _prob); +#if CPX_VERSION >= 800 + switch (stat) + { + case CPX_STAT_OPTIMAL: + return OPTIMAL; + case CPX_STAT_UNBOUNDED: + return UNBOUNDED; + case CPX_STAT_INFEASIBLE: + return INFEASIBLE; + default: + return UNDEFINED; + } +#else + statusSwitch(cplexEnv(),stat); + //CPXgetstat(cplexEnv(), _prob); + //printf("A primal status: %d, CPX_OPTIMAL=%d \n",stat,CPX_OPTIMAL); + switch (stat) { + case 0: + return UNDEFINED; //Undefined + case CPX_OPTIMAL://Optimal + return OPTIMAL; + case CPX_UNBOUNDED://Unbounded + return INFEASIBLE;//In case of dual simplex + //return UNBOUNDED; + case CPX_INFEASIBLE://Infeasible + // case CPX_IT_LIM_INFEAS: + // case CPX_TIME_LIM_INFEAS: + // case CPX_NUM_BEST_INFEAS: + // case CPX_OPTIMAL_INFEAS: + // case CPX_ABORT_INFEAS: + // case CPX_ABORT_PRIM_INFEAS: + // case CPX_ABORT_PRIM_DUAL_INFEAS: + return UNBOUNDED;//In case of dual simplex + //return INFEASIBLE; + // case CPX_OBJ_LIM: + // case CPX_IT_LIM_FEAS: + // case CPX_TIME_LIM_FEAS: + // case CPX_NUM_BEST_FEAS: + // case CPX_ABORT_FEAS: + // case CPX_ABORT_PRIM_DUAL_FEAS: + // return FEASIBLE; + default: + return UNDEFINED; //Everything else comes here + //FIXME error + } +#endif + } + + //9.0-as cplex verzio statusai + // CPX_STAT_ABORT_DUAL_OBJ_LIM + // CPX_STAT_ABORT_IT_LIM + // CPX_STAT_ABORT_OBJ_LIM + // CPX_STAT_ABORT_PRIM_OBJ_LIM + // CPX_STAT_ABORT_TIME_LIM + // CPX_STAT_ABORT_USER + // CPX_STAT_FEASIBLE_RELAXED + // CPX_STAT_INFEASIBLE + // CPX_STAT_INForUNBD + // CPX_STAT_NUM_BEST + // CPX_STAT_OPTIMAL + // CPX_STAT_OPTIMAL_FACE_UNBOUNDED + // CPX_STAT_OPTIMAL_INFEAS + // CPX_STAT_OPTIMAL_RELAXED + // CPX_STAT_UNBOUNDED + + LpCplex::ProblemType LpCplex::_getDualType() const { + int stat = CPXgetstat(cplexEnv(), _prob); +#if CPX_VERSION >= 800 + switch (stat) { + case CPX_STAT_OPTIMAL: + return OPTIMAL; + case CPX_STAT_UNBOUNDED: + return INFEASIBLE; + default: + return UNDEFINED; + } +#else + statusSwitch(cplexEnv(),stat); + switch (stat) { + case 0: + return UNDEFINED; //Undefined + case CPX_OPTIMAL://Optimal + return OPTIMAL; + case CPX_UNBOUNDED: + return INFEASIBLE; + default: + return UNDEFINED; //Everything else comes here + //FIXME error + } +#endif + } + + // MipCplex members + + MipCplex::MipCplex() + : LpBase(), CplexBase(), MipSolver() { + +#if CPX_VERSION < 800 + CPXchgprobtype(cplexEnv(), _prob, CPXPROB_MIP); +#else + CPXchgprobtype(cplexEnv(), _prob, CPXPROB_MILP); +#endif + } + + MipCplex::MipCplex(const CplexEnv& env) + : LpBase(), CplexBase(env), MipSolver() { + +#if CPX_VERSION < 800 + CPXchgprobtype(cplexEnv(), _prob, CPXPROB_MIP); +#else + CPXchgprobtype(cplexEnv(), _prob, CPXPROB_MILP); +#endif + + } + + MipCplex::MipCplex(const MipCplex& other) + : LpBase(), CplexBase(other), MipSolver() {} + + MipCplex::~MipCplex() {} + + MipCplex* MipCplex::_newSolver() const { return new MipCplex; } + MipCplex* MipCplex::_cloneSolver() const {return new MipCplex(*this); } + + const char* MipCplex::_solverName() const { return "MipCplex"; } + + void MipCplex::_setColType(int i, MipCplex::ColTypes col_type) { + + // Note If a variable is to be changed to binary, a call to CPXchgbds + // should also be made to change the bounds to 0 and 1. + + switch (col_type){ + case INTEGER: { + const char t = 'I'; + CPXchgctype (cplexEnv(), _prob, 1, &i, &t); + } break; + case REAL: { + const char t = 'C'; + CPXchgctype (cplexEnv(), _prob, 1, &i, &t); + } break; + default: + break; + } + } + + MipCplex::ColTypes MipCplex::_getColType(int i) const { + char t; + CPXgetctype (cplexEnv(), _prob, &t, i, i); + switch (t) { + case 'I': + return INTEGER; + case 'C': + return REAL; + default: + LEMON_ASSERT(false, "Invalid column type"); + return ColTypes(); + } + + } + + MipCplex::SolveExitStatus MipCplex::_solve() { + int status; + status = CPXmipopt (cplexEnv(), _prob); + if (status==0) + return SOLVED; + else + return UNSOLVED; + + } + + + MipCplex::ProblemType MipCplex::_getType() const { + + int stat = CPXgetstat(cplexEnv(), _prob); + + //Fortunately, MIP statuses did not change for cplex 8.0 + switch (stat) { + case CPXMIP_OPTIMAL: + // Optimal integer solution has been found. + case CPXMIP_OPTIMAL_TOL: + // Optimal soluton with the tolerance defined by epgap or epagap has + // been found. + return OPTIMAL; + //This also exists in later issues + // case CPXMIP_UNBOUNDED: + //return UNBOUNDED; + case CPXMIP_INFEASIBLE: + return INFEASIBLE; + default: + return UNDEFINED; + } + //Unboundedness not treated well: the following is from cplex 9.0 doc + // About Unboundedness + + // The treatment of models that are unbounded involves a few + // subtleties. Specifically, a declaration of unboundedness means that + // ILOG CPLEX has determined that the model has an unbounded + // ray. Given any feasible solution x with objective z, a multiple of + // the unbounded ray can be added to x to give a feasible solution + // with objective z-1 (or z+1 for maximization models). Thus, if a + // feasible solution exists, then the optimal objective is + // unbounded. Note that ILOG CPLEX has not necessarily concluded that + // a feasible solution exists. Users can call the routine CPXsolninfo + // to determine whether ILOG CPLEX has also concluded that the model + // has a feasible solution. + } + + MipCplex::Value MipCplex::_getSol(int i) const { + Value x; + CPXgetmipx(cplexEnv(), _prob, &x, i, i); + return x; + } + + MipCplex::Value MipCplex::_getSolValue() const { + Value objval; + CPXgetmipobjval(cplexEnv(), _prob, &objval); + return objval; + } + +} //namespace lemon + diff --git a/lemon/cplex.h b/lemon/cplex.h new file mode 100644 --- /dev/null +++ b/lemon/cplex.h @@ -0,0 +1,256 @@ +/* -*- 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_CPLEX_H +#define LEMON_CPLEX_H + +///\file +///\brief Header of the LEMON-CPLEX lp solver interface. + +#include + +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 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(); + + public: + + /// Returns the used \c CplexEnv instance + const CplexEnv& env() const { return _env; } + /// + const cpxenv* cplexEnv() const { return _env.cplexEnv(); } + + cpxlp* cplexLp() { return _prob; } + 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 LpCplex : public CplexBase, public LpSolver { + public: + /// \e + LpCplex(); + /// \e + LpCplex(const CplexEnv&); + /// \e + LpCplex(const LpCplex&); + /// \e + virtual ~LpCplex(); + + private: + + // these values cannot retrieved element by element + mutable std::vector _col_status; + mutable std::vector _row_status; + + mutable std::vector _primal_ray; + mutable std::vector _dual_ray; + + void _clear_temporals(); + + SolveExitStatus convertStatus(int status); + + protected: + + virtual LpCplex* _cloneSolver() const; + virtual LpCplex* _newSolver() const; + + 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 MipCplex : public CplexBase, public MipSolver { + public: + /// \e + MipCplex(); + /// \e + MipCplex(const CplexEnv&); + /// \e + MipCplex(const MipCplex&); + /// \e + virtual ~MipCplex(); + + protected: + + virtual MipCplex* _cloneSolver() const; + virtual MipCplex* _newSolver() const; + + 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 + diff --git a/lemon/glpk.cc b/lemon/glpk.cc new file mode 100644 --- /dev/null +++ b/lemon/glpk.cc @@ -0,0 +1,952 @@ +/* -*- 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. + * + */ + +///\file +///\brief Implementation of the LEMON GLPK LP and MIP solver interface. + +#include +#include + +#include + +namespace lemon { + + // GlpkBase members + + GlpkBase::GlpkBase() : LpBase() { + lp = glp_create_prob(); + glp_create_index(lp); + } + + 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; + } + + 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; + } + + 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(name.c_str())); + + } + + int GlpkBase::_colByName(const std::string& name) const { + int k = glp_find_col(lp, const_cast(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(name.c_str())); + + } + + int GlpkBase::_rowByName(const std::string& name) const { + int k = glp_find_row(lp, const_cast(name.c_str())); + return k > 0 ? k : -1; + } + + void GlpkBase::_setRowCoeffs(int i, ExprIterator b, ExprIterator e) { + std::vector indexes; + std::vector 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 indexes(length + 1); + std::vector 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 indexes; + std::vector 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 indexes(length + 1); + std::vector 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 indexes(length + 2); + std::vector 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 indexes(length + 2); + std::vector 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 indexes(length + 1); + std::vector 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(); + } + + // LpGlpk members + + LpGlpk::LpGlpk() + : LpBase(), GlpkBase(), LpSolver() { + messageLevel(MESSAGE_NO_OUTPUT); + } + + LpGlpk::LpGlpk(const LpGlpk& other) + : LpBase(other), GlpkBase(other), LpSolver(other) { + messageLevel(MESSAGE_NO_OUTPUT); + } + + LpGlpk* LpGlpk::_newSolver() const { return new LpGlpk; } + LpGlpk* LpGlpk::_cloneSolver() const { return new LpGlpk(*this); } + + const char* LpGlpk::_solverName() const { return "LpGlpk"; } + + void LpGlpk::_clear_temporals() { + _primal_ray.clear(); + _dual_ray.clear(); + } + + LpGlpk::SolveExitStatus LpGlpk::_solve() { + return solvePrimal(); + } + + LpGlpk::SolveExitStatus LpGlpk::solvePrimal() { + _clear_temporals(); + + glp_smcp smcp; + glp_init_smcp(&smcp); + + switch (_message_level) { + case MESSAGE_NO_OUTPUT: + smcp.msg_lev = GLP_MSG_OFF; + break; + case MESSAGE_ERROR_MESSAGE: + smcp.msg_lev = GLP_MSG_ERR; + break; + case MESSAGE_NORMAL_OUTPUT: + smcp.msg_lev = GLP_MSG_ON; + break; + case MESSAGE_FULL_OUTPUT: + smcp.msg_lev = GLP_MSG_ALL; + break; + } + + if (glp_simplex(lp, &smcp) != 0) return UNSOLVED; + return SOLVED; + } + + LpGlpk::SolveExitStatus LpGlpk::solveDual() { + _clear_temporals(); + + glp_smcp smcp; + glp_init_smcp(&smcp); + + switch (_message_level) { + case MESSAGE_NO_OUTPUT: + smcp.msg_lev = GLP_MSG_OFF; + break; + case MESSAGE_ERROR_MESSAGE: + smcp.msg_lev = GLP_MSG_ERR; + break; + case MESSAGE_NORMAL_OUTPUT: + smcp.msg_lev = GLP_MSG_ON; + break; + case MESSAGE_FULL_OUTPUT: + smcp.msg_lev = GLP_MSG_ALL; + break; + } + smcp.meth = GLP_DUAL; + + if (glp_simplex(lp, &smcp) != 0) return UNSOLVED; + return SOLVED; + } + + LpGlpk::Value LpGlpk::_getPrimal(int i) const { + return glp_get_col_prim(lp, i); + } + + LpGlpk::Value LpGlpk::_getDual(int i) const { + return glp_get_row_dual(lp, i); + } + + LpGlpk::Value LpGlpk::_getPrimalValue() const { + return glp_get_obj_val(lp); + } + + LpGlpk::VarStatus LpGlpk::_getColStatus(int i) const { + switch (glp_get_col_stat(lp, i)) { + case GLP_BS: + return BASIC; + case GLP_UP: + return UPPER; + case GLP_LO: + return LOWER; + case GLP_NF: + return FREE; + case GLP_NS: + return FIXED; + default: + LEMON_ASSERT(false, "Wrong column status"); + return LpGlpk::VarStatus(); + } + } + + LpGlpk::VarStatus LpGlpk::_getRowStatus(int i) const { + switch (glp_get_row_stat(lp, i)) { + case GLP_BS: + return BASIC; + case GLP_UP: + return UPPER; + case GLP_LO: + return LOWER; + case GLP_NF: + return FREE; + case GLP_NS: + return FIXED; + default: + LEMON_ASSERT(false, "Wrong row status"); + return LpGlpk::VarStatus(); + } + } + + LpGlpk::Value LpGlpk::_getPrimalRay(int i) const { + if (_primal_ray.empty()) { + int row_num = glp_get_num_rows(lp); + int col_num = glp_get_num_cols(lp); + + _primal_ray.resize(col_num + 1, 0.0); + + int index = glp_get_unbnd_ray(lp); + if (index != 0) { + // The primal ray is found in primal simplex second phase + LEMON_ASSERT((index <= row_num ? glp_get_row_stat(lp, index) : + glp_get_col_stat(lp, index - row_num)) != GLP_BS, + "Wrong primal ray"); + + bool negate = glp_get_obj_dir(lp) == GLP_MAX; + + if (index > row_num) { + _primal_ray[index - row_num] = 1.0; + if (glp_get_col_dual(lp, index - row_num) > 0) { + negate = !negate; + } + } else { + if (glp_get_row_dual(lp, index) > 0) { + negate = !negate; + } + } + + std::vector ray_indexes(row_num + 1); + std::vector ray_values(row_num + 1); + int ray_length = glp_eval_tab_col(lp, index, &ray_indexes.front(), + &ray_values.front()); + + for (int i = 1; i <= ray_length; ++i) { + if (ray_indexes[i] > row_num) { + _primal_ray[ray_indexes[i] - row_num] = ray_values[i]; + } + } + + if (negate) { + for (int i = 1; i <= col_num; ++i) { + _primal_ray[i] = - _primal_ray[i]; + } + } + } else { + for (int i = 1; i <= col_num; ++i) { + _primal_ray[i] = glp_get_col_prim(lp, i); + } + } + } + return _primal_ray[i]; + } + + LpGlpk::Value LpGlpk::_getDualRay(int i) const { + if (_dual_ray.empty()) { + int row_num = glp_get_num_rows(lp); + + _dual_ray.resize(row_num + 1, 0.0); + + int index = glp_get_unbnd_ray(lp); + if (index != 0) { + // The dual ray is found in dual simplex second phase + LEMON_ASSERT((index <= row_num ? glp_get_row_stat(lp, index) : + glp_get_col_stat(lp, index - row_num)) == GLP_BS, + + "Wrong dual ray"); + + int idx; + bool negate = false; + + if (index > row_num) { + idx = glp_get_col_bind(lp, index - row_num); + if (glp_get_col_prim(lp, index - row_num) > + glp_get_col_ub(lp, index - row_num)) { + negate = true; + } + } else { + idx = glp_get_row_bind(lp, index); + if (glp_get_row_prim(lp, index) > glp_get_row_ub(lp, index)) { + negate = true; + } + } + + _dual_ray[idx] = negate ? - 1.0 : 1.0; + + glp_btran(lp, &_dual_ray.front()); + } else { + double eps = 1e-7; + // The dual ray is found in primal simplex first phase + // We assume that the glpk minimizes the slack to get feasible solution + for (int i = 1; i <= row_num; ++i) { + int index = glp_get_bhead(lp, i); + if (index <= row_num) { + double res = glp_get_row_prim(lp, index); + if (res > glp_get_row_ub(lp, index) + eps) { + _dual_ray[i] = -1; + } else if (res < glp_get_row_lb(lp, index) - eps) { + _dual_ray[i] = 1; + } else { + _dual_ray[i] = 0; + } + _dual_ray[i] *= glp_get_rii(lp, index); + } else { + double res = glp_get_col_prim(lp, index - row_num); + if (res > glp_get_col_ub(lp, index - row_num) + eps) { + _dual_ray[i] = -1; + } else if (res < glp_get_col_lb(lp, index - row_num) - eps) { + _dual_ray[i] = 1; + } else { + _dual_ray[i] = 0; + } + _dual_ray[i] /= glp_get_sjj(lp, index - row_num); + } + } + + glp_btran(lp, &_dual_ray.front()); + + for (int i = 1; i <= row_num; ++i) { + _dual_ray[i] /= glp_get_rii(lp, i); + } + } + } + return _dual_ray[i]; + } + + LpGlpk::ProblemType LpGlpk::_getPrimalType() const { + if (glp_get_status(lp) == GLP_OPT) + return OPTIMAL; + switch (glp_get_prim_stat(lp)) { + case GLP_UNDEF: + return UNDEFINED; + case GLP_FEAS: + case GLP_INFEAS: + if (glp_get_dual_stat(lp) == GLP_NOFEAS) { + return UNBOUNDED; + } else { + return UNDEFINED; + } + case GLP_NOFEAS: + return INFEASIBLE; + default: + LEMON_ASSERT(false, "Wrong primal type"); + return LpGlpk::ProblemType(); + } + } + + LpGlpk::ProblemType LpGlpk::_getDualType() const { + if (glp_get_status(lp) == GLP_OPT) + return OPTIMAL; + switch (glp_get_dual_stat(lp)) { + case GLP_UNDEF: + return UNDEFINED; + case GLP_FEAS: + case GLP_INFEAS: + if (glp_get_prim_stat(lp) == GLP_NOFEAS) { + return UNBOUNDED; + } else { + return UNDEFINED; + } + case GLP_NOFEAS: + return INFEASIBLE; + default: + LEMON_ASSERT(false, "Wrong primal type"); + return LpGlpk::ProblemType(); + } + } + + void LpGlpk::presolver(bool b) { + lpx_set_int_parm(lp, LPX_K_PRESOL, b ? 1 : 0); + } + + void LpGlpk::messageLevel(MessageLevel m) { + _message_level = m; + } + + // MipGlpk members + + MipGlpk::MipGlpk() + : LpBase(), GlpkBase(), MipSolver() { + messageLevel(MESSAGE_NO_OUTPUT); + } + + MipGlpk::MipGlpk(const MipGlpk& other) + : LpBase(), GlpkBase(other), MipSolver() { + messageLevel(MESSAGE_NO_OUTPUT); + } + + void MipGlpk::_setColType(int i, MipGlpk::ColTypes col_type) { + switch (col_type) { + case INTEGER: + glp_set_col_kind(lp, i, GLP_IV); + break; + case REAL: + glp_set_col_kind(lp, i, GLP_CV); + break; + } + } + + MipGlpk::ColTypes MipGlpk::_getColType(int i) const { + switch (glp_get_col_kind(lp, i)) { + case GLP_IV: + case GLP_BV: + return INTEGER; + default: + return REAL; + } + + } + + MipGlpk::SolveExitStatus MipGlpk::_solve() { + glp_smcp smcp; + glp_init_smcp(&smcp); + + switch (_message_level) { + case MESSAGE_NO_OUTPUT: + smcp.msg_lev = GLP_MSG_OFF; + break; + case MESSAGE_ERROR_MESSAGE: + smcp.msg_lev = GLP_MSG_ERR; + break; + case MESSAGE_NORMAL_OUTPUT: + smcp.msg_lev = GLP_MSG_ON; + break; + case MESSAGE_FULL_OUTPUT: + smcp.msg_lev = GLP_MSG_ALL; + break; + } + smcp.meth = GLP_DUAL; + + if (glp_simplex(lp, &smcp) != 0) return UNSOLVED; + if (glp_get_status(lp) != GLP_OPT) return SOLVED; + + glp_iocp iocp; + glp_init_iocp(&iocp); + + switch (_message_level) { + case MESSAGE_NO_OUTPUT: + iocp.msg_lev = GLP_MSG_OFF; + break; + case MESSAGE_ERROR_MESSAGE: + iocp.msg_lev = GLP_MSG_ERR; + break; + case MESSAGE_NORMAL_OUTPUT: + iocp.msg_lev = GLP_MSG_ON; + break; + case MESSAGE_FULL_OUTPUT: + iocp.msg_lev = GLP_MSG_ALL; + break; + } + + if (glp_intopt(lp, &iocp) != 0) return UNSOLVED; + return SOLVED; + } + + + MipGlpk::ProblemType MipGlpk::_getType() const { + switch (glp_get_status(lp)) { + case GLP_OPT: + switch (glp_mip_status(lp)) { + case GLP_UNDEF: + return UNDEFINED; + case GLP_NOFEAS: + return INFEASIBLE; + case GLP_FEAS: + return FEASIBLE; + case GLP_OPT: + return OPTIMAL; + default: + LEMON_ASSERT(false, "Wrong problem type."); + return MipGlpk::ProblemType(); + } + case GLP_NOFEAS: + return INFEASIBLE; + case GLP_INFEAS: + case GLP_FEAS: + if (glp_get_dual_stat(lp) == GLP_NOFEAS) { + return UNBOUNDED; + } else { + return UNDEFINED; + } + default: + LEMON_ASSERT(false, "Wrong problem type."); + return MipGlpk::ProblemType(); + } + } + + MipGlpk::Value MipGlpk::_getSol(int i) const { + return glp_mip_col_val(lp, i); + } + + MipGlpk::Value MipGlpk::_getSolValue() const { + return glp_mip_obj_val(lp); + } + + MipGlpk* MipGlpk::_newSolver() const { return new MipGlpk; } + MipGlpk* MipGlpk::_cloneSolver() const {return new MipGlpk(*this); } + + const char* MipGlpk::_solverName() const { return "MipGlpk"; } + + void MipGlpk::messageLevel(MessageLevel m) { + _message_level = m; + } + +} //END OF NAMESPACE LEMON diff --git a/lemon/glpk.h b/lemon/glpk.h new file mode 100644 --- /dev/null +++ b/lemon/glpk.h @@ -0,0 +1,259 @@ +/* -*- 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 + +// forward declaration +#ifndef _GLP_PROB +#define _GLP_PROB +typedef struct { double _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 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(); + + 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 LpGlpk : public GlpkBase, public LpSolver { + public: + + ///\e + LpGlpk(); + ///\e + LpGlpk(const LpGlpk&); + + private: + + mutable std::vector _primal_ray; + mutable std::vector _dual_ray; + + void _clear_temporals(); + + protected: + + virtual LpGlpk* _cloneSolver() const; + virtual LpGlpk* _newSolver() const; + + 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; + + ///\todo It should be clarified + /// + virtual ProblemType _getPrimalType() const; + virtual ProblemType _getDualType() const; + + public: + + ///Solve with primal simplex + SolveExitStatus solvePrimal(); + + ///Solve with dual simplex + SolveExitStatus solveDual(); + + ///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 b); + + ///Enum for \c messageLevel() parameter + enum MessageLevel { + /// no output (default value) + MESSAGE_NO_OUTPUT = 0, + /// error messages only + MESSAGE_ERROR_MESSAGE = 1, + /// normal output + MESSAGE_NORMAL_OUTPUT = 2, + /// full output (includes informational messages) + MESSAGE_FULL_OUTPUT = 3 + }; + + private: + + MessageLevel _message_level; + + public: + + ///Set the verbosity of the messages + + ///Set the verbosity of the messages + /// + ///\param m is the level of the messages output by the solver routines. + void messageLevel(MessageLevel m); + }; + + /// \brief Interface for the GLPK MIP solver + /// + /// This class implements an interface for the GLPK MIP solver. + ///\ingroup lp_group + class MipGlpk : public GlpkBase, public MipSolver { + public: + + ///\e + MipGlpk(); + ///\e + MipGlpk(const MipGlpk&); + + protected: + + virtual MipGlpk* _cloneSolver() const; + virtual MipGlpk* _newSolver() const; + + 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; + + ///Enum for \c messageLevel() parameter + enum MessageLevel { + /// no output (default value) + MESSAGE_NO_OUTPUT = 0, + /// error messages only + MESSAGE_ERROR_MESSAGE = 1, + /// normal output + MESSAGE_NORMAL_OUTPUT = 2, + /// full output (includes informational messages) + MESSAGE_FULL_OUTPUT = 3 + }; + + private: + + MessageLevel _message_level; + + public: + + ///Set the verbosity of the messages + + ///Set the verbosity of the messages + /// + ///\param m is the level of the messages output by the solver routines. + void messageLevel(MessageLevel m); + }; + + +} //END OF NAMESPACE LEMON + +#endif //LEMON_GLPK_H + diff --git a/lemon/lp.h b/lemon/lp.h --- a/lemon/lp.h +++ b/lemon/lp.h @@ -23,13 +23,13 @@ #ifdef HAVE_GLPK -#include +#include #elif HAVE_CPLEX -#include +#include #elif HAVE_SOPLEX -#include +#include #elif HAVE_CLP -#include +#include #endif ///\file @@ -43,8 +43,8 @@ ///The default LP solver identifier. ///\ingroup lp_group /// - ///Currently, the possible values are \c LP_GLPK, \c LP_CPLEX, \c - ///LP_SOPLEX or \c LP_CLP + ///Currently, the possible values are \c GLPK, \c CPLEX, + ///\c SOPLEX or \c CLP #define LEMON_DEFAULT_LP SOLVER ///The default LP solver @@ -59,7 +59,7 @@ ///The default MIP solver identifier. ///\ingroup lp_group /// - ///Currently, the possible values are \c MIP_GLPK or \c MIP_CPLEX + ///Currently, the possible values are \c GLPK or \c CPLEX #define LEMON_DEFAULT_MIP SOLVER ///The default MIP solver. @@ -70,20 +70,20 @@ typedef MipGlpk Mip; #else #ifdef HAVE_GLPK -# define LEMON_DEFAULT_LP LP_GLPK +# define LEMON_DEFAULT_LP GLPK typedef LpGlpk Lp; -# define LEMON_DEFAULT_MIP MIP_GLPK +# define LEMON_DEFAULT_MIP GLPK typedef MipGlpk Mip; #elif HAVE_CPLEX -# define LEMON_DEFAULT_LP LP_CPLEX +# define LEMON_DEFAULT_LP CPLEX typedef LpCplex Lp; -# define LEMON_DEFAULT_MIP MIP_CPLEX +# define LEMON_DEFAULT_MIP CPLEX typedef MipCplex Mip; #elif HAVE_SOPLEX -# define DEFAULT_LP LP_SOPLEX +# define DEFAULT_LP SOPLEX typedef LpSoplex Lp; #elif HAVE_CLP -# define DEFAULT_LP LP_CLP +# define DEFAULT_LP CLP typedef LpClp Lp; #endif #endif diff --git a/lemon/lp_clp.cc b/lemon/lp_clp.cc deleted file mode 100644 --- a/lemon/lp_clp.cc +++ /dev/null @@ -1,437 +0,0 @@ -/* -*- 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 -#include - -namespace lemon { - - LpClp::LpClp() { - _prob = new ClpSimplex(); - _init_temporals(); - messageLevel(MESSAGE_NO_OUTPUT); - } - - LpClp::LpClp(const LpClp& other) { - _prob = new ClpSimplex(*other._prob); - rows = other.rows; - cols = other.cols; - _init_temporals(); - messageLevel(MESSAGE_NO_OUTPUT); - } - - LpClp::~LpClp() { - delete _prob; - _clear_temporals(); - } - - void LpClp::_init_temporals() { - _primal_ray = 0; - _dual_ray = 0; - } - - void LpClp::_clear_temporals() { - if (_primal_ray) { - delete[] _primal_ray; - _primal_ray = 0; - } - if (_dual_ray) { - delete[] _dual_ray; - _dual_ray = 0; - } - } - - LpClp* LpClp::_newSolver() const { - LpClp* newlp = new LpClp; - return newlp; - } - - LpClp* LpClp::_cloneSolver() const { - LpClp* copylp = new LpClp(*this); - return copylp; - } - - const char* LpClp::_solverName() const { return "LpClp"; } - - int LpClp::_addCol() { - _prob->addColumn(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX, 0.0); - return _prob->numberColumns() - 1; - } - - int LpClp::_addRow() { - _prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX); - return _prob->numberRows() - 1; - } - - - void LpClp::_eraseCol(int c) { - _col_names_ref.erase(_prob->getColumnName(c)); - _prob->deleteColumns(1, &c); - } - - void LpClp::_eraseRow(int r) { - _row_names_ref.erase(_prob->getRowName(r)); - _prob->deleteRows(1, &r); - } - - void LpClp::_eraseColId(int i) { - cols.eraseIndex(i); - cols.shiftIndices(i); - } - - void LpClp::_eraseRowId(int i) { - rows.eraseIndex(i); - rows.shiftIndices(i); - } - - void LpClp::_getColName(int c, std::string& name) const { - name = _prob->getColumnName(c); - } - - void LpClp::_setColName(int c, const std::string& name) { - _prob->setColumnName(c, const_cast(name)); - _col_names_ref[name] = c; - } - - int LpClp::_colByName(const std::string& name) const { - std::map::const_iterator it = _col_names_ref.find(name); - return it != _col_names_ref.end() ? it->second : -1; - } - - void LpClp::_getRowName(int r, std::string& name) const { - name = _prob->getRowName(r); - } - - void LpClp::_setRowName(int r, const std::string& name) { - _prob->setRowName(r, const_cast(name)); - _row_names_ref[name] = r; - } - - int LpClp::_rowByName(const std::string& name) const { - std::map::const_iterator it = _row_names_ref.find(name); - return it != _row_names_ref.end() ? it->second : -1; - } - - - void LpClp::_setRowCoeffs(int ix, ExprIterator b, ExprIterator e) { - std::map 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::iterator it = coeffs.begin(); - it != coeffs.end(); ++it) { - _prob->modifyCoefficient(ix, it->first, it->second); - } - } - - void LpClp::_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 LpClp::_setColCoeffs(int ix, ExprIterator b, ExprIterator e) { - std::map 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::iterator it = coeffs.begin(); - it != coeffs.end(); ++it) { - _prob->modifyCoefficient(it->first, ix, it->second); - } - } - - void LpClp::_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 LpClp::_setCoeff(int ix, int jx, Value value) { - _prob->modifyCoefficient(ix, jx, value); - } - - LpClp::Value LpClp::_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 LpClp::_setColLowerBound(int i, Value lo) { - _prob->setColumnLower(i, lo == - INF ? - COIN_DBL_MAX : lo); - } - - LpClp::Value LpClp::_getColLowerBound(int i) const { - double val = _prob->getColLower()[i]; - return val == - COIN_DBL_MAX ? - INF : val; - } - - void LpClp::_setColUpperBound(int i, Value up) { - _prob->setColumnUpper(i, up == INF ? COIN_DBL_MAX : up); - } - - LpClp::Value LpClp::_getColUpperBound(int i) const { - double val = _prob->getColUpper()[i]; - return val == COIN_DBL_MAX ? INF : val; - } - - void LpClp::_setRowLowerBound(int i, Value lo) { - _prob->setRowLower(i, lo == - INF ? - COIN_DBL_MAX : lo); - } - - LpClp::Value LpClp::_getRowLowerBound(int i) const { - double val = _prob->getRowLower()[i]; - return val == - COIN_DBL_MAX ? - INF : val; - } - - void LpClp::_setRowUpperBound(int i, Value up) { - _prob->setRowUpper(i, up == INF ? COIN_DBL_MAX : up); - } - - LpClp::Value LpClp::_getRowUpperBound(int i) const { - double val = _prob->getRowUpper()[i]; - return val == COIN_DBL_MAX ? INF : val; - } - - void LpClp::_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 LpClp::_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 LpClp::_setObjCoeff(int i, Value obj_coef) { - _prob->setObjectiveCoefficient(i, obj_coef); - } - - LpClp::Value LpClp::_getObjCoeff(int i) const { - return _prob->getObjCoefficients()[i]; - } - - LpClp::SolveExitStatus LpClp::_solve() { - return _prob->primal() >= 0 ? SOLVED : UNSOLVED; - } - - LpClp::SolveExitStatus LpClp::solvePrimal() { - return _prob->primal() >= 0 ? SOLVED : UNSOLVED; - } - - LpClp::SolveExitStatus LpClp::solveDual() { - return _prob->dual() >= 0 ? SOLVED : UNSOLVED; - } - - LpClp::SolveExitStatus LpClp::solveBarrier() { - return _prob->barrier() >= 0 ? SOLVED : UNSOLVED; - } - - LpClp::Value LpClp::_getPrimal(int i) const { - return _prob->primalColumnSolution()[i]; - } - LpClp::Value LpClp::_getPrimalValue() const { - return _prob->objectiveValue(); - } - - LpClp::Value LpClp::_getDual(int i) const { - return _prob->dualRowSolution()[i]; - } - - LpClp::Value LpClp::_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]; - } - - LpClp::Value LpClp::_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]; - } - - LpClp::VarStatus LpClp::_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(); - } - } - - LpClp::VarStatus LpClp::_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(); - } - } - - - LpClp::ProblemType LpClp::_getPrimalType() const { - if (_prob->isProvenOptimal()) { - return OPTIMAL; - } else if (_prob->isProvenPrimalInfeasible()) { - return INFEASIBLE; - } else if (_prob->isProvenDualInfeasible()) { - return UNBOUNDED; - } else { - return UNDEFINED; - } - } - - LpClp::ProblemType LpClp::_getDualType() const { - if (_prob->isProvenOptimal()) { - return OPTIMAL; - } else if (_prob->isProvenDualInfeasible()) { - return INFEASIBLE; - } else if (_prob->isProvenPrimalInfeasible()) { - return INFEASIBLE; - } else { - return UNDEFINED; - } - } - - void LpClp::_setSense(LpClp::Sense sense) { - switch (sense) { - case MIN: - _prob->setOptimizationDirection(1); - break; - case MAX: - _prob->setOptimizationDirection(-1); - break; - } - } - - LpClp::Sense LpClp::_getSense() const { - double dir = _prob->optimizationDirection(); - if (dir > 0.0) { - return MIN; - } else { - return MAX; - } - } - - void LpClp::_clear() { - delete _prob; - _prob = new ClpSimplex(); - rows.clear(); - cols.clear(); - _col_names_ref.clear(); - _clear_temporals(); - } - - void LpClp::messageLevel(MessageLevel m) { - _prob->setLogLevel(static_cast(m)); - } - -} //END OF NAMESPACE LEMON diff --git a/lemon/lp_clp.h b/lemon/lp_clp.h deleted file mode 100644 --- a/lemon/lp_clp.h +++ /dev/null @@ -1,179 +0,0 @@ -/* -*- 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_CLP_H -#define LEMON_LP_CLP_H - -///\file -///\brief Header of the LEMON-CLP lp solver interface. - -#include -#include - -#include - -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 LpClp : public LpSolver { - protected: - - ClpSimplex* _prob; - - std::map _col_names_ref; - std::map _row_names_ref; - - public: - - /// \e - LpClp(); - /// \e - LpClp(const LpClp&); - /// \e - ~LpClp(); - - protected: - - mutable double* _primal_ray; - mutable double* _dual_ray; - - void _init_temporals(); - void _clear_temporals(); - - protected: - - virtual LpClp* _newSolver() const; - virtual LpClp* _cloneSolver() const; - - virtual const char* _solverName() const; - - virtual int _addCol(); - virtual int _addRow(); - - virtual void _eraseCol(int i); - virtual void _eraseRow(int i); - - virtual void _eraseColId(int i); - virtual void _eraseRowId(int i); - - virtual void _getColName(int col, std::string& name) const; - virtual void _setColName(int col, const std::string& name); - virtual int _colByName(const std::string& name) const; - - virtual void _getRowName(int row, std::string& name) const; - virtual void _setRowName(int row, const std::string& name); - virtual int _rowByName(const std::string& name) const; - - virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e); - virtual void _getRowCoeffs(int i, InsertIterator b) const; - - virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e); - virtual void _getColCoeffs(int i, InsertIterator b) const; - - virtual void _setCoeff(int row, int col, Value value); - virtual Value _getCoeff(int row, int col) const; - - virtual void _setColLowerBound(int i, Value value); - virtual Value _getColLowerBound(int i) const; - virtual void _setColUpperBound(int i, Value value); - virtual Value _getColUpperBound(int i) const; - - virtual void _setRowLowerBound(int i, Value value); - virtual Value _getRowLowerBound(int i) const; - virtual void _setRowUpperBound(int i, Value value); - virtual Value _getRowUpperBound(int i) const; - - virtual void _setObjCoeffs(ExprIterator, 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(); - - 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)); } - - ///Enum for \c messageLevel() parameter - enum MessageLevel { - /// no output (default value) - MESSAGE_NO_OUTPUT = 0, - /// print final solution - MESSAGE_FINAL_SOLUTION = 1, - /// print factorization - MESSAGE_FACTORIZATION = 2, - /// normal output - MESSAGE_NORMAL_OUTPUT = 3, - /// verbose output - MESSAGE_VERBOSE_OUTPUT = 4 - }; - ///Set the verbosity of the messages - - ///Set the verbosity of the messages - /// - ///\param m is the level of the messages output by the solver routines. - void messageLevel(MessageLevel m); - - }; - -} //END OF NAMESPACE LEMON - -#endif //LEMON_LP_CLP_H - diff --git a/lemon/lp_cplex.cc b/lemon/lp_cplex.cc deleted file mode 100644 --- a/lemon/lp_cplex.cc +++ /dev/null @@ -1,925 +0,0 @@ -/* -*- 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 -#include -#include - -#include - -extern "C" { -#include -} - - -///\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"); - } - - CplexBase::CplexBase(const CplexEnv& env) - : LpBase(), _env(env) { - int status; - _prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem"); - } - - CplexBase::CplexBase(const CplexBase& cplex) - : LpBase() { - int status; - _prob = CPXcloneprob(cplexEnv(), cplex._prob, &status); - rows = cplex.rows; - cols = cplex.cols; - } - - 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; - } - - - 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 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(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(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 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(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(name.c_str()), &index) == 0) { - return index; - } - return -1; - } - - void CplexBase::_setRowCoeffs(int i, ExprIterator b, - ExprIterator e) - { - std::vector indices; - std::vector rowlist; - std::vector 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 indices(length); - std::vector 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 indices; - std::vector collist; - std::vector 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 indices(length); - std::vector 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 indices; - std::vector 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 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(); - } - - // LpCplex members - - LpCplex::LpCplex() - : LpBase(), CplexBase(), LpSolver() {} - - LpCplex::LpCplex(const CplexEnv& env) - : LpBase(), CplexBase(env), LpSolver() {} - - LpCplex::LpCplex(const LpCplex& other) - : LpBase(), CplexBase(other), LpSolver() {} - - LpCplex::~LpCplex() {} - - LpCplex* LpCplex::_newSolver() const { return new LpCplex; } - LpCplex* LpCplex::_cloneSolver() const {return new LpCplex(*this); } - - const char* LpCplex::_solverName() const { return "LpCplex"; } - - void LpCplex::_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. - LpCplex::SolveExitStatus LpCplex::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 - } - - LpCplex::SolveExitStatus LpCplex::_solve() { - _clear_temporals(); - return convertStatus(CPXlpopt(cplexEnv(), _prob)); - } - - LpCplex::SolveExitStatus LpCplex::solvePrimal() { - _clear_temporals(); - return convertStatus(CPXprimopt(cplexEnv(), _prob)); - } - - LpCplex::SolveExitStatus LpCplex::solveDual() { - _clear_temporals(); - return convertStatus(CPXdualopt(cplexEnv(), _prob)); - } - - LpCplex::SolveExitStatus LpCplex::solveBarrier() { - _clear_temporals(); - return convertStatus(CPXbaropt(cplexEnv(), _prob)); - } - - LpCplex::Value LpCplex::_getPrimal(int i) const { - Value x; - CPXgetx(cplexEnv(), _prob, &x, i, i); - return x; - } - - LpCplex::Value LpCplex::_getDual(int i) const { - Value y; - CPXgetpi(cplexEnv(), _prob, &y, i, i); - return y; - } - - LpCplex::Value LpCplex::_getPrimalValue() const { - Value objval; - CPXgetobjval(cplexEnv(), _prob, &objval); - return objval; - } - - LpCplex::VarStatus LpCplex::_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 LpCplex::VarStatus(); - } - } - - LpCplex::VarStatus LpCplex::_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 LpCplex::VarStatus(); - } - } - - LpCplex::Value LpCplex::_getPrimalRay(int i) const { - if (_primal_ray.empty()) { - _primal_ray.resize(CPXgetnumcols(cplexEnv(), _prob)); - CPXgetray(cplexEnv(), _prob, &_primal_ray.front()); - } - return _primal_ray[i]; - } - - LpCplex::Value LpCplex::_getDualRay(int i) const { - if (_dual_ray.empty()) { - - } - return _dual_ray[i]; - } - - //7.5-os cplex statusai (Vigyazat: a 9.0-asei masok!) - // This table lists the statuses, returned by the CPXgetstat() - // routine, for solutions to LP problems or mixed integer problems. If - // no solution exists, the return value is zero. - - // For Simplex, Barrier - // 1 CPX_OPTIMAL - // Optimal solution found - // 2 CPX_INFEASIBLE - // Problem infeasible - // 3 CPX_UNBOUNDED - // Problem unbounded - // 4 CPX_OBJ_LIM - // Objective limit exceeded in Phase II - // 5 CPX_IT_LIM_FEAS - // Iteration limit exceeded in Phase II - // 6 CPX_IT_LIM_INFEAS - // Iteration limit exceeded in Phase I - // 7 CPX_TIME_LIM_FEAS - // Time limit exceeded in Phase II - // 8 CPX_TIME_LIM_INFEAS - // Time limit exceeded in Phase I - // 9 CPX_NUM_BEST_FEAS - // Problem non-optimal, singularities in Phase II - // 10 CPX_NUM_BEST_INFEAS - // Problem non-optimal, singularities in Phase I - // 11 CPX_OPTIMAL_INFEAS - // Optimal solution found, unscaled infeasibilities - // 12 CPX_ABORT_FEAS - // Aborted in Phase II - // 13 CPX_ABORT_INFEAS - // Aborted in Phase I - // 14 CPX_ABORT_DUAL_INFEAS - // Aborted in barrier, dual infeasible - // 15 CPX_ABORT_PRIM_INFEAS - // Aborted in barrier, primal infeasible - // 16 CPX_ABORT_PRIM_DUAL_INFEAS - // Aborted in barrier, primal and dual infeasible - // 17 CPX_ABORT_PRIM_DUAL_FEAS - // Aborted in barrier, primal and dual feasible - // 18 CPX_ABORT_CROSSOVER - // Aborted in crossover - // 19 CPX_INForUNBD - // Infeasible or unbounded - // 20 CPX_PIVOT - // User pivot used - // - // Ezeket hova tegyem: - // ??case CPX_ABORT_DUAL_INFEAS - // ??case CPX_ABORT_CROSSOVER - // ??case CPX_INForUNBD - // ??case CPX_PIVOT - - //Some more interesting stuff: - - // CPX_PARAM_PROBMETHOD 1062 int LPMETHOD - // 0 Automatic - // 1 Primal Simplex - // 2 Dual Simplex - // 3 Network Simplex - // 4 Standard Barrier - // Default: 0 - // Description: Method for linear optimization. - // Determines which algorithm is used when CPXlpopt() (or "optimize" - // in the Interactive Optimizer) is called. Currently the behavior of - // the "Automatic" setting is that CPLEX simply invokes the dual - // simplex method, but this capability may be expanded in the future - // so that CPLEX chooses the method based on problem characteristics -#if CPX_VERSION < 900 - void statusSwitch(CPXENVptr cplexEnv(),int& stat){ - int lpmethod; - CPXgetintparam (cplexEnv(),CPX_PARAM_PROBMETHOD,&lpmethod); - if (lpmethod==2){ - if (stat==CPX_UNBOUNDED){ - stat=CPX_INFEASIBLE; - } - else{ - if (stat==CPX_INFEASIBLE) - stat=CPX_UNBOUNDED; - } - } - } -#else - void statusSwitch(CPXENVptr,int&){} -#endif - - LpCplex::ProblemType LpCplex::_getPrimalType() const { - // Unboundedness not treated well: the following is from cplex 9.0 doc - // About Unboundedness - - // The treatment of models that are unbounded involves a few - // subtleties. Specifically, a declaration of unboundedness means that - // ILOG CPLEX has determined that the model has an unbounded - // ray. Given any feasible solution x with objective z, a multiple of - // the unbounded ray can be added to x to give a feasible solution - // with objective z-1 (or z+1 for maximization models). Thus, if a - // feasible solution exists, then the optimal objective is - // unbounded. Note that ILOG CPLEX has not necessarily concluded that - // a feasible solution exists. Users can call the routine CPXsolninfo - // to determine whether ILOG CPLEX has also concluded that the model - // has a feasible solution. - - int stat = CPXgetstat(cplexEnv(), _prob); -#if CPX_VERSION >= 800 - switch (stat) - { - case CPX_STAT_OPTIMAL: - return OPTIMAL; - case CPX_STAT_UNBOUNDED: - return UNBOUNDED; - case CPX_STAT_INFEASIBLE: - return INFEASIBLE; - default: - return UNDEFINED; - } -#else - statusSwitch(cplexEnv(),stat); - //CPXgetstat(cplexEnv(), _prob); - //printf("A primal status: %d, CPX_OPTIMAL=%d \n",stat,CPX_OPTIMAL); - switch (stat) { - case 0: - return UNDEFINED; //Undefined - case CPX_OPTIMAL://Optimal - return OPTIMAL; - case CPX_UNBOUNDED://Unbounded - return INFEASIBLE;//In case of dual simplex - //return UNBOUNDED; - case CPX_INFEASIBLE://Infeasible - // case CPX_IT_LIM_INFEAS: - // case CPX_TIME_LIM_INFEAS: - // case CPX_NUM_BEST_INFEAS: - // case CPX_OPTIMAL_INFEAS: - // case CPX_ABORT_INFEAS: - // case CPX_ABORT_PRIM_INFEAS: - // case CPX_ABORT_PRIM_DUAL_INFEAS: - return UNBOUNDED;//In case of dual simplex - //return INFEASIBLE; - // case CPX_OBJ_LIM: - // case CPX_IT_LIM_FEAS: - // case CPX_TIME_LIM_FEAS: - // case CPX_NUM_BEST_FEAS: - // case CPX_ABORT_FEAS: - // case CPX_ABORT_PRIM_DUAL_FEAS: - // return FEASIBLE; - default: - return UNDEFINED; //Everything else comes here - //FIXME error - } -#endif - } - - //9.0-as cplex verzio statusai - // CPX_STAT_ABORT_DUAL_OBJ_LIM - // CPX_STAT_ABORT_IT_LIM - // CPX_STAT_ABORT_OBJ_LIM - // CPX_STAT_ABORT_PRIM_OBJ_LIM - // CPX_STAT_ABORT_TIME_LIM - // CPX_STAT_ABORT_USER - // CPX_STAT_FEASIBLE_RELAXED - // CPX_STAT_INFEASIBLE - // CPX_STAT_INForUNBD - // CPX_STAT_NUM_BEST - // CPX_STAT_OPTIMAL - // CPX_STAT_OPTIMAL_FACE_UNBOUNDED - // CPX_STAT_OPTIMAL_INFEAS - // CPX_STAT_OPTIMAL_RELAXED - // CPX_STAT_UNBOUNDED - - LpCplex::ProblemType LpCplex::_getDualType() const { - int stat = CPXgetstat(cplexEnv(), _prob); -#if CPX_VERSION >= 800 - switch (stat) { - case CPX_STAT_OPTIMAL: - return OPTIMAL; - case CPX_STAT_UNBOUNDED: - return INFEASIBLE; - default: - return UNDEFINED; - } -#else - statusSwitch(cplexEnv(),stat); - switch (stat) { - case 0: - return UNDEFINED; //Undefined - case CPX_OPTIMAL://Optimal - return OPTIMAL; - case CPX_UNBOUNDED: - return INFEASIBLE; - default: - return UNDEFINED; //Everything else comes here - //FIXME error - } -#endif - } - - // MipCplex members - - MipCplex::MipCplex() - : LpBase(), CplexBase(), MipSolver() { - -#if CPX_VERSION < 800 - CPXchgprobtype(cplexEnv(), _prob, CPXPROB_MIP); -#else - CPXchgprobtype(cplexEnv(), _prob, CPXPROB_MILP); -#endif - } - - MipCplex::MipCplex(const CplexEnv& env) - : LpBase(), CplexBase(env), MipSolver() { - -#if CPX_VERSION < 800 - CPXchgprobtype(cplexEnv(), _prob, CPXPROB_MIP); -#else - CPXchgprobtype(cplexEnv(), _prob, CPXPROB_MILP); -#endif - - } - - MipCplex::MipCplex(const MipCplex& other) - : LpBase(), CplexBase(other), MipSolver() {} - - MipCplex::~MipCplex() {} - - MipCplex* MipCplex::_newSolver() const { return new MipCplex; } - MipCplex* MipCplex::_cloneSolver() const {return new MipCplex(*this); } - - const char* MipCplex::_solverName() const { return "MipCplex"; } - - void MipCplex::_setColType(int i, MipCplex::ColTypes col_type) { - - // Note If a variable is to be changed to binary, a call to CPXchgbds - // should also be made to change the bounds to 0 and 1. - - switch (col_type){ - case INTEGER: { - const char t = 'I'; - CPXchgctype (cplexEnv(), _prob, 1, &i, &t); - } break; - case REAL: { - const char t = 'C'; - CPXchgctype (cplexEnv(), _prob, 1, &i, &t); - } break; - default: - break; - } - } - - MipCplex::ColTypes MipCplex::_getColType(int i) const { - char t; - CPXgetctype (cplexEnv(), _prob, &t, i, i); - switch (t) { - case 'I': - return INTEGER; - case 'C': - return REAL; - default: - LEMON_ASSERT(false, "Invalid column type"); - return ColTypes(); - } - - } - - MipCplex::SolveExitStatus MipCplex::_solve() { - int status; - status = CPXmipopt (cplexEnv(), _prob); - if (status==0) - return SOLVED; - else - return UNSOLVED; - - } - - - MipCplex::ProblemType MipCplex::_getType() const { - - int stat = CPXgetstat(cplexEnv(), _prob); - - //Fortunately, MIP statuses did not change for cplex 8.0 - switch (stat) { - case CPXMIP_OPTIMAL: - // Optimal integer solution has been found. - case CPXMIP_OPTIMAL_TOL: - // Optimal soluton with the tolerance defined by epgap or epagap has - // been found. - return OPTIMAL; - //This also exists in later issues - // case CPXMIP_UNBOUNDED: - //return UNBOUNDED; - case CPXMIP_INFEASIBLE: - return INFEASIBLE; - default: - return UNDEFINED; - } - //Unboundedness not treated well: the following is from cplex 9.0 doc - // About Unboundedness - - // The treatment of models that are unbounded involves a few - // subtleties. Specifically, a declaration of unboundedness means that - // ILOG CPLEX has determined that the model has an unbounded - // ray. Given any feasible solution x with objective z, a multiple of - // the unbounded ray can be added to x to give a feasible solution - // with objective z-1 (or z+1 for maximization models). Thus, if a - // feasible solution exists, then the optimal objective is - // unbounded. Note that ILOG CPLEX has not necessarily concluded that - // a feasible solution exists. Users can call the routine CPXsolninfo - // to determine whether ILOG CPLEX has also concluded that the model - // has a feasible solution. - } - - MipCplex::Value MipCplex::_getSol(int i) const { - Value x; - CPXgetmipx(cplexEnv(), _prob, &x, i, i); - return x; - } - - MipCplex::Value MipCplex::_getSolValue() const { - Value objval; - CPXgetmipobjval(cplexEnv(), _prob, &objval); - return objval; - } - -} //namespace lemon - diff --git a/lemon/lp_cplex.h b/lemon/lp_cplex.h deleted file mode 100644 --- a/lemon/lp_cplex.h +++ /dev/null @@ -1,256 +0,0 @@ -/* -*- 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_CPLEX_H -#define LEMON_LP_CPLEX_H - -///\file -///\brief Header of the LEMON-CPLEX lp solver interface. - -#include - -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 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(); - - public: - - /// Returns the used \c CplexEnv instance - const CplexEnv& env() const { return _env; } - /// - const cpxenv* cplexEnv() const { return _env.cplexEnv(); } - - cpxlp* cplexLp() { return _prob; } - 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 LpCplex : public CplexBase, public LpSolver { - public: - /// \e - LpCplex(); - /// \e - LpCplex(const CplexEnv&); - /// \e - LpCplex(const LpCplex&); - /// \e - virtual ~LpCplex(); - - private: - - // these values cannot retrieved element by element - mutable std::vector _col_status; - mutable std::vector _row_status; - - mutable std::vector _primal_ray; - mutable std::vector _dual_ray; - - void _clear_temporals(); - - SolveExitStatus convertStatus(int status); - - protected: - - virtual LpCplex* _cloneSolver() const; - virtual LpCplex* _newSolver() const; - - 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 MipCplex : public CplexBase, public MipSolver { - public: - /// \e - MipCplex(); - /// \e - MipCplex(const CplexEnv&); - /// \e - MipCplex(const MipCplex&); - /// \e - virtual ~MipCplex(); - - protected: - - virtual MipCplex* _cloneSolver() const; - virtual MipCplex* _newSolver() const; - - 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_LP_CPLEX_H - diff --git a/lemon/lp_glpk.cc b/lemon/lp_glpk.cc deleted file mode 100644 --- a/lemon/lp_glpk.cc +++ /dev/null @@ -1,952 +0,0 @@ -/* -*- 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. - * - */ - -///\file -///\brief Implementation of the LEMON GLPK LP and MIP solver interface. - -#include -#include - -#include - -namespace lemon { - - // GlpkBase members - - GlpkBase::GlpkBase() : LpBase() { - lp = glp_create_prob(); - glp_create_index(lp); - } - - 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; - } - - 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; - } - - 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(name.c_str())); - - } - - int GlpkBase::_colByName(const std::string& name) const { - int k = glp_find_col(lp, const_cast(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(name.c_str())); - - } - - int GlpkBase::_rowByName(const std::string& name) const { - int k = glp_find_row(lp, const_cast(name.c_str())); - return k > 0 ? k : -1; - } - - void GlpkBase::_setRowCoeffs(int i, ExprIterator b, ExprIterator e) { - std::vector indexes; - std::vector 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 indexes(length + 1); - std::vector 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 indexes; - std::vector 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 indexes(length + 1); - std::vector 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 indexes(length + 2); - std::vector 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 indexes(length + 2); - std::vector 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 indexes(length + 1); - std::vector 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(); - } - - // LpGlpk members - - LpGlpk::LpGlpk() - : LpBase(), GlpkBase(), LpSolver() { - messageLevel(MESSAGE_NO_OUTPUT); - } - - LpGlpk::LpGlpk(const LpGlpk& other) - : LpBase(other), GlpkBase(other), LpSolver(other) { - messageLevel(MESSAGE_NO_OUTPUT); - } - - LpGlpk* LpGlpk::_newSolver() const { return new LpGlpk; } - LpGlpk* LpGlpk::_cloneSolver() const { return new LpGlpk(*this); } - - const char* LpGlpk::_solverName() const { return "LpGlpk"; } - - void LpGlpk::_clear_temporals() { - _primal_ray.clear(); - _dual_ray.clear(); - } - - LpGlpk::SolveExitStatus LpGlpk::_solve() { - return solvePrimal(); - } - - LpGlpk::SolveExitStatus LpGlpk::solvePrimal() { - _clear_temporals(); - - glp_smcp smcp; - glp_init_smcp(&smcp); - - switch (_message_level) { - case MESSAGE_NO_OUTPUT: - smcp.msg_lev = GLP_MSG_OFF; - break; - case MESSAGE_ERROR_MESSAGE: - smcp.msg_lev = GLP_MSG_ERR; - break; - case MESSAGE_NORMAL_OUTPUT: - smcp.msg_lev = GLP_MSG_ON; - break; - case MESSAGE_FULL_OUTPUT: - smcp.msg_lev = GLP_MSG_ALL; - break; - } - - if (glp_simplex(lp, &smcp) != 0) return UNSOLVED; - return SOLVED; - } - - LpGlpk::SolveExitStatus LpGlpk::solveDual() { - _clear_temporals(); - - glp_smcp smcp; - glp_init_smcp(&smcp); - - switch (_message_level) { - case MESSAGE_NO_OUTPUT: - smcp.msg_lev = GLP_MSG_OFF; - break; - case MESSAGE_ERROR_MESSAGE: - smcp.msg_lev = GLP_MSG_ERR; - break; - case MESSAGE_NORMAL_OUTPUT: - smcp.msg_lev = GLP_MSG_ON; - break; - case MESSAGE_FULL_OUTPUT: - smcp.msg_lev = GLP_MSG_ALL; - break; - } - smcp.meth = GLP_DUAL; - - if (glp_simplex(lp, &smcp) != 0) return UNSOLVED; - return SOLVED; - } - - LpGlpk::Value LpGlpk::_getPrimal(int i) const { - return glp_get_col_prim(lp, i); - } - - LpGlpk::Value LpGlpk::_getDual(int i) const { - return glp_get_row_dual(lp, i); - } - - LpGlpk::Value LpGlpk::_getPrimalValue() const { - return glp_get_obj_val(lp); - } - - LpGlpk::VarStatus LpGlpk::_getColStatus(int i) const { - switch (glp_get_col_stat(lp, i)) { - case GLP_BS: - return BASIC; - case GLP_UP: - return UPPER; - case GLP_LO: - return LOWER; - case GLP_NF: - return FREE; - case GLP_NS: - return FIXED; - default: - LEMON_ASSERT(false, "Wrong column status"); - return LpGlpk::VarStatus(); - } - } - - LpGlpk::VarStatus LpGlpk::_getRowStatus(int i) const { - switch (glp_get_row_stat(lp, i)) { - case GLP_BS: - return BASIC; - case GLP_UP: - return UPPER; - case GLP_LO: - return LOWER; - case GLP_NF: - return FREE; - case GLP_NS: - return FIXED; - default: - LEMON_ASSERT(false, "Wrong row status"); - return LpGlpk::VarStatus(); - } - } - - LpGlpk::Value LpGlpk::_getPrimalRay(int i) const { - if (_primal_ray.empty()) { - int row_num = glp_get_num_rows(lp); - int col_num = glp_get_num_cols(lp); - - _primal_ray.resize(col_num + 1, 0.0); - - int index = glp_get_unbnd_ray(lp); - if (index != 0) { - // The primal ray is found in primal simplex second phase - LEMON_ASSERT((index <= row_num ? glp_get_row_stat(lp, index) : - glp_get_col_stat(lp, index - row_num)) != GLP_BS, - "Wrong primal ray"); - - bool negate = glp_get_obj_dir(lp) == GLP_MAX; - - if (index > row_num) { - _primal_ray[index - row_num] = 1.0; - if (glp_get_col_dual(lp, index - row_num) > 0) { - negate = !negate; - } - } else { - if (glp_get_row_dual(lp, index) > 0) { - negate = !negate; - } - } - - std::vector ray_indexes(row_num + 1); - std::vector ray_values(row_num + 1); - int ray_length = glp_eval_tab_col(lp, index, &ray_indexes.front(), - &ray_values.front()); - - for (int i = 1; i <= ray_length; ++i) { - if (ray_indexes[i] > row_num) { - _primal_ray[ray_indexes[i] - row_num] = ray_values[i]; - } - } - - if (negate) { - for (int i = 1; i <= col_num; ++i) { - _primal_ray[i] = - _primal_ray[i]; - } - } - } else { - for (int i = 1; i <= col_num; ++i) { - _primal_ray[i] = glp_get_col_prim(lp, i); - } - } - } - return _primal_ray[i]; - } - - LpGlpk::Value LpGlpk::_getDualRay(int i) const { - if (_dual_ray.empty()) { - int row_num = glp_get_num_rows(lp); - - _dual_ray.resize(row_num + 1, 0.0); - - int index = glp_get_unbnd_ray(lp); - if (index != 0) { - // The dual ray is found in dual simplex second phase - LEMON_ASSERT((index <= row_num ? glp_get_row_stat(lp, index) : - glp_get_col_stat(lp, index - row_num)) == GLP_BS, - - "Wrong dual ray"); - - int idx; - bool negate = false; - - if (index > row_num) { - idx = glp_get_col_bind(lp, index - row_num); - if (glp_get_col_prim(lp, index - row_num) > - glp_get_col_ub(lp, index - row_num)) { - negate = true; - } - } else { - idx = glp_get_row_bind(lp, index); - if (glp_get_row_prim(lp, index) > glp_get_row_ub(lp, index)) { - negate = true; - } - } - - _dual_ray[idx] = negate ? - 1.0 : 1.0; - - glp_btran(lp, &_dual_ray.front()); - } else { - double eps = 1e-7; - // The dual ray is found in primal simplex first phase - // We assume that the glpk minimizes the slack to get feasible solution - for (int i = 1; i <= row_num; ++i) { - int index = glp_get_bhead(lp, i); - if (index <= row_num) { - double res = glp_get_row_prim(lp, index); - if (res > glp_get_row_ub(lp, index) + eps) { - _dual_ray[i] = -1; - } else if (res < glp_get_row_lb(lp, index) - eps) { - _dual_ray[i] = 1; - } else { - _dual_ray[i] = 0; - } - _dual_ray[i] *= glp_get_rii(lp, index); - } else { - double res = glp_get_col_prim(lp, index - row_num); - if (res > glp_get_col_ub(lp, index - row_num) + eps) { - _dual_ray[i] = -1; - } else if (res < glp_get_col_lb(lp, index - row_num) - eps) { - _dual_ray[i] = 1; - } else { - _dual_ray[i] = 0; - } - _dual_ray[i] /= glp_get_sjj(lp, index - row_num); - } - } - - glp_btran(lp, &_dual_ray.front()); - - for (int i = 1; i <= row_num; ++i) { - _dual_ray[i] /= glp_get_rii(lp, i); - } - } - } - return _dual_ray[i]; - } - - LpGlpk::ProblemType LpGlpk::_getPrimalType() const { - if (glp_get_status(lp) == GLP_OPT) - return OPTIMAL; - switch (glp_get_prim_stat(lp)) { - case GLP_UNDEF: - return UNDEFINED; - case GLP_FEAS: - case GLP_INFEAS: - if (glp_get_dual_stat(lp) == GLP_NOFEAS) { - return UNBOUNDED; - } else { - return UNDEFINED; - } - case GLP_NOFEAS: - return INFEASIBLE; - default: - LEMON_ASSERT(false, "Wrong primal type"); - return LpGlpk::ProblemType(); - } - } - - LpGlpk::ProblemType LpGlpk::_getDualType() const { - if (glp_get_status(lp) == GLP_OPT) - return OPTIMAL; - switch (glp_get_dual_stat(lp)) { - case GLP_UNDEF: - return UNDEFINED; - case GLP_FEAS: - case GLP_INFEAS: - if (glp_get_prim_stat(lp) == GLP_NOFEAS) { - return UNBOUNDED; - } else { - return UNDEFINED; - } - case GLP_NOFEAS: - return INFEASIBLE; - default: - LEMON_ASSERT(false, "Wrong primal type"); - return LpGlpk::ProblemType(); - } - } - - void LpGlpk::presolver(bool b) { - lpx_set_int_parm(lp, LPX_K_PRESOL, b ? 1 : 0); - } - - void LpGlpk::messageLevel(MessageLevel m) { - _message_level = m; - } - - // MipGlpk members - - MipGlpk::MipGlpk() - : LpBase(), GlpkBase(), MipSolver() { - messageLevel(MESSAGE_NO_OUTPUT); - } - - MipGlpk::MipGlpk(const MipGlpk& other) - : LpBase(), GlpkBase(other), MipSolver() { - messageLevel(MESSAGE_NO_OUTPUT); - } - - void MipGlpk::_setColType(int i, MipGlpk::ColTypes col_type) { - switch (col_type) { - case INTEGER: - glp_set_col_kind(lp, i, GLP_IV); - break; - case REAL: - glp_set_col_kind(lp, i, GLP_CV); - break; - } - } - - MipGlpk::ColTypes MipGlpk::_getColType(int i) const { - switch (glp_get_col_kind(lp, i)) { - case GLP_IV: - case GLP_BV: - return INTEGER; - default: - return REAL; - } - - } - - MipGlpk::SolveExitStatus MipGlpk::_solve() { - glp_smcp smcp; - glp_init_smcp(&smcp); - - switch (_message_level) { - case MESSAGE_NO_OUTPUT: - smcp.msg_lev = GLP_MSG_OFF; - break; - case MESSAGE_ERROR_MESSAGE: - smcp.msg_lev = GLP_MSG_ERR; - break; - case MESSAGE_NORMAL_OUTPUT: - smcp.msg_lev = GLP_MSG_ON; - break; - case MESSAGE_FULL_OUTPUT: - smcp.msg_lev = GLP_MSG_ALL; - break; - } - smcp.meth = GLP_DUAL; - - if (glp_simplex(lp, &smcp) != 0) return UNSOLVED; - if (glp_get_status(lp) != GLP_OPT) return SOLVED; - - glp_iocp iocp; - glp_init_iocp(&iocp); - - switch (_message_level) { - case MESSAGE_NO_OUTPUT: - iocp.msg_lev = GLP_MSG_OFF; - break; - case MESSAGE_ERROR_MESSAGE: - iocp.msg_lev = GLP_MSG_ERR; - break; - case MESSAGE_NORMAL_OUTPUT: - iocp.msg_lev = GLP_MSG_ON; - break; - case MESSAGE_FULL_OUTPUT: - iocp.msg_lev = GLP_MSG_ALL; - break; - } - - if (glp_intopt(lp, &iocp) != 0) return UNSOLVED; - return SOLVED; - } - - - MipGlpk::ProblemType MipGlpk::_getType() const { - switch (glp_get_status(lp)) { - case GLP_OPT: - switch (glp_mip_status(lp)) { - case GLP_UNDEF: - return UNDEFINED; - case GLP_NOFEAS: - return INFEASIBLE; - case GLP_FEAS: - return FEASIBLE; - case GLP_OPT: - return OPTIMAL; - default: - LEMON_ASSERT(false, "Wrong problem type."); - return MipGlpk::ProblemType(); - } - case GLP_NOFEAS: - return INFEASIBLE; - case GLP_INFEAS: - case GLP_FEAS: - if (glp_get_dual_stat(lp) == GLP_NOFEAS) { - return UNBOUNDED; - } else { - return UNDEFINED; - } - default: - LEMON_ASSERT(false, "Wrong problem type."); - return MipGlpk::ProblemType(); - } - } - - MipGlpk::Value MipGlpk::_getSol(int i) const { - return glp_mip_col_val(lp, i); - } - - MipGlpk::Value MipGlpk::_getSolValue() const { - return glp_mip_obj_val(lp); - } - - MipGlpk* MipGlpk::_newSolver() const { return new MipGlpk; } - MipGlpk* MipGlpk::_cloneSolver() const {return new MipGlpk(*this); } - - const char* MipGlpk::_solverName() const { return "MipGlpk"; } - - void MipGlpk::messageLevel(MessageLevel m) { - _message_level = m; - } - -} //END OF NAMESPACE LEMON diff --git a/lemon/lp_glpk.h b/lemon/lp_glpk.h deleted file mode 100644 --- a/lemon/lp_glpk.h +++ /dev/null @@ -1,259 +0,0 @@ -/* -*- 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_GLPK_H -#define LEMON_LP_GLPK_H - -///\file -///\brief Header of the LEMON-GLPK lp solver interface. -///\ingroup lp_group - -#include - -// forward declaration -#ifndef _GLP_PROB -#define _GLP_PROB -typedef struct { double _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 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(); - - 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 LpGlpk : public GlpkBase, public LpSolver { - public: - - ///\e - LpGlpk(); - ///\e - LpGlpk(const LpGlpk&); - - private: - - mutable std::vector _primal_ray; - mutable std::vector _dual_ray; - - void _clear_temporals(); - - protected: - - virtual LpGlpk* _cloneSolver() const; - virtual LpGlpk* _newSolver() const; - - 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; - - ///\todo It should be clarified - /// - virtual ProblemType _getPrimalType() const; - virtual ProblemType _getDualType() const; - - public: - - ///Solve with primal simplex - SolveExitStatus solvePrimal(); - - ///Solve with dual simplex - SolveExitStatus solveDual(); - - ///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 b); - - ///Enum for \c messageLevel() parameter - enum MessageLevel { - /// no output (default value) - MESSAGE_NO_OUTPUT = 0, - /// error messages only - MESSAGE_ERROR_MESSAGE = 1, - /// normal output - MESSAGE_NORMAL_OUTPUT = 2, - /// full output (includes informational messages) - MESSAGE_FULL_OUTPUT = 3 - }; - - private: - - MessageLevel _message_level; - - public: - - ///Set the verbosity of the messages - - ///Set the verbosity of the messages - /// - ///\param m is the level of the messages output by the solver routines. - void messageLevel(MessageLevel m); - }; - - /// \brief Interface for the GLPK MIP solver - /// - /// This class implements an interface for the GLPK MIP solver. - ///\ingroup lp_group - class MipGlpk : public GlpkBase, public MipSolver { - public: - - ///\e - MipGlpk(); - ///\e - MipGlpk(const MipGlpk&); - - protected: - - virtual MipGlpk* _cloneSolver() const; - virtual MipGlpk* _newSolver() const; - - 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; - - ///Enum for \c messageLevel() parameter - enum MessageLevel { - /// no output (default value) - MESSAGE_NO_OUTPUT = 0, - /// error messages only - MESSAGE_ERROR_MESSAGE = 1, - /// normal output - MESSAGE_NORMAL_OUTPUT = 2, - /// full output (includes informational messages) - MESSAGE_FULL_OUTPUT = 3 - }; - - private: - - MessageLevel _message_level; - - public: - - ///Set the verbosity of the messages - - ///Set the verbosity of the messages - /// - ///\param m is the level of the messages output by the solver routines. - void messageLevel(MessageLevel m); - }; - - -} //END OF NAMESPACE LEMON - -#endif //LEMON_LP_GLPK_H - diff --git a/lemon/lp_soplex.cc b/lemon/lp_soplex.cc deleted file mode 100644 --- a/lemon/lp_soplex.cc +++ /dev/null @@ -1,423 +0,0 @@ -/* -*- 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 -#include - -#include - - -///\file -///\brief Implementation of the LEMON-SOPLEX lp solver interface. -namespace lemon { - - LpSoplex::LpSoplex() { - soplex = new soplex::SoPlex; - } - - LpSoplex::~LpSoplex() { - delete soplex; - } - - LpSoplex::LpSoplex(const LpSoplex& lp) { - rows = lp.rows; - cols = lp.cols; - - soplex = new soplex::SoPlex; - (*static_cast(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; - - } - - void LpSoplex::_clear_temporals() { - _primal_values.clear(); - _dual_values.clear(); - } - - LpSoplex* LpSoplex::_newSolver() const { - LpSoplex* newlp = new LpSoplex(); - return newlp; - } - - LpSoplex* LpSoplex::_cloneSolver() const { - LpSoplex* newlp = new LpSoplex(*this); - return newlp; - } - - const char* LpSoplex::_solverName() const { return "LpSoplex"; } - - int LpSoplex::_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 LpSoplex::_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; - } - - - void LpSoplex::_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 LpSoplex::_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 LpSoplex::_eraseColId(int i) { - cols.eraseIndex(i); - cols.relocateIndex(i, cols.maxIndex()); - } - void LpSoplex::_eraseRowId(int i) { - rows.eraseIndex(i); - rows.relocateIndex(i, rows.maxIndex()); - } - - void LpSoplex::_getColName(int c, std::string &name) const { - name = _col_names[c]; - } - - void LpSoplex::_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 LpSoplex::_colByName(const std::string& name) const { - std::map::const_iterator it = - _col_names_ref.find(name); - if (it != _col_names_ref.end()) { - return it->second; - } else { - return -1; - } - } - - void LpSoplex::_getRowName(int r, std::string &name) const { - name = _row_names[r]; - } - - void LpSoplex::_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 LpSoplex::_rowByName(const std::string& name) const { - std::map::const_iterator it = - _row_names_ref.find(name); - if (it != _row_names_ref.end()) { - return it->second; - } else { - return -1; - } - } - - - void LpSoplex::_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 LpSoplex::_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 LpSoplex::_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 LpSoplex::_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 LpSoplex::_setCoeff(int i, int j, Value value) { - soplex->changeElement(i, j, value); - } - - LpSoplex::Value LpSoplex::_getCoeff(int i, int j) const { - return soplex->rowVector(i)[j]; - } - - void LpSoplex::_setColLowerBound(int i, Value value) { - LEMON_ASSERT(value != INF, "Invalid bound"); - soplex->changeLower(i, value != -INF ? value : -soplex::infinity); - } - - LpSoplex::Value LpSoplex::_getColLowerBound(int i) const { - double value = soplex->lower(i); - return value != -soplex::infinity ? value : -INF; - } - - void LpSoplex::_setColUpperBound(int i, Value value) { - LEMON_ASSERT(value != -INF, "Invalid bound"); - soplex->changeUpper(i, value != INF ? value : soplex::infinity); - } - - LpSoplex::Value LpSoplex::_getColUpperBound(int i) const { - double value = soplex->upper(i); - return value != soplex::infinity ? value : INF; - } - - void LpSoplex::_setRowLowerBound(int i, Value lb) { - LEMON_ASSERT(lb != INF, "Invalid bound"); - soplex->changeRange(i, lb != -INF ? lb : -soplex::infinity, soplex->rhs(i)); - } - - LpSoplex::Value LpSoplex::_getRowLowerBound(int i) const { - double res = soplex->lhs(i); - return res == -soplex::infinity ? -INF : res; - } - - void LpSoplex::_setRowUpperBound(int i, Value ub) { - LEMON_ASSERT(ub != -INF, "Invalid bound"); - soplex->changeRange(i, soplex->lhs(i), ub != INF ? ub : soplex::infinity); - } - - LpSoplex::Value LpSoplex::_getRowUpperBound(int i) const { - double res = soplex->rhs(i); - return res == soplex::infinity ? INF : res; - } - - void LpSoplex::_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 LpSoplex::_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 LpSoplex::_setObjCoeff(int i, Value obj_coef) { - soplex->changeObj(i, obj_coef); - } - - LpSoplex::Value LpSoplex::_getObjCoeff(int i) const { - return soplex->obj(i); - } - - LpSoplex::SolveExitStatus LpSoplex::_solve() { - - _clear_temporals(); - - 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; - } - } - - LpSoplex::Value LpSoplex::_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]; - } - - LpSoplex::Value LpSoplex::_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]; - } - - LpSoplex::Value LpSoplex::_getPrimalValue() const { - return soplex->objValue(); - } - - LpSoplex::VarStatus LpSoplex::_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(); - } - } - - LpSoplex::VarStatus LpSoplex::_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(); - } - } - - LpSoplex::Value LpSoplex::_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]; - } - - LpSoplex::Value LpSoplex::_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]; - } - - LpSoplex::ProblemType LpSoplex::_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; - } - } - - LpSoplex::ProblemType LpSoplex::_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 LpSoplex::_setSense(Sense sense) { - switch (sense) { - case MIN: - soplex->changeSense(soplex::SPxSolver::MINIMIZE); - break; - case MAX: - soplex->changeSense(soplex::SPxSolver::MAXIMIZE); - } - } - - LpSoplex::Sense LpSoplex::_getSense() const { - switch (soplex->spxSense()) { - case soplex::SPxSolver::MAXIMIZE: - return MAX; - case soplex::SPxSolver::MINIMIZE: - return MIN; - default: - LEMON_ASSERT(false, "Wrong sense."); - return LpSoplex::Sense(); - } - } - - void LpSoplex::_clear() { - soplex->clear(); - _col_names.clear(); - _col_names_ref.clear(); - _row_names.clear(); - _row_names_ref.clear(); - cols.clear(); - rows.clear(); - _clear_temporals(); - } - -} //namespace lemon - diff --git a/lemon/lp_soplex.h b/lemon/lp_soplex.h deleted file mode 100644 --- a/lemon/lp_soplex.h +++ /dev/null @@ -1,151 +0,0 @@ -/* -*- 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_SOPLEX_H -#define LEMON_LP_SOPLEX_H - -///\file -///\brief Header of the LEMON-SOPLEX lp solver interface. - -#include -#include - -#include - -// 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 - /// http://soplex.zib.de address. - class LpSoplex : public LpSolver { - private: - - soplex::SoPlex* soplex; - - std::vector _col_names; - std::map _col_names_ref; - - std::vector _row_names; - std::map _row_names_ref; - - private: - - // these values cannot be retrieved element by element - mutable std::vector _primal_values; - mutable std::vector _dual_values; - - mutable std::vector _primal_ray; - mutable std::vector _dual_ray; - - void _clear_temporals(); - - public: - - /// \e - LpSoplex(); - /// \e - LpSoplex(const LpSoplex&); - /// \e - ~LpSoplex(); - - protected: - - virtual LpSoplex* _newSolver() const; - virtual LpSoplex* _cloneSolver() const; - - virtual const char* _solverName() const; - - virtual int _addCol(); - virtual int _addRow(); - - virtual void _eraseCol(int i); - virtual void _eraseRow(int i); - - virtual void _eraseColId(int i); - virtual void _eraseRowId(int i); - - virtual void _getColName(int col, std::string& name) const; - virtual void _setColName(int col, const std::string& name); - virtual int _colByName(const std::string& name) const; - - virtual void _getRowName(int row, std::string& name) const; - virtual void _setRowName(int row, const std::string& name); - virtual int _rowByName(const std::string& name) const; - - virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e); - virtual void _getRowCoeffs(int i, InsertIterator b) const; - - virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e); - virtual void _getColCoeffs(int i, InsertIterator b) const; - - virtual void _setCoeff(int row, int col, Value value); - virtual Value _getCoeff(int row, int col) const; - - virtual void _setColLowerBound(int i, Value value); - virtual Value _getColLowerBound(int i) const; - virtual void _setColUpperBound(int i, Value value); - virtual Value _getColUpperBound(int i) const; - - virtual void _setRowLowerBound(int i, Value value); - virtual Value _getRowLowerBound(int i) const; - virtual void _setRowUpperBound(int i, Value value); - virtual Value _getRowUpperBound(int i) const; - - virtual void _setObjCoeffs(ExprIterator b, ExprIterator e); - virtual void _getObjCoeffs(InsertIterator b) const; - - virtual void _setObjCoeff(int i, Value obj_coef); - virtual Value _getObjCoeff(int i) const; - - virtual void _setSense(Sense sense); - virtual Sense _getSense() const; - - virtual 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(); - - }; - -} //END OF NAMESPACE LEMON - -#endif //LEMON_LP_SOPLEX_H - diff --git a/lemon/soplex.cc b/lemon/soplex.cc new file mode 100644 --- /dev/null +++ b/lemon/soplex.cc @@ -0,0 +1,423 @@ +/* -*- 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 +#include + +#include + + +///\file +///\brief Implementation of the LEMON-SOPLEX lp solver interface. +namespace lemon { + + LpSoplex::LpSoplex() { + soplex = new soplex::SoPlex; + } + + LpSoplex::~LpSoplex() { + delete soplex; + } + + LpSoplex::LpSoplex(const LpSoplex& lp) { + rows = lp.rows; + cols = lp.cols; + + soplex = new soplex::SoPlex; + (*static_cast(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; + + } + + void LpSoplex::_clear_temporals() { + _primal_values.clear(); + _dual_values.clear(); + } + + LpSoplex* LpSoplex::_newSolver() const { + LpSoplex* newlp = new LpSoplex(); + return newlp; + } + + LpSoplex* LpSoplex::_cloneSolver() const { + LpSoplex* newlp = new LpSoplex(*this); + return newlp; + } + + const char* LpSoplex::_solverName() const { return "LpSoplex"; } + + int LpSoplex::_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 LpSoplex::_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; + } + + + void LpSoplex::_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 LpSoplex::_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 LpSoplex::_eraseColId(int i) { + cols.eraseIndex(i); + cols.relocateIndex(i, cols.maxIndex()); + } + void LpSoplex::_eraseRowId(int i) { + rows.eraseIndex(i); + rows.relocateIndex(i, rows.maxIndex()); + } + + void LpSoplex::_getColName(int c, std::string &name) const { + name = _col_names[c]; + } + + void LpSoplex::_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 LpSoplex::_colByName(const std::string& name) const { + std::map::const_iterator it = + _col_names_ref.find(name); + if (it != _col_names_ref.end()) { + return it->second; + } else { + return -1; + } + } + + void LpSoplex::_getRowName(int r, std::string &name) const { + name = _row_names[r]; + } + + void LpSoplex::_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 LpSoplex::_rowByName(const std::string& name) const { + std::map::const_iterator it = + _row_names_ref.find(name); + if (it != _row_names_ref.end()) { + return it->second; + } else { + return -1; + } + } + + + void LpSoplex::_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 LpSoplex::_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 LpSoplex::_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 LpSoplex::_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 LpSoplex::_setCoeff(int i, int j, Value value) { + soplex->changeElement(i, j, value); + } + + LpSoplex::Value LpSoplex::_getCoeff(int i, int j) const { + return soplex->rowVector(i)[j]; + } + + void LpSoplex::_setColLowerBound(int i, Value value) { + LEMON_ASSERT(value != INF, "Invalid bound"); + soplex->changeLower(i, value != -INF ? value : -soplex::infinity); + } + + LpSoplex::Value LpSoplex::_getColLowerBound(int i) const { + double value = soplex->lower(i); + return value != -soplex::infinity ? value : -INF; + } + + void LpSoplex::_setColUpperBound(int i, Value value) { + LEMON_ASSERT(value != -INF, "Invalid bound"); + soplex->changeUpper(i, value != INF ? value : soplex::infinity); + } + + LpSoplex::Value LpSoplex::_getColUpperBound(int i) const { + double value = soplex->upper(i); + return value != soplex::infinity ? value : INF; + } + + void LpSoplex::_setRowLowerBound(int i, Value lb) { + LEMON_ASSERT(lb != INF, "Invalid bound"); + soplex->changeRange(i, lb != -INF ? lb : -soplex::infinity, soplex->rhs(i)); + } + + LpSoplex::Value LpSoplex::_getRowLowerBound(int i) const { + double res = soplex->lhs(i); + return res == -soplex::infinity ? -INF : res; + } + + void LpSoplex::_setRowUpperBound(int i, Value ub) { + LEMON_ASSERT(ub != -INF, "Invalid bound"); + soplex->changeRange(i, soplex->lhs(i), ub != INF ? ub : soplex::infinity); + } + + LpSoplex::Value LpSoplex::_getRowUpperBound(int i) const { + double res = soplex->rhs(i); + return res == soplex::infinity ? INF : res; + } + + void LpSoplex::_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 LpSoplex::_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 LpSoplex::_setObjCoeff(int i, Value obj_coef) { + soplex->changeObj(i, obj_coef); + } + + LpSoplex::Value LpSoplex::_getObjCoeff(int i) const { + return soplex->obj(i); + } + + LpSoplex::SolveExitStatus LpSoplex::_solve() { + + _clear_temporals(); + + 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; + } + } + + LpSoplex::Value LpSoplex::_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]; + } + + LpSoplex::Value LpSoplex::_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]; + } + + LpSoplex::Value LpSoplex::_getPrimalValue() const { + return soplex->objValue(); + } + + LpSoplex::VarStatus LpSoplex::_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(); + } + } + + LpSoplex::VarStatus LpSoplex::_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(); + } + } + + LpSoplex::Value LpSoplex::_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]; + } + + LpSoplex::Value LpSoplex::_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]; + } + + LpSoplex::ProblemType LpSoplex::_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; + } + } + + LpSoplex::ProblemType LpSoplex::_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 LpSoplex::_setSense(Sense sense) { + switch (sense) { + case MIN: + soplex->changeSense(soplex::SPxSolver::MINIMIZE); + break; + case MAX: + soplex->changeSense(soplex::SPxSolver::MAXIMIZE); + } + } + + LpSoplex::Sense LpSoplex::_getSense() const { + switch (soplex->spxSense()) { + case soplex::SPxSolver::MAXIMIZE: + return MAX; + case soplex::SPxSolver::MINIMIZE: + return MIN; + default: + LEMON_ASSERT(false, "Wrong sense."); + return LpSoplex::Sense(); + } + } + + void LpSoplex::_clear() { + soplex->clear(); + _col_names.clear(); + _col_names_ref.clear(); + _row_names.clear(); + _row_names_ref.clear(); + cols.clear(); + rows.clear(); + _clear_temporals(); + } + +} //namespace lemon + diff --git a/lemon/soplex.h b/lemon/soplex.h new file mode 100644 --- /dev/null +++ b/lemon/soplex.h @@ -0,0 +1,151 @@ +/* -*- 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 +#include + +#include + +// 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 + /// http://soplex.zib.de address. + class LpSoplex : public LpSolver { + private: + + soplex::SoPlex* soplex; + + std::vector _col_names; + std::map _col_names_ref; + + std::vector _row_names; + std::map _row_names_ref; + + private: + + // these values cannot be retrieved element by element + mutable std::vector _primal_values; + mutable std::vector _dual_values; + + mutable std::vector _primal_ray; + mutable std::vector _dual_ray; + + void _clear_temporals(); + + public: + + /// \e + LpSoplex(); + /// \e + LpSoplex(const LpSoplex&); + /// \e + ~LpSoplex(); + + protected: + + virtual LpSoplex* _newSolver() const; + virtual LpSoplex* _cloneSolver() const; + + virtual const char* _solverName() const; + + virtual int _addCol(); + virtual int _addRow(); + + virtual void _eraseCol(int i); + virtual void _eraseRow(int i); + + virtual void _eraseColId(int i); + virtual void _eraseRowId(int i); + + virtual void _getColName(int col, std::string& name) const; + virtual void _setColName(int col, const std::string& name); + virtual int _colByName(const std::string& name) const; + + virtual void _getRowName(int row, std::string& name) const; + virtual void _setRowName(int row, const std::string& name); + virtual int _rowByName(const std::string& name) const; + + virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e); + virtual void _getRowCoeffs(int i, InsertIterator b) const; + + virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e); + virtual void _getColCoeffs(int i, InsertIterator b) const; + + virtual void _setCoeff(int row, int col, Value value); + virtual Value _getCoeff(int row, int col) const; + + virtual void _setColLowerBound(int i, Value value); + virtual Value _getColLowerBound(int i) const; + virtual void _setColUpperBound(int i, Value value); + virtual Value _getColUpperBound(int i) const; + + virtual void _setRowLowerBound(int i, Value value); + virtual Value _getRowLowerBound(int i) const; + virtual void _setRowUpperBound(int i, Value value); + virtual Value _getRowUpperBound(int i) const; + + virtual void _setObjCoeffs(ExprIterator b, ExprIterator e); + virtual void _getObjCoeffs(InsertIterator b) const; + + virtual void _setObjCoeff(int i, Value obj_coef); + virtual Value _getObjCoeff(int i) const; + + virtual void _setSense(Sense sense); + virtual Sense _getSense() const; + + virtual 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(); + + }; + +} //END OF NAMESPACE LEMON + +#endif //LEMON_SOPLEX_H + diff --git a/test/lp_test.cc b/test/lp_test.cc --- a/test/lp_test.cc +++ b/test/lp_test.cc @@ -26,19 +26,19 @@ #endif #ifdef HAVE_GLPK -#include +#include #endif #ifdef HAVE_CPLEX -#include +#include #endif #ifdef HAVE_SOPLEX -#include +#include #endif #ifdef HAVE_CLP -#include +#include #endif using namespace lemon; diff --git a/test/mip_test.cc b/test/mip_test.cc --- a/test/mip_test.cc +++ b/test/mip_test.cc @@ -24,11 +24,11 @@ #endif #ifdef HAVE_CPLEX -#include +#include #endif #ifdef HAVE_GLPK -#include +#include #endif