test/lp_test.cc
author deba
Tue, 24 Jan 2006 16:07:38 +0000
changeset 1901 723b2b81d900
parent 1797 91b8b9cea2f7
child 1956 a055123339d5
permissions -rw-r--r--
Lemon Graph Format uses label instead of id named map.
     1 #include <sstream>
     2 #include <lemon/lp_skeleton.h>
     3 #include "test_tools.h"
     4 
     5 
     6 #ifdef HAVE_CONFIG_H
     7 #include <config.h>
     8 #endif
     9 
    10 #ifdef HAVE_GLPK
    11 #include <lemon/lp_glpk.h>
    12 #endif
    13 
    14 #ifdef HAVE_CPLEX
    15 #include <lemon/lp_cplex.h>
    16 #endif
    17 
    18 using namespace lemon;
    19 
    20 void lpTest(LpSolverBase & lp)
    21 {
    22 
    23 
    24 
    25   typedef LpSolverBase LP;
    26 
    27   std::vector<LP::Col> x(10);
    28   //  for(int i=0;i<10;i++) x.push_back(lp.addCol());
    29   lp.addColSet(x);
    30   lp.colLowerBound(x,1);
    31   lp.colUpperBound(x,1);
    32   lp.colBounds(x,1,2);
    33 #ifndef GYORSITAS
    34 
    35   std::vector<LP::Col> y(10);
    36   lp.addColSet(y);
    37 
    38   lp.colLowerBound(y,1);
    39   lp.colUpperBound(y,1);
    40   lp.colBounds(y,1,2);
    41 
    42   std::map<int,LP::Col> z;
    43   
    44   z.insert(std::make_pair(12,INVALID));
    45   z.insert(std::make_pair(2,INVALID));
    46   z.insert(std::make_pair(7,INVALID));
    47   z.insert(std::make_pair(5,INVALID));
    48 
    49   lp.addColSet(z);
    50 
    51   lp.colLowerBound(z,1);
    52   lp.colUpperBound(z,1);
    53   lp.colBounds(z,1,2);
    54 
    55   {
    56     LP::Expr e,f,g;
    57     LP::Col p1,p2,p3,p4,p5;
    58     LP::Constr c;
    59     
    60     p1=lp.addCol();
    61     p2=lp.addCol();
    62     p3=lp.addCol();
    63     p4=lp.addCol();
    64     p5=lp.addCol();
    65     
    66     e[p1]=2;
    67     e.constComp()=12;
    68     e[p1]+=2;
    69     e.constComp()+=12;
    70     e[p1]-=2;
    71     e.constComp()-=12;
    72     
    73     e=2;
    74     e=2.2;
    75     e=p1;
    76     e=f;
    77     
    78     e+=2;
    79     e+=2.2;
    80     e+=p1;
    81     e+=f;
    82     
    83     e-=2;
    84     e-=2.2;
    85     e-=p1;
    86     e-=f;
    87     
    88     e*=2;
    89     e*=2.2;
    90     e/=2;
    91     e/=2.2;
    92     
    93     e=((p1+p2)+(p1-p2)+(p1+12)+(12+p1)+(p1-12)+(12-p1)+
    94        (f+12)+(12+f)+(p1+f)+(f+p1)+(f+g)+
    95        (f-12)+(12-f)+(p1-f)+(f-p1)+(f-g)+
    96        2.2*f+f*2.2+f/2.2+
    97        2*f+f*2+f/2+
    98        2.2*p1+p1*2.2+p1/2.2+
    99        2*p1+p1*2+p1/2
   100        );
   101 
   102 
   103     c = (e  <= f  );
   104     c = (e  <= 2.2);
   105     c = (e  <= 2  );
   106     c = (e  <= p1 );
   107     c = (2.2<= f  );
   108     c = (2  <= f  );
   109     c = (p1 <= f  );
   110     c = (p1 <= p2 );
   111     c = (p1 <= 2.2);
   112     c = (p1 <= 2  );
   113     c = (2.2<= p2 );
   114     c = (2  <= p2 );
   115     
   116     c = (e  >= f  );
   117     c = (e  >= 2.2);
   118     c = (e  >= 2  );
   119     c = (e  >= p1 );
   120     c = (2.2>= f  );
   121     c = (2  >= f  );
   122     c = (p1 >= f  );
   123     c = (p1 >= p2 );
   124     c = (p1 >= 2.2);
   125     c = (p1 >= 2  );
   126     c = (2.2>= p2 );
   127     c = (2  >= p2 );
   128     
   129     c = (e  == f  );
   130     c = (e  == 2.2);
   131     c = (e  == 2  );
   132     c = (e  == p1 );
   133     c = (2.2== f  );
   134     c = (2  == f  );
   135     c = (p1 == f  );
   136     //c = (p1 == p2 );
   137     c = (p1 == 2.2);
   138     c = (p1 == 2  );
   139     c = (2.2== p2 );
   140     c = (2  == p2 );
   141     
   142     c = (2 <= e <= 3);
   143     c = (2 <= p1<= 3);
   144     
   145     c = (2 >= e >= 3);
   146     c = (2 >= p1>= 3);
   147     
   148     e[x[3]]=2;
   149     e[x[3]]=4;
   150     e[x[3]]=1;
   151     e.constComp()=12;
   152     
   153     lp.addRow(LP::INF,e,23);
   154     lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);
   155     lp.addRow(LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23);
   156     
   157     lp.addRow(x[1]+x[3]<=x[5]-3);
   158     lp.addRow(-7<=x[1]+x[3]-12<=3);
   159     lp.addRow(x[1]<=x[5]);
   160   }
   161   
   162   {
   163     LP::DualExpr e,f,g;
   164     LP::Row p1,p2,p3,p4,p5;
   165     
   166     e[p1]=2;
   167     e[p1]+=2;
   168     e[p1]-=2;
   169     
   170     e=p1;
   171     e=f;
   172     
   173     e+=p1;
   174     e+=f;
   175     
   176     e-=p1;
   177     e-=f;
   178     
   179     e*=2;
   180     e*=2.2;
   181     e/=2;
   182     e/=2.2;
   183     
   184     e=((p1+p2)+(p1-p2)+
   185        (p1+f)+(f+p1)+(f+g)+
   186        (p1-f)+(f-p1)+(f-g)+
   187        2.2*f+f*2.2+f/2.2+
   188        2*f+f*2+f/2+
   189        2.2*p1+p1*2.2+p1/2.2+
   190        2*p1+p1*2+p1/2
   191        );
   192   }
   193   
   194 #endif
   195 }
   196 
   197 void solveAndCheck(LpSolverBase& lp, LpSolverBase::SolutionStatus stat, 
   198 		   double exp_opt) {
   199   using std::string;
   200   lp.solve();
   201   //int decimal,sign;
   202   std::ostringstream buf;
   203   buf << "Primalstatus should be: " << int(stat);
   204 
   205   //  itoa(stat,buf1, 10);
   206   check(lp.primalStatus()==stat, buf.str());
   207 
   208   if (stat ==  LpSolverBase::OPTIMAL) {
   209     std::ostringstream buf;
   210     buf << "Wrong optimal value: the right optimum is " << exp_opt; 
   211     check(std::abs(lp.primalValue()-exp_opt) < 1e-3, buf.str());
   212     //+ecvt(exp_opt,2)
   213   }
   214 }
   215  
   216 void aTest(LpSolverBase & lp)
   217 {
   218   typedef LpSolverBase LP;
   219 
   220  //The following example is very simple
   221 
   222   typedef LpSolverBase::Row Row;
   223   typedef LpSolverBase::Col Col;
   224 
   225 
   226   Col x1 = lp.addCol();
   227   Col x2 = lp.addCol();
   228 
   229 
   230   //Constraints
   231   Row upright=lp.addRow(x1+x2 <=1);  
   232   lp.addRow(x1+x2 >=-1);  
   233   lp.addRow(x1-x2 <=1);  
   234   lp.addRow(x1-x2 >=-1);  
   235   //Nonnegativity of the variables
   236   lp.colLowerBound(x1, 0);
   237   lp.colLowerBound(x2, 0);
   238   //Objective function
   239   lp.setObj(x1+x2);
   240 
   241   lp.max();
   242 
   243   //Maximization of x1+x2
   244   //over the triangle with vertices (0,0) (0,1) (1,0)
   245   double expected_opt=1;
   246   solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt);
   247   
   248   //Minimization
   249   lp.min();
   250   expected_opt=0;
   251   solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt);
   252   
   253   //Vertex (-1,0) instead of (0,0)
   254   lp.colLowerBound(x1, -LpSolverBase::INF);
   255   expected_opt=-1;
   256   solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt);
   257 
   258   //Erase one constraint and return to maximization
   259   lp.eraseRow(upright);
   260   lp.max();
   261   expected_opt=LpSolverBase::INF;
   262   solveAndCheck(lp, LpSolverBase::INFINITE, expected_opt);
   263 
   264   //Infeasibilty
   265   lp.addRow(x1+x2 <=-2);  
   266   solveAndCheck(lp, LpSolverBase::INFEASIBLE, expected_opt);
   267 
   268   //Change problem and forget to solve
   269   lp.min();
   270   check(lp.primalStatus()==LpSolverBase::UNDEFINED,"Primalstatus should be UNDEFINED");
   271 
   272 //   lp.solve();
   273 //   if (lp.primalStatus()==LpSolverBase::OPTIMAL){
   274 //     std::cout<< "Z = "<<lp.primalValue()
   275 // 	     << " (error = " << lp.primalValue()-expected_opt
   276 // 	     << "); x1 = "<<lp.primal(x1)
   277 // 	     << "; x2 = "<<lp.primal(x2)
   278 // 	     <<std::endl;
   279     
   280 //   }
   281 //   else{
   282 //     std::cout<<lp.primalStatus()<<std::endl;
   283 //     std::cout<<"Optimal solution not found!"<<std::endl;
   284 //   }
   285 
   286  
   287 
   288 }
   289 
   290 
   291 int main() 
   292 {
   293   LpSkeleton lp_skel;
   294   lpTest(lp_skel);
   295 
   296 #ifdef HAVE_GLPK
   297   LpGlpk lp_glpk1,lp_glpk2;
   298   lpTest(lp_glpk1);
   299   aTest(lp_glpk2);
   300 #endif
   301 
   302 #ifdef HAVE_CPLEX
   303   LpCplex lp_cplex1,lp_cplex2;
   304   lpTest(lp_cplex1);
   305   aTest(lp_cplex2);
   306 #endif
   307 
   308   return 0;
   309 }