Changeset 1542:0219ee65ffcc in lemon-0.x

Timestamp:

07/07/05 17:00:04 (20 years ago)

Author:

athos

Branch:

default

Phase:

public

Convert:

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

Message:

Some testing of the LP interface: bugs got fixed.

Files:

• lemon/lp_base.h (modified) (5 diffs)
• lemon/lp_cplex.cc (modified) (5 diffs)
• test/lp_test.cc (modified) (3 diffs)

lemon/lp_base.h

@@ -139 +139 @@
     };
 
-      ///\e The type of the investigated LP problem
-      enum ProblemTypes {
-          ///Primal-dual feasible
-          PRIMAL_DUAL_FEASIBLE = 0,
-          ///Primal feasible dual infeasible
-          PRIMAL_FEASIBLE_DUAL_INFEASIBLE = 1,
-          ///Primal infeasible dual feasible
-          PRIMAL_INFEASIBLE_DUAL_FEASIBLE = 2,
-          ///Primal-dual infeasible
-          PRIMAL_DUAL_INFEASIBLE = 3,
-          ///Could not determine so far
-          UNKNOWN = 4
-      };
+    ///\e The type of the investigated LP problem
+    enum ProblemTypes {
+      ///Primal-dual feasible
+      PRIMAL_DUAL_FEASIBLE = 0,
+      ///Primal feasible dual infeasible
+      PRIMAL_FEASIBLE_DUAL_INFEASIBLE = 1,
+      ///Primal infeasible dual feasible
+      PRIMAL_INFEASIBLE_DUAL_FEASIBLE = 2,
+      ///Primal-dual infeasible
+      PRIMAL_DUAL_INFEASIBLE = 3,
+      ///Could not determine so far
+      UNKNOWN = 4
+    };
 
     ///The floating point type used by the solver
@@ -553 +553 @@
     virtual int _addCol() = 0;
     virtual int _addRow() = 0;
+    virtual void _eraseCol(int col) = 0;
+    virtual void _eraseRow(int row) = 0;
     virtual void _setRowCoeffs(int i, 
                                int length,
@@ -681 +683 @@
     ///\param c is the column to be modified
     ///\param e is a dual linear expression (see \ref DualExpr)
-    ///\bug This is a temportary function. The interface will change to
+    ///\bug This is a temporary function. The interface will change to
     ///a better one.
     void setCol(Col c,const DualExpr &e) {
@@ -718 +720 @@
     Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
 
-    ///\brief Adds several new row
-    ///(i.e a variables) at once
+    ///\brief Add several new rows
+    ///(i.e a constraints) at once
     ///
     ///This magic function takes a container as its argument
@@ -844 +846 @@
       return r;
     }
+    ///Erase a coloumn (i.e a variable) from the LP
+
+    ///\param c is the coloumn to be deleted
+    ///\todo Please check this
+    void eraseCol(Col c) {
+      _eraseCol(cols.floatingId(c.id));
+      cols.erase(c.id);
+    }
+    ///Erase a  row (i.e a constraint) from the LP
+
+    ///\param r is the row to be deleted
+    ///\todo Please check this
+    void eraseRow(Row r) {
+      _eraseRow(rows.floatingId(r.id));
+      rows.erase(r.id);
+    }
 
     ///Set an element of the coefficient matrix of the LP

lemon/lp_cplex.cc

@@ -243 +243 @@
     //CPX_PARAM_LPMETHOD 
     status = CPXlpopt(env, lp);
+    //status = CPXprimopt(env, lp);
     if (status == 0){
       //We want to exclude some cases
@@ -328 +329 @@
 // ??case CPX_ABORT_CROSSOVER             
 // ??case CPX_INForUNBD                   
-// ??case CPX_PIVOT                       
+// ??case CPX_PIVOT              
+         
+//Some more interesting stuff:
+
+// CPX_PARAM_LPMETHOD  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 
+  //Hulye cplex
+  void statusSwitch(CPXENVptr env,int& stat){
+    int lpmethod;
+    CPXgetintparam (env,CPX_PARAM_LPMETHOD,&lpmethod);
+    if (lpmethod==2){
+      if (stat==CPX_UNBOUNDED){
+        stat=CPX_INFEASIBLE;
+      }
+      else{
+        if (stat==CPX_INFEASIBLE)
+          stat=CPX_UNBOUNDED;
+      }
+    }
+  }
 
   LpCplex::SolutionStatus LpCplex::_getPrimalStatus()
   {
+    
     int stat = CPXgetstat(env, lp);
+    statusSwitch(env,stat);
+    //CPXgetstat(env, lp);
     //printf("A primal status: %d, CPX_OPTIMAL=%d \n",stat,CPX_OPTIMAL);
     switch (stat) {
@@ -340 +370 @@
       return OPTIMAL;
     case CPX_UNBOUNDED://Unbounded
-      return INFINITE;
+      return INFEASIBLE;//In case of dual simplex
+      //return INFINITE;
     case CPX_INFEASIBLE://Infeasible 
  //    case CPX_IT_LIM_INFEAS:
@@ -349 +380 @@
 //     case CPX_ABORT_PRIM_INFEAS:           
 //     case CPX_ABORT_PRIM_DUAL_INFEAS:      
-      return INFEASIBLE;
+      return INFINITE;//In case of dual simplex
+      //return INFEASIBLE;
 //     case CPX_OBJ_LIM:                    
 //     case CPX_IT_LIM_FEAS:             
@@ -384 +416 @@
   {
     int stat = CPXgetstat(env, lp);
+    statusSwitch(env,stat);
     switch (stat) {
     case 0:

test/lp_test.cc

@@ -1 +1 @@
 #include<lemon/lp_skeleton.h>
 #include "test_tools.h"
+
 
 #ifdef HAVE_CONFIG_H
@@ -183 +184 @@
 }
 
+void solveAndCheck(LpSolverBase& lp, LpSolverBase::SolutionStatus stat, 
+                   double exp_opt){
+  lp.solve();
+  //int decimal,sign;
+  std::string buf1;
+  //  itoa(stat,buf1, 10);
+  check(lp.primalStatus()==stat,"Primalstatus should be "+buf1);
+    
+  if (stat ==  LpSolverBase::OPTIMAL){
+    check(std::abs(lp.primalValue()-exp_opt)<1e-3,
+          "Wrong optimal value: the right optimum is ");
+    //+ecvt(exp_opt,2)
+  }
+}
+ 
 void aTest(LpSolverBase & lp)
 {
   typedef LpSolverBase LP;
 
- //The following example is taken from the book by Gáspár and Temesi, page 39.
+ //The following example is very simple
 
   typedef LpSolverBase::Row Row;
@@ -198 +214 @@
 
   //Constraints
-  lp.addRow(3*x1+2*x2 >=6);  
-  lp.addRow(-1*x1+x2<=4);  
-  lp.addRow(5*x1+8*x2<=40);  
-  lp.addRow(x1-2*x2<=4);  
+  Row upright=lp.addRow(x1+x2 <=1);  
+  lp.addRow(x1+x2 >=-1);  
+  lp.addRow(x1-x2 <=1);  
+  lp.addRow(x1-x2 >=-1);  
   //Nonnegativity of the variables
   lp.colLowerBound(x1, 0);
   lp.colLowerBound(x2, 0);
   //Objective function
-  lp.setObj(2*x1+x2);
+  lp.setObj(x1+x2);
 
   lp.max();
-  lp.solve();
-
-  double opt=122.0/9.0;
-  
-  if (lp.primalStatus()==LpSolverBase::OPTIMAL){
-    std::cout<< "Z = "<<lp.primalValue()
-             << " (error = " << lp.primalValue()-opt
-             << "); x1 = "<<lp.primal(x1)
-             << "; x2 = "<<lp.primal(x2)
-             <<std::endl;
-    
-  }
-  else{
-    std::cout<<"Optimal solution not found!"<<std::endl;
-  }
-
-  check(lp.primalStatus()==LpSolverBase::OPTIMAL,"Primalstatus should be OPTIMAL");
-
-  check(std::abs(lp.primalValue()-opt)<1e-3,
-        "Wrong optimal value: the right optimum is 122/9 (13.555555...)");
-
+
+  //Maximization of x1+x2
+  //over the triangle with vertices (0,0) (0,1) (1,0)
+  double expected_opt=1;
+  solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt);
+  
+  //Minimization
+  lp.min();
+  expected_opt=0;
+  solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt);
+  
+  //Vertex (-1,0) instead of (0,0)
+  lp.colLowerBound(x1, -LpSolverBase::INF);
+  expected_opt=-1;
+  solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt);
+
+  //Erase one constraint and return to maximization
+  lp.eraseRow(upright);
+  lp.max();
+  expected_opt=LpSolverBase::INF;
+  solveAndCheck(lp, LpSolverBase::INFINITE, expected_opt);
+
+  //Infeasibilty
+  lp.addRow(x1+x2 <=-2);  
+  solveAndCheck(lp, LpSolverBase::INFEASIBLE, expected_opt);
+
+  //Change problem and forget to solve
+  lp.min();
+  check(lp.primalStatus()==LpSolverBase::UNDEFINED,"Primalstatus should be UNDEFINED");
+
+//   lp.solve();
+//   if (lp.primalStatus()==LpSolverBase::OPTIMAL){
+//     std::cout<< "Z = "<<lp.primalValue()
+//           << " (error = " << lp.primalValue()-expected_opt
+//           << "); x1 = "<<lp.primal(x1)
+//           << "; x2 = "<<lp.primal(x2)
+//           <<std::endl;
+    
+//   }
+//   else{
+//     std::cout<<lp.primalStatus()<<std::endl;
+//     std::cout<<"Optimal solution not found!"<<std::endl;
+//   }
+
+ 
 
 }