Changeset 2605:852361980706 in lemon-0.x

Timestamp:

04/08/08 18:01:28 (16 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3488

Message:

Bug fixes in LP solvers

• the copyLp is clarified
• newLp and copyLp gives back pointers
• cplex gives back empty string for variables without name
• cplex row and column retrieval
• added macro for soplex

Files:

• lemon/config.h.in (modified) (1 diff)
• lemon/lp_base.h (modified) (4 diffs)
• lemon/lp_cplex.cc (modified) (10 diffs)
• lemon/lp_cplex.h (modified) (2 diffs)
• lemon/lp_glpk.cc (modified) (2 diffs)
• lemon/lp_glpk.h (modified) (2 diffs)
• lemon/lp_skeleton.cc (modified) (1 diff)
• lemon/lp_skeleton.h (modified) (1 diff)
• lemon/lp_soplex.cc (modified) (1 diff)
• lemon/lp_soplex.h (modified) (1 diff)
• test/lp_test.cc (modified) (5 diffs)

lemon/config.h.in

@@ -4 +4 @@
 /* Define to 1 if you have GLPK. */
 #undef HAVE_GLPK
+
+/* Define to 1 if you have SOPLEX. */
+#undef HAVE_SOPLEX

lemon/lp_base.h

@@ -372 +372 @@
       }
 
-      //std::ostream &
-      void prettyPrint(std::ostream &os) {
-        //std::fmtflags os.flags();
-        //os.setf(std::ios::showpos);
-        Base::iterator j=Base::begin();
-        if (j!=Base::end())
-          os<<j->second<<"*x["<<id(j->first)<<"]";
-        ++j;
-        for (; j!=Base::end(); ++j){
-          if (j->second>=0)
-            os<<"+";
-          os<<j->second<<"*x["<<id(j->first)<<"]";
-        }
-        //Nem valami korrekt, de nem talaltam meg, hogy kell
-        //os.unsetf(std::ios::showpos);
-
-        //return os;
-      }
-
     };
     
@@ -482 +463 @@
       }
 
-      void prettyPrint(std::ostream &os) {
-        if (_lb==-LpSolverBase::INF||isNaN(_lb))
-          os<<"-infty<=";
-        else
-          os<<_lb<<"<=";
-        _expr.prettyPrint(os);
-        if (_ub==LpSolverBase::INF)
-          os<<"<=infty";
-        else
-          os<<"<="<<_ub;
-        //return os;
-      }
-
     };
     
@@ -736 +704 @@
 
     //Abstract virtual functions
-    virtual LpSolverBase &_newLp() = 0;
-    virtual LpSolverBase &_copyLp(){
-      ///\todo This should be implemented here, too, when we have
-      ///problem retrieving routines. It can be overriden.
-
-      //Starting:
-      LpSolverBase & newlp(_newLp());
+    virtual LpSolverBase* _newLp() = 0;
+    virtual LpSolverBase* _copyLp(){
+      LpSolverBase* newlp = _newLp();
+
+      std::map<Col, Col> ref;
+      for (LpSolverBase::ColIt it(*this); it != INVALID; ++it) {
+        Col ccol = newlp->addCol();
+        ref[it] = ccol;
+        newlp->colName(ccol, colName(it));
+        newlp->colLowerBound(ccol, colLowerBound(it));
+        newlp->colUpperBound(ccol, colUpperBound(it));
+      }
+
+      for (LpSolverBase::RowIt it(*this); it != INVALID; ++it) {
+        Expr e = row(it), ce;
+        for (Expr::iterator jt = e.begin(); jt != e.end(); ++jt) {
+          ce[ref[jt->first]] = jt->second;
+        }
+        ce += e.constComp();
+        Row r = newlp->addRow(ce);
+
+        double lower, upper;
+        getRowBounds(it, lower, upper);
+        newlp->rowBounds(r, lower, upper);
+      }
+
       return newlp;
-      //return *(LpSolverBase*)0;
     };
 
@@ -805 +791 @@
 
     ///Creates a new LP problem
-    LpSolverBase &newLp() {return _newLp();}
+    LpSolverBase* newLp() {return _newLp();}
     ///Makes a copy of the LP problem
-    LpSolverBase &copyLp() {return _copyLp();}
+    LpSolverBase* copyLp() {return _copyLp();}
     
     ///\name Build up and modify the LP

lemon/lp_cplex.cc

@@ -18 +18 @@
 
 #include <iostream>
+#include <vector>
 #include<lemon/lp_cplex.h>
 
@@ -24 +25 @@
 namespace lemon {
   
-  LpCplex::LpCplex() : LpSolverBase() {
+  LpCplex::LpCplex() {
     //    env = CPXopenCPLEXdevelop(&status);     
     env = CPXopenCPLEX(&status);     
     lp = CPXcreateprob(env, &status, "LP problem");
   }
+
+  LpCplex::LpCplex(const LpCplex& cplex) : LpSolverBase() {
+    env = CPXopenCPLEX(&status);     
+    lp = CPXcloneprob(env, cplex.lp, &status);
+    rows = cplex.rows;
+    cols = cplex.cols;
+  }
   
   LpCplex::~LpCplex() {
-    CPXfreeprob(env,&lp); 
-    CPXcloseCPLEX(&env); 
-  }
-  
-  LpSolverBase &LpCplex::_newLp() 
+    CPXfreeprob(env,&lp);
+    CPXcloseCPLEX(&env);
+  }
+  
+  LpSolverBase* LpCplex::_newLp() 
   {
     //The first approach opens a new environment
-    LpCplex* newlp=new LpCplex();
-    return *newlp;
-  }
-
-  LpSolverBase &LpCplex::_copyLp() {
-    ///\bug FixID data is not copied!
-    //The first approach opens a new environment
-    LpCplex* newlp=new LpCplex();
-    //The routine CPXcloneprob can be used to create a new CPLEX problem 
-    //object and copy all the problem data from an existing problem 
-    //object to it. Solution and starting information is not copied.
-    newlp->lp = CPXcloneprob(env, lp, &status);
-    return *newlp;
+    return new LpCplex();
+  }
+
+  LpSolverBase* LpCplex::_copyLp() {
+    return new LpCplex(*this);
   }
 
@@ -57 +57 @@
     int i = CPXgetnumcols(env, lp);
     Value lb[1],ub[1];
-    lb[0]=-INF;//-CPX_INFBOUND;
-    ub[0]=INF;//CPX_INFBOUND;
+    lb[0]=-INF;
+    ub[0]=INF;
     status = CPXnewcols(env, lp, 1, NULL, lb, ub, NULL, NULL);
     return i;
@@ -90 +90 @@
     int storespace;
     CPXgetcolname(env, lp, 0, 0, 0, &storespace, col, col);
-
+    if (storespace == 0) {
+      name.clear();
+      return;
+    }
+    
     storespace *= -1;
     std::vector<char> buf(storespace);
@@ -137 +141 @@
 
   void LpCplex::_getRowCoeffs(int i, RowIterator b) const {
+    int tmp1, tmp2, tmp3, length;
+    CPXgetrows(env, lp, &tmp1, &tmp2, 0, 0, 0, &length, i, i);
+    
+    length = -length;
+    std::vector<int> indices(length);
+    std::vector<double> values(length);
+
+    CPXgetrows(env, lp, &tmp1, &tmp2, &indices[0], &values[0], 
+               length, &tmp3, i, i);
+    
+    for (int i = 0; i < length; ++i) {
+      *b = std::make_pair(indices[i], values[i]);
+      ++b;
+    }
+    
     /// \todo implement
   }
@@ -157 +176 @@
 
   void LpCplex::_getColCoeffs(int i, ColIterator b) const {
-    /// \todo implement
+
+    int tmp1, tmp2, tmp3, length;
+    CPXgetcols(env, lp, &tmp1, &tmp2, 0, 0, 0, &length, i, i);
+    
+    length = -length;
+    std::vector<int> indices(length);
+    std::vector<double> values(length);
+
+    CPXgetcols(env, lp, &tmp1, &tmp2, &indices[0], &values[0], 
+               length, &tmp3, i, i);
+    
+    for (int i = 0; i < length; ++i) {
+      *b = std::make_pair(indices[i], values[i]);
+      ++b;
+    }
+    
   }
   
@@ -188 +222 @@
     LpCplex::Value x;
     CPXgetlb (env, lp, &x, i, i);
+    if (x <= -CPX_INFBOUND) x = -INF;
     return x;
   }
@@ -206 +241 @@
     LpCplex::Value x;
     CPXgetub (env, lp, &x, i, i);
+    if (x >= CPX_INFBOUND) x = INF;
     return x;
   }
@@ -470 +506 @@
 // 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 env,int& stat){
-#if CPX_VERSION < 900
     int lpmethod;
     CPXgetintparam (env,CPX_PARAM_LPMETHOD,&lpmethod);
@@ -483 +519 @@
       }
     }
+  }
+#else
+  void statusSwitch(CPXENVptr,int&){}
 #endif
-  }
 
   LpCplex::SolutionStatus LpCplex::_getPrimalStatus() const

lemon/lp_cplex.h

@@ -50 +50 @@
     LpCplex();
     /// \e
+    LpCplex(const LpCplex&);
+    /// \e
     ~LpCplex();
 
   protected:
-    virtual LpSolverBase &_newLp();
-    virtual LpSolverBase &_copyLp();
+    virtual LpSolverBase* _newLp();
+    virtual LpSolverBase* _copyLp();
 
 
@@ -101 +103 @@
     virtual bool _isMax() const;
 
+  public:
+
+    CPXENVptr cplexEnv() { return env; } 
+    CPXLPptr cplexLp() { return lp; }
+
   };
 } //END OF NAMESPACE LEMON

lemon/lp_glpk.cc

@@ -90 +90 @@
                                 LEMON_glp(get_col_ub)(glp.lp,i));
       }
+    rows = glp.rows;
+    cols = glp.cols;
   }
   
@@ -106 +108 @@
 
 
-  LpSolverBase &LpGlpk::_newLp()
-  {
-    LpGlpk* newlp=new LpGlpk;
-    return *newlp;
+  LpSolverBase* LpGlpk::_newLp()
+  {
+    LpGlpk* newlp = new LpGlpk;
+    return newlp;
   }
   
   ///\e
 
-  LpSolverBase &LpGlpk::_copyLp()
-  {
-    LpGlpk* newlp=new LpGlpk(*this);
-    return *newlp;
+  LpSolverBase* LpGlpk::_copyLp()
+  {
+    LpGlpk *newlp = new LpGlpk(*this);
+    return newlp;
   }
 

lemon/lp_glpk.h

@@ -50 +50 @@
     
   protected:
-    virtual LpSolverBase &_newLp();
-    virtual LpSolverBase &_copyLp();
+    virtual LpSolverBase* _newLp();
+    virtual LpSolverBase* _copyLp();
 
     virtual int _addCol();
@@ -121 +121 @@
     ///Pointer to the underlying GLPK data structure.
     LPX *lpx() {return lp;}
+
+    ///Returns the constraint identifier understood by GLPK.
+    int lpxRow(Row r) { return _lpId(r); }
+
+    ///Returns the variable identifier understood by GLPK.
+    int lpxCol(Col c) { return _lpId(c); }
   };
 } //END OF NAMESPACE LEMON

lemon/lp_skeleton.cc

@@ -23 +23 @@
 namespace lemon {
   
-  LpSolverBase &LpSkeleton::_newLp()
+  LpSolverBase* LpSkeleton::_newLp()
   {
     LpSolverBase *tmp=0;
-    return *tmp;
+    return tmp;
   }
   
-  LpSolverBase &LpSkeleton::_copyLp()
+  LpSolverBase* LpSkeleton::_copyLp()
   {
     LpSolverBase *tmp=0;
-    return *tmp;
+    return tmp;
   }
 

lemon/lp_skeleton.h

@@ -33 +33 @@
 
     ///\e
-    virtual LpSolverBase &_newLp();
+    virtual LpSolverBase* _newLp();
     ///\e
-    virtual LpSolverBase &_copyLp();
+    virtual LpSolverBase* _copyLp();
     /// \e
     virtual int _addCol();

lemon/lp_soplex.cc

@@ -37 +37 @@
     delete soplex;
   }
-  
-  LpSolverBase &LpSoplex::_newLp() {
+
+  LpSoplex::LpSoplex(const LpSoplex& lp) : LpSolverBase() {
+    rows = lp.rows;
+    rows.setIdHandler(relocateIdHandler);
+
+    cols = lp.cols;
+    cols.setIdHandler(relocateIdHandler);
+
+    soplex = new soplex::SoPlex;
+    (*static_cast<soplex::SPxLP*>(soplex)) = *(lp.soplex);
+
+    colNames = lp.colNames;
+    invColNames = lp.invColNames;
+
+    primal_value = lp.primal_value;
+    dual_value = lp.dual_value;
+
+  }
+  
+  LpSolverBase* LpSoplex::_newLp() {
     LpSoplex* newlp = new LpSoplex();
-    return *newlp;
-  }
-
-  LpSolverBase &LpSoplex::_copyLp() {
-    LpSoplex* newlp = new LpSoplex();
-    (*static_cast<soplex::SPxLP*>(newlp->soplex)) = *soplex;
-    return *newlp;
+    return newlp;
+  }
+
+  LpSolverBase* LpSoplex::_copyLp() {
+    LpSoplex* newlp = new LpSoplex(*this);
+    return newlp;
   }
 

lemon/lp_soplex.h

@@ -67 +67 @@
     LpSoplex();
     /// \e
+    LpSoplex(const LpSoplex&);
+    /// \e
     ~LpSoplex();
 
   protected:
 
-    virtual LpSolverBase &_newLp();
-    virtual LpSolverBase &_copyLp();
+    virtual LpSolverBase* _newLp();
+    virtual LpSolverBase* _copyLp();
 
     virtual int _addCol();

test/lp_test.cc

@@ -21 +21 @@
 #include "test_tools.h"
 #include <lemon/tolerance.h>
+#include <lemon/lp_utils.h>
 
 #ifdef HAVE_CONFIG_H
@@ -217 +218 @@
   {
     LP::DualExpr e,f,g;
-    LP::Row p1,p2,p3,p4,p5;
+    LP::Row p1 = INVALID, p2 = INVALID, p3 = INVALID, 
+      p4 = INVALID, p5 = INVALID;
     
     e[p1]=2;
@@ -296 +298 @@
   lp.max();
 
-
   //Testing the problem retrieving routines
   check(lp.objCoeff(x1)==1,"First term should be 1 in the obj function!");
@@ -308 +309 @@
   check(  lb==-LpSolverBase::INF,"The lower bound for the first row should be -infty.");
   check(  ub==1,"The upper bound for the first row should be 1.");
-
+  LpSolverBase::Expr e = lp.row(upright);
+  check(  e.size() == 2, "The row retrieval gives back wrong expression.");
+  check(  e[x1] == 1, "The first coefficient should 1.");
+  check(  e[x2] == 1, "The second coefficient should 1.");
+
+  LpSolverBase::DualExpr de = lp.col(x1);
+  check(  de.size() == 4, "The col retrieval gives back wrong expression.");
+  check(  de[upright] == 1, "The first coefficient should 1.");
+
+  LpSolverBase* clp = lp.copyLp();
+
+  //Testing the problem retrieving routines
+  check(clp->objCoeff(x1)==1,"First term should be 1 in the obj function!");
+  check(clp->isMax(),"This is a maximization!");
+  check(clp->coeff(upright,x1)==1,"The coefficient in question is 1!");
+  //  std::cout<<lp.colLowerBound(x1)<<std::endl;
+  check(  clp->colLowerBound(x1)==0,"The lower bound for variable x1 should be 0.");
+  std::cerr << clp->colUpperBound(x1) << std::endl;
+  check(  clp->colUpperBound(x1)==LpSolverBase::INF,"The upper bound for variable x1 should be infty.");
+
+  clp->getRowBounds(upright,lb,ub);
+  check(  lb==-LpSolverBase::INF,"The lower bound for the first row should be -infty.");
+  check(  ub==1,"The upper bound for the first row should be 1.");
+  e = clp->row(upright);
+  check(  e.size() == 2, "The row retrieval gives back wrong expression.");
+  check(  e[x1] == 1, "The first coefficient should 1.");
+  check(  e[x2] == 1, "The second coefficient should 1.");
+
+  de = clp->col(x1);
+  check(  de.size() == 4, "The col retrieval gives back wrong expression.");
+  check(  de[upright] == 1, "The first coefficient should 1.");
+  
+  delete clp;
 
   //Maximization of x1+x2
@@ -338 +371 @@
   lp.min();
   check(lp.primalStatus()==LpSolverBase::UNDEFINED,"Primalstatus should be UNDEFINED");
+
 
 //   lp.solve();