1.1 --- a/lemon/config.h.in Tue Apr 08 15:16:16 2008 +0000
1.2 +++ b/lemon/config.h.in Tue Apr 08 16:01:28 2008 +0000
1.3 @@ -3,3 +3,6 @@
1.4
1.5 /* Define to 1 if you have GLPK. */
1.6 #undef HAVE_GLPK
1.7 +
1.8 +/* Define to 1 if you have SOPLEX. */
1.9 +#undef HAVE_SOPLEX
2.1 --- a/lemon/lp_base.h Tue Apr 08 15:16:16 2008 +0000
2.2 +++ b/lemon/lp_base.h Tue Apr 08 16:01:28 2008 +0000
2.3 @@ -371,25 +371,6 @@
2.4 return *this;
2.5 }
2.6
2.7 - //std::ostream &
2.8 - void prettyPrint(std::ostream &os) {
2.9 - //std::fmtflags os.flags();
2.10 - //os.setf(std::ios::showpos);
2.11 - Base::iterator j=Base::begin();
2.12 - if (j!=Base::end())
2.13 - os<<j->second<<"*x["<<id(j->first)<<"]";
2.14 - ++j;
2.15 - for (; j!=Base::end(); ++j){
2.16 - if (j->second>=0)
2.17 - os<<"+";
2.18 - os<<j->second<<"*x["<<id(j->first)<<"]";
2.19 - }
2.20 - //Nem valami korrekt, de nem talaltam meg, hogy kell
2.21 - //os.unsetf(std::ios::showpos);
2.22 -
2.23 - //return os;
2.24 - }
2.25 -
2.26 };
2.27
2.28 ///Linear constraint
2.29 @@ -481,19 +462,6 @@
2.30 return isFinite(_ub);
2.31 }
2.32
2.33 - void prettyPrint(std::ostream &os) {
2.34 - if (_lb==-LpSolverBase::INF||isNaN(_lb))
2.35 - os<<"-infty<=";
2.36 - else
2.37 - os<<_lb<<"<=";
2.38 - _expr.prettyPrint(os);
2.39 - if (_ub==LpSolverBase::INF)
2.40 - os<<"<=infty";
2.41 - else
2.42 - os<<"<="<<_ub;
2.43 - //return os;
2.44 - }
2.45 -
2.46 };
2.47
2.48 ///Linear expression of rows
2.49 @@ -735,15 +703,33 @@
2.50 typedef MappedOutputIterator<DualExpr> ColIterator;
2.51
2.52 //Abstract virtual functions
2.53 - virtual LpSolverBase &_newLp() = 0;
2.54 - virtual LpSolverBase &_copyLp(){
2.55 - ///\todo This should be implemented here, too, when we have
2.56 - ///problem retrieving routines. It can be overriden.
2.57 + virtual LpSolverBase* _newLp() = 0;
2.58 + virtual LpSolverBase* _copyLp(){
2.59 + LpSolverBase* newlp = _newLp();
2.60
2.61 - //Starting:
2.62 - LpSolverBase & newlp(_newLp());
2.63 + std::map<Col, Col> ref;
2.64 + for (LpSolverBase::ColIt it(*this); it != INVALID; ++it) {
2.65 + Col ccol = newlp->addCol();
2.66 + ref[it] = ccol;
2.67 + newlp->colName(ccol, colName(it));
2.68 + newlp->colLowerBound(ccol, colLowerBound(it));
2.69 + newlp->colUpperBound(ccol, colUpperBound(it));
2.70 + }
2.71 +
2.72 + for (LpSolverBase::RowIt it(*this); it != INVALID; ++it) {
2.73 + Expr e = row(it), ce;
2.74 + for (Expr::iterator jt = e.begin(); jt != e.end(); ++jt) {
2.75 + ce[ref[jt->first]] = jt->second;
2.76 + }
2.77 + ce += e.constComp();
2.78 + Row r = newlp->addRow(ce);
2.79 +
2.80 + double lower, upper;
2.81 + getRowBounds(it, lower, upper);
2.82 + newlp->rowBounds(r, lower, upper);
2.83 + }
2.84 +
2.85 return newlp;
2.86 - //return *(LpSolverBase*)0;
2.87 };
2.88
2.89 virtual int _addCol() = 0;
2.90 @@ -804,9 +790,9 @@
2.91 virtual ~LpSolverBase() {}
2.92
2.93 ///Creates a new LP problem
2.94 - LpSolverBase &newLp() {return _newLp();}
2.95 + LpSolverBase* newLp() {return _newLp();}
2.96 ///Makes a copy of the LP problem
2.97 - LpSolverBase ©Lp() {return _copyLp();}
2.98 + LpSolverBase* copyLp() {return _copyLp();}
2.99
2.100 ///\name Build up and modify the LP
2.101
3.1 --- a/lemon/lp_cplex.cc Tue Apr 08 15:16:16 2008 +0000
3.2 +++ b/lemon/lp_cplex.cc Tue Apr 08 16:01:28 2008 +0000
3.3 @@ -17,47 +17,47 @@
3.4 */
3.5
3.6 #include <iostream>
3.7 +#include <vector>
3.8 #include<lemon/lp_cplex.h>
3.9
3.10 ///\file
3.11 ///\brief Implementation of the LEMON-CPLEX lp solver interface.
3.12 namespace lemon {
3.13
3.14 - LpCplex::LpCplex() : LpSolverBase() {
3.15 + LpCplex::LpCplex() {
3.16 // env = CPXopenCPLEXdevelop(&status);
3.17 env = CPXopenCPLEX(&status);
3.18 lp = CPXcreateprob(env, &status, "LP problem");
3.19 }
3.20 +
3.21 + LpCplex::LpCplex(const LpCplex& cplex) : LpSolverBase() {
3.22 + env = CPXopenCPLEX(&status);
3.23 + lp = CPXcloneprob(env, cplex.lp, &status);
3.24 + rows = cplex.rows;
3.25 + cols = cplex.cols;
3.26 + }
3.27
3.28 LpCplex::~LpCplex() {
3.29 - CPXfreeprob(env,&lp);
3.30 - CPXcloseCPLEX(&env);
3.31 + CPXfreeprob(env,&lp);
3.32 + CPXcloseCPLEX(&env);
3.33 }
3.34
3.35 - LpSolverBase &LpCplex::_newLp()
3.36 + LpSolverBase* LpCplex::_newLp()
3.37 {
3.38 //The first approach opens a new environment
3.39 - LpCplex* newlp=new LpCplex();
3.40 - return *newlp;
3.41 + return new LpCplex();
3.42 }
3.43
3.44 - LpSolverBase &LpCplex::_copyLp() {
3.45 - ///\bug FixID data is not copied!
3.46 - //The first approach opens a new environment
3.47 - LpCplex* newlp=new LpCplex();
3.48 - //The routine CPXcloneprob can be used to create a new CPLEX problem
3.49 - //object and copy all the problem data from an existing problem
3.50 - //object to it. Solution and starting information is not copied.
3.51 - newlp->lp = CPXcloneprob(env, lp, &status);
3.52 - return *newlp;
3.53 + LpSolverBase* LpCplex::_copyLp() {
3.54 + return new LpCplex(*this);
3.55 }
3.56
3.57 int LpCplex::_addCol()
3.58 {
3.59 int i = CPXgetnumcols(env, lp);
3.60 Value lb[1],ub[1];
3.61 - lb[0]=-INF;//-CPX_INFBOUND;
3.62 - ub[0]=INF;//CPX_INFBOUND;
3.63 + lb[0]=-INF;
3.64 + ub[0]=INF;
3.65 status = CPXnewcols(env, lp, 1, NULL, lb, ub, NULL, NULL);
3.66 return i;
3.67 }
3.68 @@ -89,7 +89,11 @@
3.69 ///\bug Untested
3.70 int storespace;
3.71 CPXgetcolname(env, lp, 0, 0, 0, &storespace, col, col);
3.72 -
3.73 + if (storespace == 0) {
3.74 + name.clear();
3.75 + return;
3.76 + }
3.77 +
3.78 storespace *= -1;
3.79 std::vector<char> buf(storespace);
3.80 char *names[1];
3.81 @@ -136,6 +140,21 @@
3.82 }
3.83
3.84 void LpCplex::_getRowCoeffs(int i, RowIterator b) const {
3.85 + int tmp1, tmp2, tmp3, length;
3.86 + CPXgetrows(env, lp, &tmp1, &tmp2, 0, 0, 0, &length, i, i);
3.87 +
3.88 + length = -length;
3.89 + std::vector<int> indices(length);
3.90 + std::vector<double> values(length);
3.91 +
3.92 + CPXgetrows(env, lp, &tmp1, &tmp2, &indices[0], &values[0],
3.93 + length, &tmp3, i, i);
3.94 +
3.95 + for (int i = 0; i < length; ++i) {
3.96 + *b = std::make_pair(indices[i], values[i]);
3.97 + ++b;
3.98 + }
3.99 +
3.100 /// \todo implement
3.101 }
3.102
3.103 @@ -156,7 +175,22 @@
3.104 }
3.105
3.106 void LpCplex::_getColCoeffs(int i, ColIterator b) const {
3.107 - /// \todo implement
3.108 +
3.109 + int tmp1, tmp2, tmp3, length;
3.110 + CPXgetcols(env, lp, &tmp1, &tmp2, 0, 0, 0, &length, i, i);
3.111 +
3.112 + length = -length;
3.113 + std::vector<int> indices(length);
3.114 + std::vector<double> values(length);
3.115 +
3.116 + CPXgetcols(env, lp, &tmp1, &tmp2, &indices[0], &values[0],
3.117 + length, &tmp3, i, i);
3.118 +
3.119 + for (int i = 0; i < length; ++i) {
3.120 + *b = std::make_pair(indices[i], values[i]);
3.121 + ++b;
3.122 + }
3.123 +
3.124 }
3.125
3.126 void LpCplex::_setCoeff(int row, int col, Value value)
3.127 @@ -187,6 +221,7 @@
3.128 {
3.129 LpCplex::Value x;
3.130 CPXgetlb (env, lp, &x, i, i);
3.131 + if (x <= -CPX_INFBOUND) x = -INF;
3.132 return x;
3.133 }
3.134
3.135 @@ -205,6 +240,7 @@
3.136 {
3.137 LpCplex::Value x;
3.138 CPXgetub (env, lp, &x, i, i);
3.139 + if (x >= CPX_INFBOUND) x = INF;
3.140 return x;
3.141 }
3.142
3.143 @@ -469,8 +505,8 @@
3.144 // Default: 0
3.145 // Description: Method for linear optimization.
3.146 // 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
3.147 +#if CPX_VERSION < 900
3.148 void statusSwitch(CPXENVptr env,int& stat){
3.149 -#if CPX_VERSION < 900
3.150 int lpmethod;
3.151 CPXgetintparam (env,CPX_PARAM_LPMETHOD,&lpmethod);
3.152 if (lpmethod==2){
3.153 @@ -482,8 +518,10 @@
3.154 stat=CPX_UNBOUNDED;
3.155 }
3.156 }
3.157 + }
3.158 +#else
3.159 + void statusSwitch(CPXENVptr,int&){}
3.160 #endif
3.161 - }
3.162
3.163 LpCplex::SolutionStatus LpCplex::_getPrimalStatus() const
3.164 {
4.1 --- a/lemon/lp_cplex.h Tue Apr 08 15:16:16 2008 +0000
4.2 +++ b/lemon/lp_cplex.h Tue Apr 08 16:01:28 2008 +0000
4.3 @@ -49,11 +49,13 @@
4.4 /// \e
4.5 LpCplex();
4.6 /// \e
4.7 + LpCplex(const LpCplex&);
4.8 + /// \e
4.9 ~LpCplex();
4.10
4.11 protected:
4.12 - virtual LpSolverBase &_newLp();
4.13 - virtual LpSolverBase &_copyLp();
4.14 + virtual LpSolverBase* _newLp();
4.15 + virtual LpSolverBase* _copyLp();
4.16
4.17
4.18 virtual int _addCol();
4.19 @@ -100,6 +102,11 @@
4.20
4.21 virtual bool _isMax() const;
4.22
4.23 + public:
4.24 +
4.25 + CPXENVptr cplexEnv() { return env; }
4.26 + CPXLPptr cplexLp() { return lp; }
4.27 +
4.28 };
4.29 } //END OF NAMESPACE LEMON
4.30
5.1 --- a/lemon/lp_glpk.cc Tue Apr 08 15:16:16 2008 +0000
5.2 +++ b/lemon/lp_glpk.cc Tue Apr 08 16:01:28 2008 +0000
5.3 @@ -89,6 +89,8 @@
5.4 LEMON_glp(get_col_lb)(glp.lp,i),
5.5 LEMON_glp(get_col_ub)(glp.lp,i));
5.6 }
5.7 + rows = glp.rows;
5.8 + cols = glp.cols;
5.9 }
5.10
5.11 LpGlpk::~LpGlpk() {
5.12 @@ -105,18 +107,18 @@
5.13 ///\e
5.14
5.15
5.16 - LpSolverBase &LpGlpk::_newLp()
5.17 + LpSolverBase* LpGlpk::_newLp()
5.18 {
5.19 - LpGlpk* newlp=new LpGlpk;
5.20 - return *newlp;
5.21 + LpGlpk* newlp = new LpGlpk;
5.22 + return newlp;
5.23 }
5.24
5.25 ///\e
5.26
5.27 - LpSolverBase &LpGlpk::_copyLp()
5.28 + LpSolverBase* LpGlpk::_copyLp()
5.29 {
5.30 - LpGlpk* newlp=new LpGlpk(*this);
5.31 - return *newlp;
5.32 + LpGlpk *newlp = new LpGlpk(*this);
5.33 + return newlp;
5.34 }
5.35
5.36 int LpGlpk::_addRow() {
6.1 --- a/lemon/lp_glpk.h Tue Apr 08 15:16:16 2008 +0000
6.2 +++ b/lemon/lp_glpk.h Tue Apr 08 16:01:28 2008 +0000
6.3 @@ -49,8 +49,8 @@
6.4 ~LpGlpk();
6.5
6.6 protected:
6.7 - virtual LpSolverBase &_newLp();
6.8 - virtual LpSolverBase &_copyLp();
6.9 + virtual LpSolverBase* _newLp();
6.10 + virtual LpSolverBase* _copyLp();
6.11
6.12 virtual int _addCol();
6.13 virtual int _addRow();
6.14 @@ -120,6 +120,12 @@
6.15
6.16 ///Pointer to the underlying GLPK data structure.
6.17 LPX *lpx() {return lp;}
6.18 +
6.19 + ///Returns the constraint identifier understood by GLPK.
6.20 + int lpxRow(Row r) { return _lpId(r); }
6.21 +
6.22 + ///Returns the variable identifier understood by GLPK.
6.23 + int lpxCol(Col c) { return _lpId(c); }
6.24 };
6.25 } //END OF NAMESPACE LEMON
6.26
7.1 --- a/lemon/lp_skeleton.cc Tue Apr 08 15:16:16 2008 +0000
7.2 +++ b/lemon/lp_skeleton.cc Tue Apr 08 16:01:28 2008 +0000
7.3 @@ -22,16 +22,16 @@
7.4 ///\brief A skeleton file to implement LP solver interfaces
7.5 namespace lemon {
7.6
7.7 - LpSolverBase &LpSkeleton::_newLp()
7.8 + LpSolverBase* LpSkeleton::_newLp()
7.9 {
7.10 LpSolverBase *tmp=0;
7.11 - return *tmp;
7.12 + return tmp;
7.13 }
7.14
7.15 - LpSolverBase &LpSkeleton::_copyLp()
7.16 + LpSolverBase* LpSkeleton::_copyLp()
7.17 {
7.18 LpSolverBase *tmp=0;
7.19 - return *tmp;
7.20 + return tmp;
7.21 }
7.22
7.23 int LpSkeleton::_addCol()
8.1 --- a/lemon/lp_skeleton.h Tue Apr 08 15:16:16 2008 +0000
8.2 +++ b/lemon/lp_skeleton.h Tue Apr 08 16:01:28 2008 +0000
8.3 @@ -32,9 +32,9 @@
8.4 protected:
8.5
8.6 ///\e
8.7 - virtual LpSolverBase &_newLp();
8.8 + virtual LpSolverBase* _newLp();
8.9 ///\e
8.10 - virtual LpSolverBase &_copyLp();
8.11 + virtual LpSolverBase* _copyLp();
8.12 /// \e
8.13 virtual int _addCol();
8.14 /// \e
9.1 --- a/lemon/lp_soplex.cc Tue Apr 08 15:16:16 2008 +0000
9.2 +++ b/lemon/lp_soplex.cc Tue Apr 08 16:01:28 2008 +0000
9.3 @@ -36,16 +36,33 @@
9.4 LpSoplex::~LpSoplex() {
9.5 delete soplex;
9.6 }
9.7 +
9.8 + LpSoplex::LpSoplex(const LpSoplex& lp) : LpSolverBase() {
9.9 + rows = lp.rows;
9.10 + rows.setIdHandler(relocateIdHandler);
9.11 +
9.12 + cols = lp.cols;
9.13 + cols.setIdHandler(relocateIdHandler);
9.14 +
9.15 + soplex = new soplex::SoPlex;
9.16 + (*static_cast<soplex::SPxLP*>(soplex)) = *(lp.soplex);
9.17 +
9.18 + colNames = lp.colNames;
9.19 + invColNames = lp.invColNames;
9.20 +
9.21 + primal_value = lp.primal_value;
9.22 + dual_value = lp.dual_value;
9.23 +
9.24 + }
9.25
9.26 - LpSolverBase &LpSoplex::_newLp() {
9.27 + LpSolverBase* LpSoplex::_newLp() {
9.28 LpSoplex* newlp = new LpSoplex();
9.29 - return *newlp;
9.30 + return newlp;
9.31 }
9.32
9.33 - LpSolverBase &LpSoplex::_copyLp() {
9.34 - LpSoplex* newlp = new LpSoplex();
9.35 - (*static_cast<soplex::SPxLP*>(newlp->soplex)) = *soplex;
9.36 - return *newlp;
9.37 + LpSolverBase* LpSoplex::_copyLp() {
9.38 + LpSoplex* newlp = new LpSoplex(*this);
9.39 + return newlp;
9.40 }
9.41
9.42 int LpSoplex::_addCol() {
10.1 --- a/lemon/lp_soplex.h Tue Apr 08 15:16:16 2008 +0000
10.2 +++ b/lemon/lp_soplex.h Tue Apr 08 16:01:28 2008 +0000
10.3 @@ -66,12 +66,14 @@
10.4 /// \e
10.5 LpSoplex();
10.6 /// \e
10.7 + LpSoplex(const LpSoplex&);
10.8 + /// \e
10.9 ~LpSoplex();
10.10
10.11 protected:
10.12
10.13 - virtual LpSolverBase &_newLp();
10.14 - virtual LpSolverBase &_copyLp();
10.15 + virtual LpSolverBase* _newLp();
10.16 + virtual LpSolverBase* _copyLp();
10.17
10.18 virtual int _addCol();
10.19 virtual int _addRow();
11.1 --- a/test/lp_test.cc Tue Apr 08 15:16:16 2008 +0000
11.2 +++ b/test/lp_test.cc Tue Apr 08 16:01:28 2008 +0000
11.3 @@ -20,6 +20,7 @@
11.4 #include <lemon/lp_skeleton.h>
11.5 #include "test_tools.h"
11.6 #include <lemon/tolerance.h>
11.7 +#include <lemon/lp_utils.h>
11.8
11.9 #ifdef HAVE_CONFIG_H
11.10 #include <lemon/config.h>
11.11 @@ -216,7 +217,8 @@
11.12
11.13 {
11.14 LP::DualExpr e,f,g;
11.15 - LP::Row p1,p2,p3,p4,p5;
11.16 + LP::Row p1 = INVALID, p2 = INVALID, p3 = INVALID,
11.17 + p4 = INVALID, p5 = INVALID;
11.18
11.19 e[p1]=2;
11.20 e[p1]+=2;
11.21 @@ -295,7 +297,6 @@
11.22
11.23 lp.max();
11.24
11.25 -
11.26 //Testing the problem retrieving routines
11.27 check(lp.objCoeff(x1)==1,"First term should be 1 in the obj function!");
11.28 check(lp.isMax(),"This is a maximization!");
11.29 @@ -307,7 +308,39 @@
11.30 lp.getRowBounds(upright,lb,ub);
11.31 check( lb==-LpSolverBase::INF,"The lower bound for the first row should be -infty.");
11.32 check( ub==1,"The upper bound for the first row should be 1.");
11.33 + LpSolverBase::Expr e = lp.row(upright);
11.34 + check( e.size() == 2, "The row retrieval gives back wrong expression.");
11.35 + check( e[x1] == 1, "The first coefficient should 1.");
11.36 + check( e[x2] == 1, "The second coefficient should 1.");
11.37
11.38 + LpSolverBase::DualExpr de = lp.col(x1);
11.39 + check( de.size() == 4, "The col retrieval gives back wrong expression.");
11.40 + check( de[upright] == 1, "The first coefficient should 1.");
11.41 +
11.42 + LpSolverBase* clp = lp.copyLp();
11.43 +
11.44 + //Testing the problem retrieving routines
11.45 + check(clp->objCoeff(x1)==1,"First term should be 1 in the obj function!");
11.46 + check(clp->isMax(),"This is a maximization!");
11.47 + check(clp->coeff(upright,x1)==1,"The coefficient in question is 1!");
11.48 + // std::cout<<lp.colLowerBound(x1)<<std::endl;
11.49 + check( clp->colLowerBound(x1)==0,"The lower bound for variable x1 should be 0.");
11.50 + std::cerr << clp->colUpperBound(x1) << std::endl;
11.51 + check( clp->colUpperBound(x1)==LpSolverBase::INF,"The upper bound for variable x1 should be infty.");
11.52 +
11.53 + clp->getRowBounds(upright,lb,ub);
11.54 + check( lb==-LpSolverBase::INF,"The lower bound for the first row should be -infty.");
11.55 + check( ub==1,"The upper bound for the first row should be 1.");
11.56 + e = clp->row(upright);
11.57 + check( e.size() == 2, "The row retrieval gives back wrong expression.");
11.58 + check( e[x1] == 1, "The first coefficient should 1.");
11.59 + check( e[x2] == 1, "The second coefficient should 1.");
11.60 +
11.61 + de = clp->col(x1);
11.62 + check( de.size() == 4, "The col retrieval gives back wrong expression.");
11.63 + check( de[upright] == 1, "The first coefficient should 1.");
11.64 +
11.65 + delete clp;
11.66
11.67 //Maximization of x1+x2
11.68 //over the triangle with vertices (0,0) (0,1) (1,0)
11.69 @@ -338,6 +371,7 @@
11.70 lp.min();
11.71 check(lp.primalStatus()==LpSolverBase::UNDEFINED,"Primalstatus should be UNDEFINED");
11.72
11.73 +
11.74 // lp.solve();
11.75 // if (lp.primalStatus()==LpSolverBase::OPTIMAL){
11.76 // std::cout<< "Z = "<<lp.primalValue()