# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 1231763161 0
# Node ID 08d495d480899a56e5065a17058edb9e9ad325fc
# Parent 76ec7bd57026964284fe00990441ced0ea3faa5e
Remove lp_ prefix from the solver's header name
diff -r 76ec7bd57026 -r 08d495d48089 lemon/Makefile.am
--- a/lemon/Makefile.am Mon Jan 12 12:25:55 2009 +0000
+++ b/lemon/Makefile.am Mon Jan 12 12:26:01 2009 +0000
@@ -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 -r 76ec7bd57026 -r 08d495d48089 lemon/clp.cc
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/clp.cc Mon Jan 12 12:26:01 2009 +0000
@@ -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 <lemon/clp.h>
+#include <coin/ClpSimplex.hpp>
+
+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<std::string&>(name));
+ _col_names_ref[name] = c;
+ }
+
+ int LpClp::_colByName(const std::string& name) const {
+ std::map<std::string, int>::const_iterator it = _col_names_ref.find(name);
+ return it != _col_names_ref.end() ? it->second : -1;
+ }
+
+ void 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<std::string&>(name));
+ _row_names_ref[name] = r;
+ }
+
+ int LpClp::_rowByName(const std::string& name) const {
+ std::map<std::string, int>::const_iterator it = _row_names_ref.find(name);
+ return it != _row_names_ref.end() ? it->second : -1;
+ }
+
+
+ void LpClp::_setRowCoeffs(int ix, ExprIterator b, ExprIterator e) {
+ std::map<int, Value> coeffs;
+
+ int n = _prob->clpMatrix()->getNumCols();
+
+ const int* indices = _prob->clpMatrix()->getIndices();
+ const double* elements = _prob->clpMatrix()->getElements();
+
+ for (int i = 0; i < n; ++i) {
+ CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i];
+ CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i];
+
+ const int* it = std::lower_bound(indices + begin, indices + end, ix);
+ if (it != indices + end && *it == ix && elements[it - indices] != 0.0) {
+ coeffs[i] = 0.0;
+ }
+ }
+
+ for (ExprIterator it = b; it != e; ++it) {
+ coeffs[it->first] = it->second;
+ }
+
+ for (std::map<int, Value>::iterator it = coeffs.begin();
+ it != coeffs.end(); ++it) {
+ _prob->modifyCoefficient(ix, it->first, it->second);
+ }
+ }
+
+ void 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<int, Value> coeffs;
+
+ CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];
+ CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];
+
+ const int* indices = _prob->clpMatrix()->getIndices();
+ const double* elements = _prob->clpMatrix()->getElements();
+
+ for (CoinBigIndex i = begin; i != end; ++i) {
+ if (elements[i] != 0.0) {
+ coeffs[indices[i]] = 0.0;
+ }
+ }
+ for (ExprIterator it = b; it != e; ++it) {
+ coeffs[it->first] = it->second;
+ }
+ for (std::map<int, Value>::iterator it = coeffs.begin();
+ it != coeffs.end(); ++it) {
+ _prob->modifyCoefficient(it->first, ix, it->second);
+ }
+ }
+
+ void 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<int>(m));
+ }
+
+} //END OF NAMESPACE LEMON
diff -r 76ec7bd57026 -r 08d495d48089 lemon/clp.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/clp.h Mon Jan 12 12:26:01 2009 +0000
@@ -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 <vector>
+#include <string>
+
+#include <lemon/lp_base.h>
+
+class ClpSimplex;
+
+namespace lemon {
+
+ /// \ingroup lp_group
+ ///
+ /// \brief Interface for the CLP solver
+ ///
+ /// This class implements an interface for the Clp LP solver. The
+ /// Clp library is an object oriented lp solver library developed at
+ /// the IBM. The CLP is part of the COIN-OR package and it can be
+ /// used with Common Public License.
+ class LpClp : public LpSolver {
+ protected:
+
+ ClpSimplex* _prob;
+
+ std::map<std::string, int> _col_names_ref;
+ std::map<std::string, int> _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 -r 76ec7bd57026 -r 08d495d48089 lemon/cplex.cc
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/cplex.cc Mon Jan 12 12:26:01 2009 +0000
@@ -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 <iostream>
+#include <vector>
+#include <cstring>
+
+#include <lemon/cplex.h>
+
+extern "C" {
+#include <ilcplex/cplex.h>
+}
+
+
+///\file
+///\brief Implementation of the LEMON-CPLEX lp solver interface.
+namespace lemon {
+
+ CplexEnv::LicenseError::LicenseError(int status) {
+ if (!CPXgeterrorstring(0, status, _message)) {
+ std::strcpy(_message, "Cplex unknown error");
+ }
+ }
+
+ CplexEnv::CplexEnv() {
+ int status;
+ _cnt = new int;
+ _env = CPXopenCPLEX(&status);
+ if (_env == 0) {
+ delete _cnt;
+ _cnt = 0;
+ throw LicenseError(status);
+ }
+ }
+
+ CplexEnv::CplexEnv(const CplexEnv& other) {
+ _env = other._env;
+ _cnt = other._cnt;
+ ++(*_cnt);
+ }
+
+ CplexEnv& CplexEnv::operator=(const CplexEnv& other) {
+ _env = other._env;
+ _cnt = other._cnt;
+ ++(*_cnt);
+ return *this;
+ }
+
+ CplexEnv::~CplexEnv() {
+ --(*_cnt);
+ if (*_cnt == 0) {
+ delete _cnt;
+ CPXcloseCPLEX(&_env);
+ }
+ }
+
+ CplexBase::CplexBase() : LpBase() {
+ int status;
+ _prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem");
+ }
+
+ 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<char> buf(size);
+ char *cname;
+ int tmp;
+ CPXgetcolname(cplexEnv(), _prob, &cname, &buf.front(), size,
+ &tmp, col, col);
+ name = cname;
+ }
+
+ void CplexBase::_setColName(int col, const std::string &name) {
+ char *cname;
+ cname = const_cast<char*>(name.c_str());
+ CPXchgcolname(cplexEnv(), _prob, 1, &col, &cname);
+ }
+
+ int CplexBase::_colByName(const std::string& name) const {
+ int index;
+ if (CPXgetcolindex(cplexEnv(), _prob,
+ const_cast<char*>(name.c_str()), &index) == 0) {
+ return index;
+ }
+ return -1;
+ }
+
+ void CplexBase::_getRowName(int row, std::string &name) const {
+ int size;
+ CPXgetrowname(cplexEnv(), _prob, 0, 0, 0, &size, row, row);
+ if (size == 0) {
+ name.clear();
+ return;
+ }
+
+ size *= -1;
+ std::vector<char> buf(size);
+ char *cname;
+ int tmp;
+ CPXgetrowname(cplexEnv(), _prob, &cname, &buf.front(), size,
+ &tmp, row, row);
+ name = cname;
+ }
+
+ void CplexBase::_setRowName(int row, const std::string &name) {
+ char *cname;
+ cname = const_cast<char*>(name.c_str());
+ CPXchgrowname(cplexEnv(), _prob, 1, &row, &cname);
+ }
+
+ int CplexBase::_rowByName(const std::string& name) const {
+ int index;
+ if (CPXgetrowindex(cplexEnv(), _prob,
+ const_cast<char*>(name.c_str()), &index) == 0) {
+ return index;
+ }
+ return -1;
+ }
+
+ void CplexBase::_setRowCoeffs(int i, ExprIterator b,
+ ExprIterator e)
+ {
+ std::vector<int> indices;
+ std::vector<int> rowlist;
+ std::vector<Value> values;
+
+ for(ExprIterator it=b; it!=e; ++it) {
+ indices.push_back(it->first);
+ values.push_back(it->second);
+ rowlist.push_back(i);
+ }
+
+ CPXchgcoeflist(cplexEnv(), _prob, values.size(),
+ &rowlist.front(), &indices.front(), &values.front());
+ }
+
+ void CplexBase::_getRowCoeffs(int i, InsertIterator b) const {
+ int tmp1, tmp2, tmp3, length;
+ CPXgetrows(cplexEnv(), _prob, &tmp1, &tmp2, 0, 0, 0, &length, i, i);
+
+ length = -length;
+ std::vector<int> indices(length);
+ std::vector<double> values(length);
+
+ CPXgetrows(cplexEnv(), _prob, &tmp1, &tmp2,
+ &indices.front(), &values.front(),
+ length, &tmp3, i, i);
+
+ for (int i = 0; i < length; ++i) {
+ *b = std::make_pair(indices[i], values[i]);
+ ++b;
+ }
+ }
+
+ void CplexBase::_setColCoeffs(int i, ExprIterator b, ExprIterator e) {
+ std::vector<int> indices;
+ std::vector<int> collist;
+ std::vector<Value> values;
+
+ for(ExprIterator it=b; it!=e; ++it) {
+ indices.push_back(it->first);
+ values.push_back(it->second);
+ collist.push_back(i);
+ }
+
+ CPXchgcoeflist(cplexEnv(), _prob, values.size(),
+ &indices.front(), &collist.front(), &values.front());
+ }
+
+ void CplexBase::_getColCoeffs(int i, InsertIterator b) const {
+
+ int tmp1, tmp2, tmp3, length;
+ CPXgetcols(cplexEnv(), _prob, &tmp1, &tmp2, 0, 0, 0, &length, i, i);
+
+ length = -length;
+ std::vector<int> indices(length);
+ std::vector<double> values(length);
+
+ CPXgetcols(cplexEnv(), _prob, &tmp1, &tmp2,
+ &indices.front(), &values.front(),
+ length, &tmp3, i, i);
+
+ for (int i = 0; i < length; ++i) {
+ *b = std::make_pair(indices[i], values[i]);
+ ++b;
+ }
+
+ }
+
+ void CplexBase::_setCoeff(int row, int col, Value value) {
+ CPXchgcoef(cplexEnv(), _prob, row, col, value);
+ }
+
+ CplexBase::Value CplexBase::_getCoeff(int row, int col) const {
+ CplexBase::Value value;
+ CPXgetcoef(cplexEnv(), _prob, row, col, &value);
+ return value;
+ }
+
+ void CplexBase::_setColLowerBound(int i, Value value) {
+ const char s = 'L';
+ CPXchgbds(cplexEnv(), _prob, 1, &i, &s, &value);
+ }
+
+ CplexBase::Value CplexBase::_getColLowerBound(int i) const {
+ CplexBase::Value res;
+ CPXgetlb(cplexEnv(), _prob, &res, i, i);
+ return res <= -CPX_INFBOUND ? -INF : res;
+ }
+
+ void CplexBase::_setColUpperBound(int i, Value value)
+ {
+ const char s = 'U';
+ CPXchgbds(cplexEnv(), _prob, 1, &i, &s, &value);
+ }
+
+ CplexBase::Value CplexBase::_getColUpperBound(int i) const {
+ CplexBase::Value res;
+ CPXgetub(cplexEnv(), _prob, &res, i, i);
+ return res >= CPX_INFBOUND ? INF : res;
+ }
+
+ CplexBase::Value CplexBase::_getRowLowerBound(int i) const {
+ char s;
+ CPXgetsense(cplexEnv(), _prob, &s, i, i);
+ CplexBase::Value res;
+
+ switch (s) {
+ case 'G':
+ case 'R':
+ case 'E':
+ CPXgetrhs(cplexEnv(), _prob, &res, i, i);
+ return res <= -CPX_INFBOUND ? -INF : res;
+ default:
+ return -INF;
+ }
+ }
+
+ CplexBase::Value CplexBase::_getRowUpperBound(int i) const {
+ char s;
+ CPXgetsense(cplexEnv(), _prob, &s, i, i);
+ CplexBase::Value res;
+
+ switch (s) {
+ case 'L':
+ case 'E':
+ CPXgetrhs(cplexEnv(), _prob, &res, i, i);
+ return res >= CPX_INFBOUND ? INF : res;
+ case 'R':
+ CPXgetrhs(cplexEnv(), _prob, &res, i, i);
+ {
+ double rng;
+ CPXgetrngval(cplexEnv(), _prob, &rng, i, i);
+ res += rng;
+ }
+ return res >= CPX_INFBOUND ? INF : res;
+ default:
+ return INF;
+ }
+ }
+
+ //This is easier to implement
+ void CplexBase::_set_row_bounds(int i, Value lb, Value ub) {
+ if (lb == -INF) {
+ const char s = 'L';
+ CPXchgsense(cplexEnv(), _prob, 1, &i, &s);
+ CPXchgrhs(cplexEnv(), _prob, 1, &i, &ub);
+ } else if (ub == INF) {
+ const char s = 'G';
+ CPXchgsense(cplexEnv(), _prob, 1, &i, &s);
+ CPXchgrhs(cplexEnv(), _prob, 1, &i, &lb);
+ } else if (lb == ub){
+ const char s = 'E';
+ CPXchgsense(cplexEnv(), _prob, 1, &i, &s);
+ CPXchgrhs(cplexEnv(), _prob, 1, &i, &lb);
+ } else {
+ const char s = 'R';
+ CPXchgsense(cplexEnv(), _prob, 1, &i, &s);
+ CPXchgrhs(cplexEnv(), _prob, 1, &i, &lb);
+ double len = ub - lb;
+ CPXchgrngval(cplexEnv(), _prob, 1, &i, &len);
+ }
+ }
+
+ void CplexBase::_setRowLowerBound(int i, Value lb)
+ {
+ LEMON_ASSERT(lb != INF, "Invalid bound");
+ _set_row_bounds(i, lb, CplexBase::_getRowUpperBound(i));
+ }
+
+ void CplexBase::_setRowUpperBound(int i, Value ub)
+ {
+
+ LEMON_ASSERT(ub != -INF, "Invalid bound");
+ _set_row_bounds(i, CplexBase::_getRowLowerBound(i), ub);
+ }
+
+ void CplexBase::_setObjCoeffs(ExprIterator b, ExprIterator e)
+ {
+ std::vector<int> indices;
+ std::vector<Value> values;
+ for(ExprIterator it=b; it!=e; ++it) {
+ indices.push_back(it->first);
+ values.push_back(it->second);
+ }
+ CPXchgobj(cplexEnv(), _prob, values.size(),
+ &indices.front(), &values.front());
+
+ }
+
+ void CplexBase::_getObjCoeffs(InsertIterator b) const
+ {
+ int num = CPXgetnumcols(cplexEnv(), _prob);
+ std::vector<Value> x(num);
+
+ CPXgetobj(cplexEnv(), _prob, &x.front(), 0, num - 1);
+ for (int i = 0; i < num; ++i) {
+ if (x[i] != 0.0) {
+ *b = std::make_pair(i, x[i]);
+ ++b;
+ }
+ }
+ }
+
+ void CplexBase::_setObjCoeff(int i, Value obj_coef)
+ {
+ CPXchgobj(cplexEnv(), _prob, 1, &i, &obj_coef);
+ }
+
+ CplexBase::Value CplexBase::_getObjCoeff(int i) const
+ {
+ Value x;
+ CPXgetobj(cplexEnv(), _prob, &x, i, i);
+ return x;
+ }
+
+ void CplexBase::_setSense(CplexBase::Sense sense) {
+ switch (sense) {
+ case MIN:
+ CPXchgobjsen(cplexEnv(), _prob, CPX_MIN);
+ break;
+ case MAX:
+ CPXchgobjsen(cplexEnv(), _prob, CPX_MAX);
+ break;
+ }
+ }
+
+ CplexBase::Sense CplexBase::_getSense() const {
+ switch (CPXgetobjsen(cplexEnv(), _prob)) {
+ case CPX_MIN:
+ return MIN;
+ case CPX_MAX:
+ return MAX;
+ default:
+ LEMON_ASSERT(false, "Invalid sense");
+ return CplexBase::Sense();
+ }
+ }
+
+ void CplexBase::_clear() {
+ CPXfreeprob(cplexEnv(),&_prob);
+ int status;
+ _prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem");
+ rows.clear();
+ cols.clear();
+ }
+
+ // 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 -r 76ec7bd57026 -r 08d495d48089 lemon/cplex.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/cplex.h Mon Jan 12 12:26:01 2009 +0000
@@ -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 <lemon/lp_base.h>
+
+struct cpxenv;
+struct cpxlp;
+
+namespace lemon {
+
+ /// \brief Reference counted wrapper around cpxenv pointer
+ ///
+ /// The cplex uses environment object which is responsible for
+ /// checking the proper license usage. This class provides a simple
+ /// interface for share the environment object between different
+ /// problems.
+ class CplexEnv {
+ friend class CplexBase;
+ private:
+ cpxenv* _env;
+ mutable int* _cnt;
+
+ public:
+
+ /// \brief This exception is thrown when the license check is not
+ /// sufficient
+ class LicenseError : public Exception {
+ friend class CplexEnv;
+ private:
+
+ LicenseError(int status);
+ char _message[510];
+
+ public:
+
+ /// The short error message
+ virtual const char* what() const throw() {
+ return _message;
+ }
+ };
+
+ /// Constructor
+ CplexEnv();
+ /// Shallow copy constructor
+ CplexEnv(const CplexEnv&);
+ /// Shallow assignement
+ CplexEnv& operator=(const CplexEnv&);
+ /// Destructor
+ virtual ~CplexEnv();
+
+ protected:
+
+ cpxenv* cplexEnv() { return _env; }
+ const cpxenv* cplexEnv() const { return _env; }
+ };
+
+ /// \brief Base interface for the CPLEX LP and MIP solver
+ ///
+ /// This class implements the common interface of the CPLEX LP and
+ /// MIP solvers.
+ /// \ingroup lp_group
+ class CplexBase : virtual public LpBase {
+ protected:
+
+ CplexEnv _env;
+ cpxlp* _prob;
+
+ CplexBase();
+ CplexBase(const CplexEnv&);
+ CplexBase(const CplexBase &);
+ virtual ~CplexBase();
+
+ virtual int _addCol();
+ virtual int _addRow();
+
+ virtual 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<int> _col_status;
+ mutable std::vector<int> _row_status;
+
+ mutable std::vector<Value> _primal_ray;
+ mutable std::vector<Value> _dual_ray;
+
+ void _clear_temporals();
+
+ SolveExitStatus convertStatus(int status);
+
+ protected:
+
+ virtual 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 -r 76ec7bd57026 -r 08d495d48089 lemon/glpk.cc
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/glpk.cc Mon Jan 12 12:26:01 2009 +0000
@@ -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 <lemon/glpk.h>
+#include <glpk.h>
+
+#include <lemon/assert.h>
+
+namespace lemon {
+
+ // GlpkBase members
+
+ GlpkBase::GlpkBase() : LpBase() {
+ lp = glp_create_prob();
+ glp_create_index(lp);
+ }
+
+ 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<char*>(name.c_str()));
+
+ }
+
+ int GlpkBase::_colByName(const std::string& name) const {
+ int k = glp_find_col(lp, const_cast<char*>(name.c_str()));
+ return k > 0 ? k : -1;
+ }
+
+ void GlpkBase::_getRowName(int r, std::string& name) const {
+ const char *str = glp_get_row_name(lp, r);
+ if (str) name = str;
+ else name.clear();
+ }
+
+ void GlpkBase::_setRowName(int r, const std::string & name) {
+ glp_set_row_name(lp, r, const_cast<char*>(name.c_str()));
+
+ }
+
+ int GlpkBase::_rowByName(const std::string& name) const {
+ int k = glp_find_row(lp, const_cast<char*>(name.c_str()));
+ return k > 0 ? k : -1;
+ }
+
+ void GlpkBase::_setRowCoeffs(int i, ExprIterator b, ExprIterator e) {
+ std::vector<int> indexes;
+ std::vector<Value> values;
+
+ indexes.push_back(0);
+ values.push_back(0);
+
+ for(ExprIterator it = b; it != e; ++it) {
+ indexes.push_back(it->first);
+ values.push_back(it->second);
+ }
+
+ glp_set_mat_row(lp, i, values.size() - 1,
+ &indexes.front(), &values.front());
+ }
+
+ void GlpkBase::_getRowCoeffs(int ix, InsertIterator b) const {
+ int length = glp_get_mat_row(lp, ix, 0, 0);
+
+ std::vector<int> indexes(length + 1);
+ std::vector<Value> values(length + 1);
+
+ glp_get_mat_row(lp, ix, &indexes.front(), &values.front());
+
+ for (int i = 1; i <= length; ++i) {
+ *b = std::make_pair(indexes[i], values[i]);
+ ++b;
+ }
+ }
+
+ void GlpkBase::_setColCoeffs(int ix, ExprIterator b,
+ ExprIterator e) {
+
+ std::vector<int> indexes;
+ std::vector<Value> values;
+
+ indexes.push_back(0);
+ values.push_back(0);
+
+ for(ExprIterator it = b; it != e; ++it) {
+ indexes.push_back(it->first);
+ values.push_back(it->second);
+ }
+
+ glp_set_mat_col(lp, ix, values.size() - 1,
+ &indexes.front(), &values.front());
+ }
+
+ void GlpkBase::_getColCoeffs(int ix, InsertIterator b) const {
+ int length = glp_get_mat_col(lp, ix, 0, 0);
+
+ std::vector<int> indexes(length + 1);
+ std::vector<Value> values(length + 1);
+
+ glp_get_mat_col(lp, ix, &indexes.front(), &values.front());
+
+ for (int i = 1; i <= length; ++i) {
+ *b = std::make_pair(indexes[i], values[i]);
+ ++b;
+ }
+ }
+
+ void GlpkBase::_setCoeff(int ix, int jx, Value value) {
+
+ if (glp_get_num_cols(lp) < glp_get_num_rows(lp)) {
+
+ int length = glp_get_mat_row(lp, ix, 0, 0);
+
+ std::vector<int> indexes(length + 2);
+ std::vector<Value> values(length + 2);
+
+ glp_get_mat_row(lp, ix, &indexes.front(), &values.front());
+
+ //The following code does not suppose that the elements of the
+ //array indexes are sorted
+ bool found = false;
+ for (int i = 1; i <= length; ++i) {
+ if (indexes[i] == jx) {
+ found = true;
+ values[i] = value;
+ break;
+ }
+ }
+ if (!found) {
+ ++length;
+ indexes[length] = jx;
+ values[length] = value;
+ }
+
+ glp_set_mat_row(lp, ix, length, &indexes.front(), &values.front());
+
+ } else {
+
+ int length = glp_get_mat_col(lp, jx, 0, 0);
+
+ std::vector<int> indexes(length + 2);
+ std::vector<Value> values(length + 2);
+
+ glp_get_mat_col(lp, jx, &indexes.front(), &values.front());
+
+ //The following code does not suppose that the elements of the
+ //array indexes are sorted
+ bool found = false;
+ for (int i = 1; i <= length; ++i) {
+ if (indexes[i] == ix) {
+ found = true;
+ values[i] = value;
+ break;
+ }
+ }
+ if (!found) {
+ ++length;
+ indexes[length] = ix;
+ values[length] = value;
+ }
+
+ glp_set_mat_col(lp, jx, length, &indexes.front(), &values.front());
+ }
+
+ }
+
+ GlpkBase::Value GlpkBase::_getCoeff(int ix, int jx) const {
+
+ int length = glp_get_mat_row(lp, ix, 0, 0);
+
+ std::vector<int> indexes(length + 1);
+ std::vector<Value> values(length + 1);
+
+ glp_get_mat_row(lp, ix, &indexes.front(), &values.front());
+
+ for (int i = 1; i <= length; ++i) {
+ if (indexes[i] == jx) {
+ return values[i];
+ }
+ }
+
+ return 0;
+ }
+
+ void GlpkBase::_setColLowerBound(int i, Value lo) {
+ LEMON_ASSERT(lo != INF, "Invalid bound");
+
+ int b = glp_get_col_type(lp, i);
+ double up = glp_get_col_ub(lp, i);
+ if (lo == -INF) {
+ switch (b) {
+ case GLP_FR:
+ case GLP_LO:
+ glp_set_col_bnds(lp, i, GLP_FR, lo, up);
+ break;
+ case GLP_UP:
+ break;
+ case GLP_DB:
+ case GLP_FX:
+ glp_set_col_bnds(lp, i, GLP_UP, lo, up);
+ break;
+ default:
+ break;
+ }
+ } else {
+ switch (b) {
+ case GLP_FR:
+ case GLP_LO:
+ glp_set_col_bnds(lp, i, GLP_LO, lo, up);
+ break;
+ case GLP_UP:
+ case GLP_DB:
+ case GLP_FX:
+ if (lo == up)
+ glp_set_col_bnds(lp, i, GLP_FX, lo, up);
+ else
+ glp_set_col_bnds(lp, i, GLP_DB, lo, up);
+ break;
+ default:
+ break;
+ }
+ }
+ }
+
+ GlpkBase::Value GlpkBase::_getColLowerBound(int i) const {
+ int b = glp_get_col_type(lp, i);
+ switch (b) {
+ case GLP_LO:
+ case GLP_DB:
+ case GLP_FX:
+ return glp_get_col_lb(lp, i);
+ default:
+ return -INF;
+ }
+ }
+
+ void GlpkBase::_setColUpperBound(int i, Value up) {
+ LEMON_ASSERT(up != -INF, "Invalid bound");
+
+ int b = glp_get_col_type(lp, i);
+ double lo = glp_get_col_lb(lp, i);
+ if (up == INF) {
+ switch (b) {
+ case GLP_FR:
+ case GLP_LO:
+ break;
+ case GLP_UP:
+ glp_set_col_bnds(lp, i, GLP_FR, lo, up);
+ break;
+ case GLP_DB:
+ case GLP_FX:
+ glp_set_col_bnds(lp, i, GLP_LO, lo, up);
+ break;
+ default:
+ break;
+ }
+ } else {
+ switch (b) {
+ case GLP_FR:
+ glp_set_col_bnds(lp, i, GLP_UP, lo, up);
+ break;
+ case GLP_UP:
+ glp_set_col_bnds(lp, i, GLP_UP, lo, up);
+ break;
+ case GLP_LO:
+ case GLP_DB:
+ case GLP_FX:
+ if (lo == up)
+ glp_set_col_bnds(lp, i, GLP_FX, lo, up);
+ else
+ glp_set_col_bnds(lp, i, GLP_DB, lo, up);
+ break;
+ default:
+ break;
+ }
+ }
+
+ }
+
+ GlpkBase::Value GlpkBase::_getColUpperBound(int i) const {
+ int b = glp_get_col_type(lp, i);
+ switch (b) {
+ case GLP_UP:
+ case GLP_DB:
+ case GLP_FX:
+ return glp_get_col_ub(lp, i);
+ default:
+ return INF;
+ }
+ }
+
+ void GlpkBase::_setRowLowerBound(int i, Value lo) {
+ LEMON_ASSERT(lo != INF, "Invalid bound");
+
+ int b = glp_get_row_type(lp, i);
+ double up = glp_get_row_ub(lp, i);
+ if (lo == -INF) {
+ switch (b) {
+ case GLP_FR:
+ case GLP_LO:
+ glp_set_row_bnds(lp, i, GLP_FR, lo, up);
+ break;
+ case GLP_UP:
+ break;
+ case GLP_DB:
+ case GLP_FX:
+ glp_set_row_bnds(lp, i, GLP_UP, lo, up);
+ break;
+ default:
+ break;
+ }
+ } else {
+ switch (b) {
+ case GLP_FR:
+ case GLP_LO:
+ glp_set_row_bnds(lp, i, GLP_LO, lo, up);
+ break;
+ case GLP_UP:
+ case GLP_DB:
+ case GLP_FX:
+ if (lo == up)
+ glp_set_row_bnds(lp, i, GLP_FX, lo, up);
+ else
+ glp_set_row_bnds(lp, i, GLP_DB, lo, up);
+ break;
+ default:
+ break;
+ }
+ }
+
+ }
+
+ GlpkBase::Value GlpkBase::_getRowLowerBound(int i) const {
+ int b = glp_get_row_type(lp, i);
+ switch (b) {
+ case GLP_LO:
+ case GLP_DB:
+ case GLP_FX:
+ return glp_get_row_lb(lp, i);
+ default:
+ return -INF;
+ }
+ }
+
+ void GlpkBase::_setRowUpperBound(int i, Value up) {
+ LEMON_ASSERT(up != -INF, "Invalid bound");
+
+ int b = glp_get_row_type(lp, i);
+ double lo = glp_get_row_lb(lp, i);
+ if (up == INF) {
+ switch (b) {
+ case GLP_FR:
+ case GLP_LO:
+ break;
+ case GLP_UP:
+ glp_set_row_bnds(lp, i, GLP_FR, lo, up);
+ break;
+ case GLP_DB:
+ case GLP_FX:
+ glp_set_row_bnds(lp, i, GLP_LO, lo, up);
+ break;
+ default:
+ break;
+ }
+ } else {
+ switch (b) {
+ case GLP_FR:
+ glp_set_row_bnds(lp, i, GLP_UP, lo, up);
+ break;
+ case GLP_UP:
+ glp_set_row_bnds(lp, i, GLP_UP, lo, up);
+ break;
+ case GLP_LO:
+ case GLP_DB:
+ case GLP_FX:
+ if (lo == up)
+ glp_set_row_bnds(lp, i, GLP_FX, lo, up);
+ else
+ glp_set_row_bnds(lp, i, GLP_DB, lo, up);
+ break;
+ default:
+ break;
+ }
+ }
+ }
+
+ GlpkBase::Value GlpkBase::_getRowUpperBound(int i) const {
+ int b = glp_get_row_type(lp, i);
+ switch (b) {
+ case GLP_UP:
+ case GLP_DB:
+ case GLP_FX:
+ return glp_get_row_ub(lp, i);
+ default:
+ return INF;
+ }
+ }
+
+ void GlpkBase::_setObjCoeffs(ExprIterator b, ExprIterator e) {
+ for (int i = 1; i <= glp_get_num_cols(lp); ++i) {
+ glp_set_obj_coef(lp, i, 0.0);
+ }
+ for (ExprIterator it = b; it != e; ++it) {
+ glp_set_obj_coef(lp, it->first, it->second);
+ }
+ }
+
+ void GlpkBase::_getObjCoeffs(InsertIterator b) const {
+ for (int i = 1; i <= glp_get_num_cols(lp); ++i) {
+ Value val = glp_get_obj_coef(lp, i);
+ if (val != 0.0) {
+ *b = std::make_pair(i, val);
+ ++b;
+ }
+ }
+ }
+
+ void GlpkBase::_setObjCoeff(int i, Value obj_coef) {
+ //i = 0 means the constant term (shift)
+ glp_set_obj_coef(lp, i, obj_coef);
+ }
+
+ GlpkBase::Value GlpkBase::_getObjCoeff(int i) const {
+ //i = 0 means the constant term (shift)
+ return glp_get_obj_coef(lp, i);
+ }
+
+ void GlpkBase::_setSense(GlpkBase::Sense sense) {
+ switch (sense) {
+ case MIN:
+ glp_set_obj_dir(lp, GLP_MIN);
+ break;
+ case MAX:
+ glp_set_obj_dir(lp, GLP_MAX);
+ break;
+ }
+ }
+
+ GlpkBase::Sense GlpkBase::_getSense() const {
+ switch(glp_get_obj_dir(lp)) {
+ case GLP_MIN:
+ return MIN;
+ case GLP_MAX:
+ return MAX;
+ default:
+ LEMON_ASSERT(false, "Wrong sense");
+ return GlpkBase::Sense();
+ }
+ }
+
+ void GlpkBase::_clear() {
+ glp_erase_prob(lp);
+ rows.clear();
+ cols.clear();
+ }
+
+ // 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<int> ray_indexes(row_num + 1);
+ std::vector<Value> 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 -r 76ec7bd57026 -r 08d495d48089 lemon/glpk.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/glpk.h Mon Jan 12 12:26:01 2009 +0000
@@ -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 <lemon/lp_base.h>
+
+// 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<double> _primal_ray;
+ mutable std::vector<double> _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 -r 76ec7bd57026 -r 08d495d48089 lemon/lp.h
--- a/lemon/lp.h Mon Jan 12 12:25:55 2009 +0000
+++ b/lemon/lp.h Mon Jan 12 12:26:01 2009 +0000
@@ -23,13 +23,13 @@
#ifdef HAVE_GLPK
-#include <lemon/lp_glpk.h>
+#include <lemon/glpk.h>
#elif HAVE_CPLEX
-#include <lemon/lp_cplex.h>
+#include <lemon/cplex.h>
#elif HAVE_SOPLEX
-#include <lemon/lp_soplex.h>
+#include <lemon/soplex.h>
#elif HAVE_CLP
-#include <lemon/lp_clp.h>
+#include <lemon/clp.h>
#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 -r 76ec7bd57026 -r 08d495d48089 lemon/lp_clp.cc
--- a/lemon/lp_clp.cc Mon Jan 12 12:25:55 2009 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -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 <lemon/lp_clp.h>
-#include <coin/ClpSimplex.hpp>
-
-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<std::string&>(name));
- _col_names_ref[name] = c;
- }
-
- int LpClp::_colByName(const std::string& name) const {
- std::map<std::string, int>::const_iterator it = _col_names_ref.find(name);
- return it != _col_names_ref.end() ? it->second : -1;
- }
-
- void 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<std::string&>(name));
- _row_names_ref[name] = r;
- }
-
- int LpClp::_rowByName(const std::string& name) const {
- std::map<std::string, int>::const_iterator it = _row_names_ref.find(name);
- return it != _row_names_ref.end() ? it->second : -1;
- }
-
-
- void LpClp::_setRowCoeffs(int ix, ExprIterator b, ExprIterator e) {
- std::map<int, Value> coeffs;
-
- int n = _prob->clpMatrix()->getNumCols();
-
- const int* indices = _prob->clpMatrix()->getIndices();
- const double* elements = _prob->clpMatrix()->getElements();
-
- for (int i = 0; i < n; ++i) {
- CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i];
- CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i];
-
- const int* it = std::lower_bound(indices + begin, indices + end, ix);
- if (it != indices + end && *it == ix && elements[it - indices] != 0.0) {
- coeffs[i] = 0.0;
- }
- }
-
- for (ExprIterator it = b; it != e; ++it) {
- coeffs[it->first] = it->second;
- }
-
- for (std::map<int, Value>::iterator it = coeffs.begin();
- it != coeffs.end(); ++it) {
- _prob->modifyCoefficient(ix, it->first, it->second);
- }
- }
-
- void 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<int, Value> coeffs;
-
- CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];
- CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];
-
- const int* indices = _prob->clpMatrix()->getIndices();
- const double* elements = _prob->clpMatrix()->getElements();
-
- for (CoinBigIndex i = begin; i != end; ++i) {
- if (elements[i] != 0.0) {
- coeffs[indices[i]] = 0.0;
- }
- }
- for (ExprIterator it = b; it != e; ++it) {
- coeffs[it->first] = it->second;
- }
- for (std::map<int, Value>::iterator it = coeffs.begin();
- it != coeffs.end(); ++it) {
- _prob->modifyCoefficient(it->first, ix, it->second);
- }
- }
-
- void 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<int>(m));
- }
-
-} //END OF NAMESPACE LEMON
diff -r 76ec7bd57026 -r 08d495d48089 lemon/lp_clp.h
--- a/lemon/lp_clp.h Mon Jan 12 12:25:55 2009 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -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 <vector>
-#include <string>
-
-#include <lemon/lp_base.h>
-
-class ClpSimplex;
-
-namespace lemon {
-
- /// \ingroup lp_group
- ///
- /// \brief Interface for the CLP solver
- ///
- /// This class implements an interface for the Clp LP solver. The
- /// Clp library is an object oriented lp solver library developed at
- /// the IBM. The CLP is part of the COIN-OR package and it can be
- /// used with Common Public License.
- class LpClp : public LpSolver {
- protected:
-
- ClpSimplex* _prob;
-
- std::map<std::string, int> _col_names_ref;
- std::map<std::string, int> _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 -r 76ec7bd57026 -r 08d495d48089 lemon/lp_cplex.cc
--- a/lemon/lp_cplex.cc Mon Jan 12 12:25:55 2009 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -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 <iostream>
-#include <vector>
-#include <cstring>
-
-#include <lemon/lp_cplex.h>
-
-extern "C" {
-#include <ilcplex/cplex.h>
-}
-
-
-///\file
-///\brief Implementation of the LEMON-CPLEX lp solver interface.
-namespace lemon {
-
- CplexEnv::LicenseError::LicenseError(int status) {
- if (!CPXgeterrorstring(0, status, _message)) {
- std::strcpy(_message, "Cplex unknown error");
- }
- }
-
- CplexEnv::CplexEnv() {
- int status;
- _cnt = new int;
- _env = CPXopenCPLEX(&status);
- if (_env == 0) {
- delete _cnt;
- _cnt = 0;
- throw LicenseError(status);
- }
- }
-
- CplexEnv::CplexEnv(const CplexEnv& other) {
- _env = other._env;
- _cnt = other._cnt;
- ++(*_cnt);
- }
-
- CplexEnv& CplexEnv::operator=(const CplexEnv& other) {
- _env = other._env;
- _cnt = other._cnt;
- ++(*_cnt);
- return *this;
- }
-
- CplexEnv::~CplexEnv() {
- --(*_cnt);
- if (*_cnt == 0) {
- delete _cnt;
- CPXcloseCPLEX(&_env);
- }
- }
-
- CplexBase::CplexBase() : LpBase() {
- int status;
- _prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem");
- }
-
- 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<char> buf(size);
- char *cname;
- int tmp;
- CPXgetcolname(cplexEnv(), _prob, &cname, &buf.front(), size,
- &tmp, col, col);
- name = cname;
- }
-
- void CplexBase::_setColName(int col, const std::string &name) {
- char *cname;
- cname = const_cast<char*>(name.c_str());
- CPXchgcolname(cplexEnv(), _prob, 1, &col, &cname);
- }
-
- int CplexBase::_colByName(const std::string& name) const {
- int index;
- if (CPXgetcolindex(cplexEnv(), _prob,
- const_cast<char*>(name.c_str()), &index) == 0) {
- return index;
- }
- return -1;
- }
-
- void CplexBase::_getRowName(int row, std::string &name) const {
- int size;
- CPXgetrowname(cplexEnv(), _prob, 0, 0, 0, &size, row, row);
- if (size == 0) {
- name.clear();
- return;
- }
-
- size *= -1;
- std::vector<char> buf(size);
- char *cname;
- int tmp;
- CPXgetrowname(cplexEnv(), _prob, &cname, &buf.front(), size,
- &tmp, row, row);
- name = cname;
- }
-
- void CplexBase::_setRowName(int row, const std::string &name) {
- char *cname;
- cname = const_cast<char*>(name.c_str());
- CPXchgrowname(cplexEnv(), _prob, 1, &row, &cname);
- }
-
- int CplexBase::_rowByName(const std::string& name) const {
- int index;
- if (CPXgetrowindex(cplexEnv(), _prob,
- const_cast<char*>(name.c_str()), &index) == 0) {
- return index;
- }
- return -1;
- }
-
- void CplexBase::_setRowCoeffs(int i, ExprIterator b,
- ExprIterator e)
- {
- std::vector<int> indices;
- std::vector<int> rowlist;
- std::vector<Value> values;
-
- for(ExprIterator it=b; it!=e; ++it) {
- indices.push_back(it->first);
- values.push_back(it->second);
- rowlist.push_back(i);
- }
-
- CPXchgcoeflist(cplexEnv(), _prob, values.size(),
- &rowlist.front(), &indices.front(), &values.front());
- }
-
- void CplexBase::_getRowCoeffs(int i, InsertIterator b) const {
- int tmp1, tmp2, tmp3, length;
- CPXgetrows(cplexEnv(), _prob, &tmp1, &tmp2, 0, 0, 0, &length, i, i);
-
- length = -length;
- std::vector<int> indices(length);
- std::vector<double> values(length);
-
- CPXgetrows(cplexEnv(), _prob, &tmp1, &tmp2,
- &indices.front(), &values.front(),
- length, &tmp3, i, i);
-
- for (int i = 0; i < length; ++i) {
- *b = std::make_pair(indices[i], values[i]);
- ++b;
- }
- }
-
- void CplexBase::_setColCoeffs(int i, ExprIterator b, ExprIterator e) {
- std::vector<int> indices;
- std::vector<int> collist;
- std::vector<Value> values;
-
- for(ExprIterator it=b; it!=e; ++it) {
- indices.push_back(it->first);
- values.push_back(it->second);
- collist.push_back(i);
- }
-
- CPXchgcoeflist(cplexEnv(), _prob, values.size(),
- &indices.front(), &collist.front(), &values.front());
- }
-
- void CplexBase::_getColCoeffs(int i, InsertIterator b) const {
-
- int tmp1, tmp2, tmp3, length;
- CPXgetcols(cplexEnv(), _prob, &tmp1, &tmp2, 0, 0, 0, &length, i, i);
-
- length = -length;
- std::vector<int> indices(length);
- std::vector<double> values(length);
-
- CPXgetcols(cplexEnv(), _prob, &tmp1, &tmp2,
- &indices.front(), &values.front(),
- length, &tmp3, i, i);
-
- for (int i = 0; i < length; ++i) {
- *b = std::make_pair(indices[i], values[i]);
- ++b;
- }
-
- }
-
- void CplexBase::_setCoeff(int row, int col, Value value) {
- CPXchgcoef(cplexEnv(), _prob, row, col, value);
- }
-
- CplexBase::Value CplexBase::_getCoeff(int row, int col) const {
- CplexBase::Value value;
- CPXgetcoef(cplexEnv(), _prob, row, col, &value);
- return value;
- }
-
- void CplexBase::_setColLowerBound(int i, Value value) {
- const char s = 'L';
- CPXchgbds(cplexEnv(), _prob, 1, &i, &s, &value);
- }
-
- CplexBase::Value CplexBase::_getColLowerBound(int i) const {
- CplexBase::Value res;
- CPXgetlb(cplexEnv(), _prob, &res, i, i);
- return res <= -CPX_INFBOUND ? -INF : res;
- }
-
- void CplexBase::_setColUpperBound(int i, Value value)
- {
- const char s = 'U';
- CPXchgbds(cplexEnv(), _prob, 1, &i, &s, &value);
- }
-
- CplexBase::Value CplexBase::_getColUpperBound(int i) const {
- CplexBase::Value res;
- CPXgetub(cplexEnv(), _prob, &res, i, i);
- return res >= CPX_INFBOUND ? INF : res;
- }
-
- CplexBase::Value CplexBase::_getRowLowerBound(int i) const {
- char s;
- CPXgetsense(cplexEnv(), _prob, &s, i, i);
- CplexBase::Value res;
-
- switch (s) {
- case 'G':
- case 'R':
- case 'E':
- CPXgetrhs(cplexEnv(), _prob, &res, i, i);
- return res <= -CPX_INFBOUND ? -INF : res;
- default:
- return -INF;
- }
- }
-
- CplexBase::Value CplexBase::_getRowUpperBound(int i) const {
- char s;
- CPXgetsense(cplexEnv(), _prob, &s, i, i);
- CplexBase::Value res;
-
- switch (s) {
- case 'L':
- case 'E':
- CPXgetrhs(cplexEnv(), _prob, &res, i, i);
- return res >= CPX_INFBOUND ? INF : res;
- case 'R':
- CPXgetrhs(cplexEnv(), _prob, &res, i, i);
- {
- double rng;
- CPXgetrngval(cplexEnv(), _prob, &rng, i, i);
- res += rng;
- }
- return res >= CPX_INFBOUND ? INF : res;
- default:
- return INF;
- }
- }
-
- //This is easier to implement
- void CplexBase::_set_row_bounds(int i, Value lb, Value ub) {
- if (lb == -INF) {
- const char s = 'L';
- CPXchgsense(cplexEnv(), _prob, 1, &i, &s);
- CPXchgrhs(cplexEnv(), _prob, 1, &i, &ub);
- } else if (ub == INF) {
- const char s = 'G';
- CPXchgsense(cplexEnv(), _prob, 1, &i, &s);
- CPXchgrhs(cplexEnv(), _prob, 1, &i, &lb);
- } else if (lb == ub){
- const char s = 'E';
- CPXchgsense(cplexEnv(), _prob, 1, &i, &s);
- CPXchgrhs(cplexEnv(), _prob, 1, &i, &lb);
- } else {
- const char s = 'R';
- CPXchgsense(cplexEnv(), _prob, 1, &i, &s);
- CPXchgrhs(cplexEnv(), _prob, 1, &i, &lb);
- double len = ub - lb;
- CPXchgrngval(cplexEnv(), _prob, 1, &i, &len);
- }
- }
-
- void CplexBase::_setRowLowerBound(int i, Value lb)
- {
- LEMON_ASSERT(lb != INF, "Invalid bound");
- _set_row_bounds(i, lb, CplexBase::_getRowUpperBound(i));
- }
-
- void CplexBase::_setRowUpperBound(int i, Value ub)
- {
-
- LEMON_ASSERT(ub != -INF, "Invalid bound");
- _set_row_bounds(i, CplexBase::_getRowLowerBound(i), ub);
- }
-
- void CplexBase::_setObjCoeffs(ExprIterator b, ExprIterator e)
- {
- std::vector<int> indices;
- std::vector<Value> values;
- for(ExprIterator it=b; it!=e; ++it) {
- indices.push_back(it->first);
- values.push_back(it->second);
- }
- CPXchgobj(cplexEnv(), _prob, values.size(),
- &indices.front(), &values.front());
-
- }
-
- void CplexBase::_getObjCoeffs(InsertIterator b) const
- {
- int num = CPXgetnumcols(cplexEnv(), _prob);
- std::vector<Value> x(num);
-
- CPXgetobj(cplexEnv(), _prob, &x.front(), 0, num - 1);
- for (int i = 0; i < num; ++i) {
- if (x[i] != 0.0) {
- *b = std::make_pair(i, x[i]);
- ++b;
- }
- }
- }
-
- void CplexBase::_setObjCoeff(int i, Value obj_coef)
- {
- CPXchgobj(cplexEnv(), _prob, 1, &i, &obj_coef);
- }
-
- CplexBase::Value CplexBase::_getObjCoeff(int i) const
- {
- Value x;
- CPXgetobj(cplexEnv(), _prob, &x, i, i);
- return x;
- }
-
- void CplexBase::_setSense(CplexBase::Sense sense) {
- switch (sense) {
- case MIN:
- CPXchgobjsen(cplexEnv(), _prob, CPX_MIN);
- break;
- case MAX:
- CPXchgobjsen(cplexEnv(), _prob, CPX_MAX);
- break;
- }
- }
-
- CplexBase::Sense CplexBase::_getSense() const {
- switch (CPXgetobjsen(cplexEnv(), _prob)) {
- case CPX_MIN:
- return MIN;
- case CPX_MAX:
- return MAX;
- default:
- LEMON_ASSERT(false, "Invalid sense");
- return CplexBase::Sense();
- }
- }
-
- void CplexBase::_clear() {
- CPXfreeprob(cplexEnv(),&_prob);
- int status;
- _prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem");
- rows.clear();
- cols.clear();
- }
-
- // 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 -r 76ec7bd57026 -r 08d495d48089 lemon/lp_cplex.h
--- a/lemon/lp_cplex.h Mon Jan 12 12:25:55 2009 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -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 <lemon/lp_base.h>
-
-struct cpxenv;
-struct cpxlp;
-
-namespace lemon {
-
- /// \brief Reference counted wrapper around cpxenv pointer
- ///
- /// The cplex uses environment object which is responsible for
- /// checking the proper license usage. This class provides a simple
- /// interface for share the environment object between different
- /// problems.
- class CplexEnv {
- friend class CplexBase;
- private:
- cpxenv* _env;
- mutable int* _cnt;
-
- public:
-
- /// \brief This exception is thrown when the license check is not
- /// sufficient
- class LicenseError : public Exception {
- friend class CplexEnv;
- private:
-
- LicenseError(int status);
- char _message[510];
-
- public:
-
- /// The short error message
- virtual const char* what() const throw() {
- return _message;
- }
- };
-
- /// Constructor
- CplexEnv();
- /// Shallow copy constructor
- CplexEnv(const CplexEnv&);
- /// Shallow assignement
- CplexEnv& operator=(const CplexEnv&);
- /// Destructor
- virtual ~CplexEnv();
-
- protected:
-
- cpxenv* cplexEnv() { return _env; }
- const cpxenv* cplexEnv() const { return _env; }
- };
-
- /// \brief Base interface for the CPLEX LP and MIP solver
- ///
- /// This class implements the common interface of the CPLEX LP and
- /// MIP solvers.
- /// \ingroup lp_group
- class CplexBase : virtual public LpBase {
- protected:
-
- CplexEnv _env;
- cpxlp* _prob;
-
- CplexBase();
- CplexBase(const CplexEnv&);
- CplexBase(const CplexBase &);
- virtual ~CplexBase();
-
- virtual int _addCol();
- virtual int _addRow();
-
- virtual 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<int> _col_status;
- mutable std::vector<int> _row_status;
-
- mutable std::vector<Value> _primal_ray;
- mutable std::vector<Value> _dual_ray;
-
- void _clear_temporals();
-
- SolveExitStatus convertStatus(int status);
-
- protected:
-
- virtual 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 -r 76ec7bd57026 -r 08d495d48089 lemon/lp_glpk.cc
--- a/lemon/lp_glpk.cc Mon Jan 12 12:25:55 2009 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -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 <lemon/lp_glpk.h>
-#include <glpk.h>
-
-#include <lemon/assert.h>
-
-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<char*>(name.c_str()));
-
- }
-
- int GlpkBase::_colByName(const std::string& name) const {
- int k = glp_find_col(lp, const_cast<char*>(name.c_str()));
- return k > 0 ? k : -1;
- }
-
- void GlpkBase::_getRowName(int r, std::string& name) const {
- const char *str = glp_get_row_name(lp, r);
- if (str) name = str;
- else name.clear();
- }
-
- void GlpkBase::_setRowName(int r, const std::string & name) {
- glp_set_row_name(lp, r, const_cast<char*>(name.c_str()));
-
- }
-
- int GlpkBase::_rowByName(const std::string& name) const {
- int k = glp_find_row(lp, const_cast<char*>(name.c_str()));
- return k > 0 ? k : -1;
- }
-
- void GlpkBase::_setRowCoeffs(int i, ExprIterator b, ExprIterator e) {
- std::vector<int> indexes;
- std::vector<Value> values;
-
- indexes.push_back(0);
- values.push_back(0);
-
- for(ExprIterator it = b; it != e; ++it) {
- indexes.push_back(it->first);
- values.push_back(it->second);
- }
-
- glp_set_mat_row(lp, i, values.size() - 1,
- &indexes.front(), &values.front());
- }
-
- void GlpkBase::_getRowCoeffs(int ix, InsertIterator b) const {
- int length = glp_get_mat_row(lp, ix, 0, 0);
-
- std::vector<int> indexes(length + 1);
- std::vector<Value> values(length + 1);
-
- glp_get_mat_row(lp, ix, &indexes.front(), &values.front());
-
- for (int i = 1; i <= length; ++i) {
- *b = std::make_pair(indexes[i], values[i]);
- ++b;
- }
- }
-
- void GlpkBase::_setColCoeffs(int ix, ExprIterator b,
- ExprIterator e) {
-
- std::vector<int> indexes;
- std::vector<Value> values;
-
- indexes.push_back(0);
- values.push_back(0);
-
- for(ExprIterator it = b; it != e; ++it) {
- indexes.push_back(it->first);
- values.push_back(it->second);
- }
-
- glp_set_mat_col(lp, ix, values.size() - 1,
- &indexes.front(), &values.front());
- }
-
- void GlpkBase::_getColCoeffs(int ix, InsertIterator b) const {
- int length = glp_get_mat_col(lp, ix, 0, 0);
-
- std::vector<int> indexes(length + 1);
- std::vector<Value> values(length + 1);
-
- glp_get_mat_col(lp, ix, &indexes.front(), &values.front());
-
- for (int i = 1; i <= length; ++i) {
- *b = std::make_pair(indexes[i], values[i]);
- ++b;
- }
- }
-
- void GlpkBase::_setCoeff(int ix, int jx, Value value) {
-
- if (glp_get_num_cols(lp) < glp_get_num_rows(lp)) {
-
- int length = glp_get_mat_row(lp, ix, 0, 0);
-
- std::vector<int> indexes(length + 2);
- std::vector<Value> values(length + 2);
-
- glp_get_mat_row(lp, ix, &indexes.front(), &values.front());
-
- //The following code does not suppose that the elements of the
- //array indexes are sorted
- bool found = false;
- for (int i = 1; i <= length; ++i) {
- if (indexes[i] == jx) {
- found = true;
- values[i] = value;
- break;
- }
- }
- if (!found) {
- ++length;
- indexes[length] = jx;
- values[length] = value;
- }
-
- glp_set_mat_row(lp, ix, length, &indexes.front(), &values.front());
-
- } else {
-
- int length = glp_get_mat_col(lp, jx, 0, 0);
-
- std::vector<int> indexes(length + 2);
- std::vector<Value> values(length + 2);
-
- glp_get_mat_col(lp, jx, &indexes.front(), &values.front());
-
- //The following code does not suppose that the elements of the
- //array indexes are sorted
- bool found = false;
- for (int i = 1; i <= length; ++i) {
- if (indexes[i] == ix) {
- found = true;
- values[i] = value;
- break;
- }
- }
- if (!found) {
- ++length;
- indexes[length] = ix;
- values[length] = value;
- }
-
- glp_set_mat_col(lp, jx, length, &indexes.front(), &values.front());
- }
-
- }
-
- GlpkBase::Value GlpkBase::_getCoeff(int ix, int jx) const {
-
- int length = glp_get_mat_row(lp, ix, 0, 0);
-
- std::vector<int> indexes(length + 1);
- std::vector<Value> values(length + 1);
-
- glp_get_mat_row(lp, ix, &indexes.front(), &values.front());
-
- for (int i = 1; i <= length; ++i) {
- if (indexes[i] == jx) {
- return values[i];
- }
- }
-
- return 0;
- }
-
- void GlpkBase::_setColLowerBound(int i, Value lo) {
- LEMON_ASSERT(lo != INF, "Invalid bound");
-
- int b = glp_get_col_type(lp, i);
- double up = glp_get_col_ub(lp, i);
- if (lo == -INF) {
- switch (b) {
- case GLP_FR:
- case GLP_LO:
- glp_set_col_bnds(lp, i, GLP_FR, lo, up);
- break;
- case GLP_UP:
- break;
- case GLP_DB:
- case GLP_FX:
- glp_set_col_bnds(lp, i, GLP_UP, lo, up);
- break;
- default:
- break;
- }
- } else {
- switch (b) {
- case GLP_FR:
- case GLP_LO:
- glp_set_col_bnds(lp, i, GLP_LO, lo, up);
- break;
- case GLP_UP:
- case GLP_DB:
- case GLP_FX:
- if (lo == up)
- glp_set_col_bnds(lp, i, GLP_FX, lo, up);
- else
- glp_set_col_bnds(lp, i, GLP_DB, lo, up);
- break;
- default:
- break;
- }
- }
- }
-
- GlpkBase::Value GlpkBase::_getColLowerBound(int i) const {
- int b = glp_get_col_type(lp, i);
- switch (b) {
- case GLP_LO:
- case GLP_DB:
- case GLP_FX:
- return glp_get_col_lb(lp, i);
- default:
- return -INF;
- }
- }
-
- void GlpkBase::_setColUpperBound(int i, Value up) {
- LEMON_ASSERT(up != -INF, "Invalid bound");
-
- int b = glp_get_col_type(lp, i);
- double lo = glp_get_col_lb(lp, i);
- if (up == INF) {
- switch (b) {
- case GLP_FR:
- case GLP_LO:
- break;
- case GLP_UP:
- glp_set_col_bnds(lp, i, GLP_FR, lo, up);
- break;
- case GLP_DB:
- case GLP_FX:
- glp_set_col_bnds(lp, i, GLP_LO, lo, up);
- break;
- default:
- break;
- }
- } else {
- switch (b) {
- case GLP_FR:
- glp_set_col_bnds(lp, i, GLP_UP, lo, up);
- break;
- case GLP_UP:
- glp_set_col_bnds(lp, i, GLP_UP, lo, up);
- break;
- case GLP_LO:
- case GLP_DB:
- case GLP_FX:
- if (lo == up)
- glp_set_col_bnds(lp, i, GLP_FX, lo, up);
- else
- glp_set_col_bnds(lp, i, GLP_DB, lo, up);
- break;
- default:
- break;
- }
- }
-
- }
-
- GlpkBase::Value GlpkBase::_getColUpperBound(int i) const {
- int b = glp_get_col_type(lp, i);
- switch (b) {
- case GLP_UP:
- case GLP_DB:
- case GLP_FX:
- return glp_get_col_ub(lp, i);
- default:
- return INF;
- }
- }
-
- void GlpkBase::_setRowLowerBound(int i, Value lo) {
- LEMON_ASSERT(lo != INF, "Invalid bound");
-
- int b = glp_get_row_type(lp, i);
- double up = glp_get_row_ub(lp, i);
- if (lo == -INF) {
- switch (b) {
- case GLP_FR:
- case GLP_LO:
- glp_set_row_bnds(lp, i, GLP_FR, lo, up);
- break;
- case GLP_UP:
- break;
- case GLP_DB:
- case GLP_FX:
- glp_set_row_bnds(lp, i, GLP_UP, lo, up);
- break;
- default:
- break;
- }
- } else {
- switch (b) {
- case GLP_FR:
- case GLP_LO:
- glp_set_row_bnds(lp, i, GLP_LO, lo, up);
- break;
- case GLP_UP:
- case GLP_DB:
- case GLP_FX:
- if (lo == up)
- glp_set_row_bnds(lp, i, GLP_FX, lo, up);
- else
- glp_set_row_bnds(lp, i, GLP_DB, lo, up);
- break;
- default:
- break;
- }
- }
-
- }
-
- GlpkBase::Value GlpkBase::_getRowLowerBound(int i) const {
- int b = glp_get_row_type(lp, i);
- switch (b) {
- case GLP_LO:
- case GLP_DB:
- case GLP_FX:
- return glp_get_row_lb(lp, i);
- default:
- return -INF;
- }
- }
-
- void GlpkBase::_setRowUpperBound(int i, Value up) {
- LEMON_ASSERT(up != -INF, "Invalid bound");
-
- int b = glp_get_row_type(lp, i);
- double lo = glp_get_row_lb(lp, i);
- if (up == INF) {
- switch (b) {
- case GLP_FR:
- case GLP_LO:
- break;
- case GLP_UP:
- glp_set_row_bnds(lp, i, GLP_FR, lo, up);
- break;
- case GLP_DB:
- case GLP_FX:
- glp_set_row_bnds(lp, i, GLP_LO, lo, up);
- break;
- default:
- break;
- }
- } else {
- switch (b) {
- case GLP_FR:
- glp_set_row_bnds(lp, i, GLP_UP, lo, up);
- break;
- case GLP_UP:
- glp_set_row_bnds(lp, i, GLP_UP, lo, up);
- break;
- case GLP_LO:
- case GLP_DB:
- case GLP_FX:
- if (lo == up)
- glp_set_row_bnds(lp, i, GLP_FX, lo, up);
- else
- glp_set_row_bnds(lp, i, GLP_DB, lo, up);
- break;
- default:
- break;
- }
- }
- }
-
- GlpkBase::Value GlpkBase::_getRowUpperBound(int i) const {
- int b = glp_get_row_type(lp, i);
- switch (b) {
- case GLP_UP:
- case GLP_DB:
- case GLP_FX:
- return glp_get_row_ub(lp, i);
- default:
- return INF;
- }
- }
-
- void GlpkBase::_setObjCoeffs(ExprIterator b, ExprIterator e) {
- for (int i = 1; i <= glp_get_num_cols(lp); ++i) {
- glp_set_obj_coef(lp, i, 0.0);
- }
- for (ExprIterator it = b; it != e; ++it) {
- glp_set_obj_coef(lp, it->first, it->second);
- }
- }
-
- void GlpkBase::_getObjCoeffs(InsertIterator b) const {
- for (int i = 1; i <= glp_get_num_cols(lp); ++i) {
- Value val = glp_get_obj_coef(lp, i);
- if (val != 0.0) {
- *b = std::make_pair(i, val);
- ++b;
- }
- }
- }
-
- void GlpkBase::_setObjCoeff(int i, Value obj_coef) {
- //i = 0 means the constant term (shift)
- glp_set_obj_coef(lp, i, obj_coef);
- }
-
- GlpkBase::Value GlpkBase::_getObjCoeff(int i) const {
- //i = 0 means the constant term (shift)
- return glp_get_obj_coef(lp, i);
- }
-
- void GlpkBase::_setSense(GlpkBase::Sense sense) {
- switch (sense) {
- case MIN:
- glp_set_obj_dir(lp, GLP_MIN);
- break;
- case MAX:
- glp_set_obj_dir(lp, GLP_MAX);
- break;
- }
- }
-
- GlpkBase::Sense GlpkBase::_getSense() const {
- switch(glp_get_obj_dir(lp)) {
- case GLP_MIN:
- return MIN;
- case GLP_MAX:
- return MAX;
- default:
- LEMON_ASSERT(false, "Wrong sense");
- return GlpkBase::Sense();
- }
- }
-
- void GlpkBase::_clear() {
- glp_erase_prob(lp);
- rows.clear();
- cols.clear();
- }
-
- // 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<int> ray_indexes(row_num + 1);
- std::vector<Value> 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 -r 76ec7bd57026 -r 08d495d48089 lemon/lp_glpk.h
--- a/lemon/lp_glpk.h Mon Jan 12 12:25:55 2009 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -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 <lemon/lp_base.h>
-
-// 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<double> _primal_ray;
- mutable std::vector<double> _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 -r 76ec7bd57026 -r 08d495d48089 lemon/lp_soplex.cc
--- a/lemon/lp_soplex.cc Mon Jan 12 12:25:55 2009 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -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 <iostream>
-#include <lemon/lp_soplex.h>
-
-#include <soplex/soplex.h>
-
-
-///\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::SPxLP*>(soplex)) = *(lp.soplex);
-
- _col_names = lp._col_names;
- _col_names_ref = lp._col_names_ref;
-
- _row_names = lp._row_names;
- _row_names_ref = lp._row_names_ref;
-
- }
-
- 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<std::string, int>::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<std::string, int>::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 -r 76ec7bd57026 -r 08d495d48089 lemon/lp_soplex.h
--- a/lemon/lp_soplex.h Mon Jan 12 12:25:55 2009 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -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 <vector>
-#include <string>
-
-#include <lemon/lp_base.h>
-
-// Forward declaration
-namespace soplex {
- class SoPlex;
-}
-
-namespace lemon {
-
- /// \ingroup lp_group
- ///
- /// \brief Interface for the SOPLEX solver
- ///
- /// This class implements an interface for the SoPlex LP solver.
- /// The SoPlex library is an object oriented lp solver library
- /// developed at the Konrad-Zuse-Zentrum für Informationstechnik
- /// Berlin (ZIB). You can find detailed information about it at the
- /// <tt>http://soplex.zib.de</tt> address.
- class LpSoplex : public LpSolver {
- private:
-
- soplex::SoPlex* soplex;
-
- std::vector<std::string> _col_names;
- std::map<std::string, int> _col_names_ref;
-
- std::vector<std::string> _row_names;
- std::map<std::string, int> _row_names_ref;
-
- private:
-
- // these values cannot be retrieved element by element
- mutable std::vector<Value> _primal_values;
- mutable std::vector<Value> _dual_values;
-
- mutable std::vector<Value> _primal_ray;
- mutable std::vector<Value> _dual_ray;
-
- void _clear_temporals();
-
- public:
-
- /// \e
- 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 -r 76ec7bd57026 -r 08d495d48089 lemon/soplex.cc
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/soplex.cc Mon Jan 12 12:26:01 2009 +0000
@@ -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 <iostream>
+#include <lemon/soplex.h>
+
+#include <soplex/soplex.h>
+
+
+///\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::SPxLP*>(soplex)) = *(lp.soplex);
+
+ _col_names = lp._col_names;
+ _col_names_ref = lp._col_names_ref;
+
+ _row_names = lp._row_names;
+ _row_names_ref = lp._row_names_ref;
+
+ }
+
+ 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<std::string, int>::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<std::string, int>::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 -r 76ec7bd57026 -r 08d495d48089 lemon/soplex.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/soplex.h Mon Jan 12 12:26:01 2009 +0000
@@ -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 <vector>
+#include <string>
+
+#include <lemon/lp_base.h>
+
+// Forward declaration
+namespace soplex {
+ class SoPlex;
+}
+
+namespace lemon {
+
+ /// \ingroup lp_group
+ ///
+ /// \brief Interface for the SOPLEX solver
+ ///
+ /// This class implements an interface for the SoPlex LP solver.
+ /// The SoPlex library is an object oriented lp solver library
+ /// developed at the Konrad-Zuse-Zentrum für Informationstechnik
+ /// Berlin (ZIB). You can find detailed information about it at the
+ /// <tt>http://soplex.zib.de</tt> address.
+ class LpSoplex : public LpSolver {
+ private:
+
+ soplex::SoPlex* soplex;
+
+ std::vector<std::string> _col_names;
+ std::map<std::string, int> _col_names_ref;
+
+ std::vector<std::string> _row_names;
+ std::map<std::string, int> _row_names_ref;
+
+ private:
+
+ // these values cannot be retrieved element by element
+ mutable std::vector<Value> _primal_values;
+ mutable std::vector<Value> _dual_values;
+
+ mutable std::vector<Value> _primal_ray;
+ mutable std::vector<Value> _dual_ray;
+
+ void _clear_temporals();
+
+ public:
+
+ /// \e
+ 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 -r 76ec7bd57026 -r 08d495d48089 test/lp_test.cc
--- a/test/lp_test.cc Mon Jan 12 12:25:55 2009 +0000
+++ b/test/lp_test.cc Mon Jan 12 12:26:01 2009 +0000
@@ -26,19 +26,19 @@
#endif
#ifdef HAVE_GLPK
-#include <lemon/lp_glpk.h>
+#include <lemon/glpk.h>
#endif
#ifdef HAVE_CPLEX
-#include <lemon/lp_cplex.h>
+#include <lemon/cplex.h>
#endif
#ifdef HAVE_SOPLEX
-#include <lemon/lp_soplex.h>
+#include <lemon/soplex.h>
#endif
#ifdef HAVE_CLP
-#include <lemon/lp_clp.h>
+#include <lemon/clp.h>
#endif
using namespace lemon;
diff -r 76ec7bd57026 -r 08d495d48089 test/mip_test.cc
--- a/test/mip_test.cc Mon Jan 12 12:25:55 2009 +0000
+++ b/test/mip_test.cc Mon Jan 12 12:26:01 2009 +0000
@@ -24,11 +24,11 @@
#endif
#ifdef HAVE_CPLEX
-#include <lemon/lp_cplex.h>
+#include <lemon/cplex.h>
#endif
#ifdef HAVE_GLPK
-#include <lemon/lp_glpk.h>
+#include <lemon/glpk.h>
#endif