test/lp_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 20 Feb 2010 16:51:43 +0100
changeset 846 9d380bf27194
parent 627 20dac2104519
child 957 2eebc8f7dca5
permissions -rw-r--r--
Use 'long long' flow cost in dimacs-solver.cc (#347)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #include <sstream>
    20 #include <lemon/lp_skeleton.h>
    21 #include "test_tools.h"
    22 #include <lemon/tolerance.h>
    23 
    24 #include <lemon/config.h>
    25 
    26 #ifdef LEMON_HAVE_GLPK
    27 #include <lemon/glpk.h>
    28 #endif
    29 
    30 #ifdef LEMON_HAVE_CPLEX
    31 #include <lemon/cplex.h>
    32 #endif
    33 
    34 #ifdef LEMON_HAVE_SOPLEX
    35 #include <lemon/soplex.h>
    36 #endif
    37 
    38 #ifdef LEMON_HAVE_CLP
    39 #include <lemon/clp.h>
    40 #endif
    41 
    42 using namespace lemon;
    43 
    44 void lpTest(LpSolver& lp)
    45 {
    46 
    47   typedef LpSolver LP;
    48 
    49   std::vector<LP::Col> x(10);
    50   //  for(int i=0;i<10;i++) x.push_back(lp.addCol());
    51   lp.addColSet(x);
    52   lp.colLowerBound(x,1);
    53   lp.colUpperBound(x,1);
    54   lp.colBounds(x,1,2);
    55 
    56   std::vector<LP::Col> y(10);
    57   lp.addColSet(y);
    58 
    59   lp.colLowerBound(y,1);
    60   lp.colUpperBound(y,1);
    61   lp.colBounds(y,1,2);
    62 
    63   std::map<int,LP::Col> z;
    64 
    65   z.insert(std::make_pair(12,INVALID));
    66   z.insert(std::make_pair(2,INVALID));
    67   z.insert(std::make_pair(7,INVALID));
    68   z.insert(std::make_pair(5,INVALID));
    69 
    70   lp.addColSet(z);
    71 
    72   lp.colLowerBound(z,1);
    73   lp.colUpperBound(z,1);
    74   lp.colBounds(z,1,2);
    75 
    76   {
    77     LP::Expr e,f,g;
    78     LP::Col p1,p2,p3,p4,p5;
    79     LP::Constr c;
    80 
    81     p1=lp.addCol();
    82     p2=lp.addCol();
    83     p3=lp.addCol();
    84     p4=lp.addCol();
    85     p5=lp.addCol();
    86 
    87     e[p1]=2;
    88     *e=12;
    89     e[p1]+=2;
    90     *e+=12;
    91     e[p1]-=2;
    92     *e-=12;
    93 
    94     e=2;
    95     e=2.2;
    96     e=p1;
    97     e=f;
    98 
    99     e+=2;
   100     e+=2.2;
   101     e+=p1;
   102     e+=f;
   103 
   104     e-=2;
   105     e-=2.2;
   106     e-=p1;
   107     e-=f;
   108 
   109     e*=2;
   110     e*=2.2;
   111     e/=2;
   112     e/=2.2;
   113 
   114     e=((p1+p2)+(p1-p2)+(p1+12)+(12+p1)+(p1-12)+(12-p1)+
   115        (f+12)+(12+f)+(p1+f)+(f+p1)+(f+g)+
   116        (f-12)+(12-f)+(p1-f)+(f-p1)+(f-g)+
   117        2.2*f+f*2.2+f/2.2+
   118        2*f+f*2+f/2+
   119        2.2*p1+p1*2.2+p1/2.2+
   120        2*p1+p1*2+p1/2
   121        );
   122 
   123 
   124     c = (e  <= f  );
   125     c = (e  <= 2.2);
   126     c = (e  <= 2  );
   127     c = (e  <= p1 );
   128     c = (2.2<= f  );
   129     c = (2  <= f  );
   130     c = (p1 <= f  );
   131     c = (p1 <= p2 );
   132     c = (p1 <= 2.2);
   133     c = (p1 <= 2  );
   134     c = (2.2<= p2 );
   135     c = (2  <= p2 );
   136 
   137     c = (e  >= f  );
   138     c = (e  >= 2.2);
   139     c = (e  >= 2  );
   140     c = (e  >= p1 );
   141     c = (2.2>= f  );
   142     c = (2  >= f  );
   143     c = (p1 >= f  );
   144     c = (p1 >= p2 );
   145     c = (p1 >= 2.2);
   146     c = (p1 >= 2  );
   147     c = (2.2>= p2 );
   148     c = (2  >= p2 );
   149 
   150     c = (e  == f  );
   151     c = (e  == 2.2);
   152     c = (e  == 2  );
   153     c = (e  == p1 );
   154     c = (2.2== f  );
   155     c = (2  == f  );
   156     c = (p1 == f  );
   157     //c = (p1 == p2 );
   158     c = (p1 == 2.2);
   159     c = (p1 == 2  );
   160     c = (2.2== p2 );
   161     c = (2  == p2 );
   162 
   163     c = ((2 <= e) <= 3);
   164     c = ((2 <= p1) <= 3);
   165 
   166     c = ((2 >= e) >= 3);
   167     c = ((2 >= p1) >= 3);
   168 
   169     e[x[3]]=2;
   170     e[x[3]]=4;
   171     e[x[3]]=1;
   172     *e=12;
   173 
   174     lp.addRow(-LP::INF,e,23);
   175     lp.addRow(-LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);
   176     lp.addRow(-LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23);
   177 
   178     lp.addRow(x[1]+x[3]<=x[5]-3);
   179     lp.addRow((-7<=x[1]+x[3]-12)<=3);
   180     lp.addRow(x[1]<=x[5]);
   181 
   182     std::ostringstream buf;
   183 
   184 
   185     e=((p1+p2)+(p1-0.99*p2));
   186     //e.prettyPrint(std::cout);
   187     //(e<=2).prettyPrint(std::cout);
   188     double tolerance=0.001;
   189     e.simplify(tolerance);
   190     buf << "Coeff. of p2 should be 0.01";
   191     check(e[p2]>0, buf.str());
   192 
   193     tolerance=0.02;
   194     e.simplify(tolerance);
   195     buf << "Coeff. of p2 should be 0";
   196     check(const_cast<const LpSolver::Expr&>(e)[p2]==0, buf.str());
   197 
   198     //Test for clone/new
   199     LP* lpnew = lp.newSolver();
   200     LP* lpclone = lp.cloneSolver();
   201     delete lpnew;
   202     delete lpclone;
   203 
   204   }
   205 
   206   {
   207     LP::DualExpr e,f,g;
   208     LP::Row p1 = INVALID, p2 = INVALID, p3 = INVALID,
   209       p4 = INVALID, p5 = INVALID;
   210 
   211     e[p1]=2;
   212     e[p1]+=2;
   213     e[p1]-=2;
   214 
   215     e=p1;
   216     e=f;
   217 
   218     e+=p1;
   219     e+=f;
   220 
   221     e-=p1;
   222     e-=f;
   223 
   224     e*=2;
   225     e*=2.2;
   226     e/=2;
   227     e/=2.2;
   228 
   229     e=((p1+p2)+(p1-p2)+
   230        (p1+f)+(f+p1)+(f+g)+
   231        (p1-f)+(f-p1)+(f-g)+
   232        2.2*f+f*2.2+f/2.2+
   233        2*f+f*2+f/2+
   234        2.2*p1+p1*2.2+p1/2.2+
   235        2*p1+p1*2+p1/2
   236        );
   237   }
   238 
   239 }
   240 
   241 void solveAndCheck(LpSolver& lp, LpSolver::ProblemType stat,
   242                    double exp_opt) {
   243   using std::string;
   244   lp.solve();
   245 
   246   std::ostringstream buf;
   247   buf << "PrimalType should be: " << int(stat) << int(lp.primalType());
   248 
   249   check(lp.primalType()==stat, buf.str());
   250 
   251   if (stat ==  LpSolver::OPTIMAL) {
   252     std::ostringstream sbuf;
   253     sbuf << "Wrong optimal value (" << lp.primal() <<") with "
   254          << lp.solverName() <<"\n     the right optimum is " << exp_opt;
   255     check(std::abs(lp.primal()-exp_opt) < 1e-3, sbuf.str());
   256   }
   257 }
   258 
   259 void aTest(LpSolver & lp)
   260 {
   261   typedef LpSolver LP;
   262 
   263  //The following example is very simple
   264 
   265   typedef LpSolver::Row Row;
   266   typedef LpSolver::Col Col;
   267 
   268 
   269   Col x1 = lp.addCol();
   270   Col x2 = lp.addCol();
   271 
   272 
   273   //Constraints
   274   Row upright=lp.addRow(x1+2*x2 <=1);
   275   lp.addRow(x1+x2 >=-1);
   276   lp.addRow(x1-x2 <=1);
   277   lp.addRow(x1-x2 >=-1);
   278   //Nonnegativity of the variables
   279   lp.colLowerBound(x1, 0);
   280   lp.colLowerBound(x2, 0);
   281   //Objective function
   282   lp.obj(x1+x2);
   283 
   284   lp.sense(lp.MAX);
   285 
   286   //Testing the problem retrieving routines
   287   check(lp.objCoeff(x1)==1,"First term should be 1 in the obj function!");
   288   check(lp.sense() == lp.MAX,"This is a maximization!");
   289   check(lp.coeff(upright,x1)==1,"The coefficient in question is 1!");
   290   check(lp.colLowerBound(x1)==0,
   291         "The lower bound for variable x1 should be 0.");
   292   check(lp.colUpperBound(x1)==LpSolver::INF,
   293         "The upper bound for variable x1 should be infty.");
   294   check(lp.rowLowerBound(upright) == -LpSolver::INF,
   295         "The lower bound for the first row should be -infty.");
   296   check(lp.rowUpperBound(upright)==1,
   297         "The upper bound for the first row should be 1.");
   298   LpSolver::Expr e = lp.row(upright);
   299   check(e[x1] == 1, "The first coefficient should 1.");
   300   check(e[x2] == 2, "The second coefficient should 1.");
   301 
   302   lp.row(upright, x1+x2 <=1);
   303   e = lp.row(upright);
   304   check(e[x1] == 1, "The first coefficient should 1.");
   305   check(e[x2] == 1, "The second coefficient should 1.");
   306 
   307   LpSolver::DualExpr de = lp.col(x1);
   308   check(  de[upright] == 1, "The first coefficient should 1.");
   309 
   310   LpSolver* clp = lp.cloneSolver();
   311 
   312   //Testing the problem retrieving routines
   313   check(clp->objCoeff(x1)==1,"First term should be 1 in the obj function!");
   314   check(clp->sense() == clp->MAX,"This is a maximization!");
   315   check(clp->coeff(upright,x1)==1,"The coefficient in question is 1!");
   316   //  std::cout<<lp.colLowerBound(x1)<<std::endl;
   317   check(clp->colLowerBound(x1)==0,
   318         "The lower bound for variable x1 should be 0.");
   319   check(clp->colUpperBound(x1)==LpSolver::INF,
   320         "The upper bound for variable x1 should be infty.");
   321 
   322   check(lp.rowLowerBound(upright)==-LpSolver::INF,
   323         "The lower bound for the first row should be -infty.");
   324   check(lp.rowUpperBound(upright)==1,
   325         "The upper bound for the first row should be 1.");
   326   e = clp->row(upright);
   327   check(e[x1] == 1, "The first coefficient should 1.");
   328   check(e[x2] == 1, "The second coefficient should 1.");
   329 
   330   de = clp->col(x1);
   331   check(de[upright] == 1, "The first coefficient should 1.");
   332 
   333   delete clp;
   334 
   335   //Maximization of x1+x2
   336   //over the triangle with vertices (0,0) (0,1) (1,0)
   337   double expected_opt=1;
   338   solveAndCheck(lp, LpSolver::OPTIMAL, expected_opt);
   339 
   340   //Minimization
   341   lp.sense(lp.MIN);
   342   expected_opt=0;
   343   solveAndCheck(lp, LpSolver::OPTIMAL, expected_opt);
   344 
   345   //Vertex (-1,0) instead of (0,0)
   346   lp.colLowerBound(x1, -LpSolver::INF);
   347   expected_opt=-1;
   348   solveAndCheck(lp, LpSolver::OPTIMAL, expected_opt);
   349 
   350   //Erase one constraint and return to maximization
   351   lp.erase(upright);
   352   lp.sense(lp.MAX);
   353   expected_opt=LpSolver::INF;
   354   solveAndCheck(lp, LpSolver::UNBOUNDED, expected_opt);
   355 
   356   //Infeasibilty
   357   lp.addRow(x1+x2 <=-2);
   358   solveAndCheck(lp, LpSolver::INFEASIBLE, expected_opt);
   359 
   360 }
   361 
   362 template<class LP>
   363 void cloneTest()
   364 {
   365   //Test for clone/new
   366 
   367   LP* lp = new LP();
   368   LP* lpnew = lp->newSolver();
   369   LP* lpclone = lp->cloneSolver();
   370   delete lp;
   371   delete lpnew;
   372   delete lpclone;
   373 }
   374 
   375 int main()
   376 {
   377   LpSkeleton lp_skel;
   378   lpTest(lp_skel);
   379 
   380 #ifdef LEMON_HAVE_GLPK
   381   {
   382     GlpkLp lp_glpk1,lp_glpk2;
   383     lpTest(lp_glpk1);
   384     aTest(lp_glpk2);
   385     cloneTest<GlpkLp>();
   386   }
   387 #endif
   388 
   389 #ifdef LEMON_HAVE_CPLEX
   390   try {
   391     CplexLp lp_cplex1,lp_cplex2;
   392     lpTest(lp_cplex1);
   393     aTest(lp_cplex2);
   394     cloneTest<CplexLp>();
   395   } catch (CplexEnv::LicenseError& error) {
   396     check(false, error.what());
   397   }
   398 #endif
   399 
   400 #ifdef LEMON_HAVE_SOPLEX
   401   {
   402     SoplexLp lp_soplex1,lp_soplex2;
   403     lpTest(lp_soplex1);
   404     aTest(lp_soplex2);
   405     cloneTest<SoplexLp>();
   406   }
   407 #endif
   408 
   409 #ifdef LEMON_HAVE_CLP
   410   {
   411     ClpLp lp_clp1,lp_clp2;
   412     lpTest(lp_clp1);
   413     aTest(lp_clp2);
   414     cloneTest<ClpLp>();
   415   }
   416 #endif
   417 
   418   return 0;
   419 }