test/lp_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 20 Dec 2011 19:25:40 +0100
changeset 966 c8fce9beb46a
parent 631 d21b38647e53
child 988 8d281761dea4
permissions -rw-r--r--
Merge head merging
     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     { //Tests for #430
   170       LP::Col v=lp.addCol();
   171       LP::Constr c = v >= -3;
   172       c = c <= 4;
   173       LP::Constr c2;
   174       c2 = -3 <= v <= 4;
   175     }
   176 
   177     e[x[3]]=2;
   178     e[x[3]]=4;
   179     e[x[3]]=1;
   180     *e=12;
   181 
   182     lp.addRow(-LP::INF,e,23);
   183     lp.addRow(-LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);
   184     lp.addRow(-LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23);
   185 
   186     lp.addRow(x[1]+x[3]<=x[5]-3);
   187     lp.addRow((-7<=x[1]+x[3]-12)<=3);
   188     lp.addRow(x[1]<=x[5]);
   189 
   190     std::ostringstream buf;
   191 
   192 
   193     e=((p1+p2)+(p1-0.99*p2));
   194     //e.prettyPrint(std::cout);
   195     //(e<=2).prettyPrint(std::cout);
   196     double tolerance=0.001;
   197     e.simplify(tolerance);
   198     buf << "Coeff. of p2 should be 0.01";
   199     check(e[p2]>0, buf.str());
   200 
   201     tolerance=0.02;
   202     e.simplify(tolerance);
   203     buf << "Coeff. of p2 should be 0";
   204     check(const_cast<const LpSolver::Expr&>(e)[p2]==0, buf.str());
   205 
   206     //Test for clone/new
   207     LP* lpnew = lp.newSolver();
   208     LP* lpclone = lp.cloneSolver();
   209     delete lpnew;
   210     delete lpclone;
   211 
   212   }
   213 
   214   {
   215     LP::DualExpr e,f,g;
   216     LP::Row p1 = INVALID, p2 = INVALID, p3 = INVALID,
   217       p4 = INVALID, p5 = INVALID;
   218 
   219     e[p1]=2;
   220     e[p1]+=2;
   221     e[p1]-=2;
   222 
   223     e=p1;
   224     e=f;
   225 
   226     e+=p1;
   227     e+=f;
   228 
   229     e-=p1;
   230     e-=f;
   231 
   232     e*=2;
   233     e*=2.2;
   234     e/=2;
   235     e/=2.2;
   236 
   237     e=((p1+p2)+(p1-p2)+
   238        (p1+f)+(f+p1)+(f+g)+
   239        (p1-f)+(f-p1)+(f-g)+
   240        2.2*f+f*2.2+f/2.2+
   241        2*f+f*2+f/2+
   242        2.2*p1+p1*2.2+p1/2.2+
   243        2*p1+p1*2+p1/2
   244        );
   245   }
   246 
   247 }
   248 
   249 void solveAndCheck(LpSolver& lp, LpSolver::ProblemType stat,
   250                    double exp_opt) {
   251   using std::string;
   252   lp.solve();
   253 
   254   std::ostringstream buf;
   255   buf << "PrimalType should be: " << int(stat) << int(lp.primalType());
   256 
   257   check(lp.primalType()==stat, buf.str());
   258 
   259   if (stat ==  LpSolver::OPTIMAL) {
   260     std::ostringstream sbuf;
   261     sbuf << "Wrong optimal value (" << lp.primal() <<") with "
   262          << lp.solverName() <<"\n     the right optimum is " << exp_opt;
   263     check(std::abs(lp.primal()-exp_opt) < 1e-3, sbuf.str());
   264   }
   265 }
   266 
   267 void aTest(LpSolver & lp)
   268 {
   269   typedef LpSolver LP;
   270 
   271  //The following example is very simple
   272 
   273   typedef LpSolver::Row Row;
   274   typedef LpSolver::Col Col;
   275 
   276 
   277   Col x1 = lp.addCol();
   278   Col x2 = lp.addCol();
   279 
   280 
   281   //Constraints
   282   Row upright=lp.addRow(x1+2*x2 <=1);
   283   lp.addRow(x1+x2 >=-1);
   284   lp.addRow(x1-x2 <=1);
   285   lp.addRow(x1-x2 >=-1);
   286   //Nonnegativity of the variables
   287   lp.colLowerBound(x1, 0);
   288   lp.colLowerBound(x2, 0);
   289   //Objective function
   290   lp.obj(x1+x2);
   291 
   292   lp.sense(lp.MAX);
   293 
   294   //Testing the problem retrieving routines
   295   check(lp.objCoeff(x1)==1,"First term should be 1 in the obj function!");
   296   check(lp.sense() == lp.MAX,"This is a maximization!");
   297   check(lp.coeff(upright,x1)==1,"The coefficient in question is 1!");
   298   check(lp.colLowerBound(x1)==0,
   299         "The lower bound for variable x1 should be 0.");
   300   check(lp.colUpperBound(x1)==LpSolver::INF,
   301         "The upper bound for variable x1 should be infty.");
   302   check(lp.rowLowerBound(upright) == -LpSolver::INF,
   303         "The lower bound for the first row should be -infty.");
   304   check(lp.rowUpperBound(upright)==1,
   305         "The upper bound for the first row should be 1.");
   306   LpSolver::Expr e = lp.row(upright);
   307   check(e[x1] == 1, "The first coefficient should 1.");
   308   check(e[x2] == 2, "The second coefficient should 1.");
   309 
   310   lp.row(upright, x1+x2 <=1);
   311   e = lp.row(upright);
   312   check(e[x1] == 1, "The first coefficient should 1.");
   313   check(e[x2] == 1, "The second coefficient should 1.");
   314 
   315   LpSolver::DualExpr de = lp.col(x1);
   316   check(  de[upright] == 1, "The first coefficient should 1.");
   317 
   318   LpSolver* clp = lp.cloneSolver();
   319 
   320   //Testing the problem retrieving routines
   321   check(clp->objCoeff(x1)==1,"First term should be 1 in the obj function!");
   322   check(clp->sense() == clp->MAX,"This is a maximization!");
   323   check(clp->coeff(upright,x1)==1,"The coefficient in question is 1!");
   324   //  std::cout<<lp.colLowerBound(x1)<<std::endl;
   325   check(clp->colLowerBound(x1)==0,
   326         "The lower bound for variable x1 should be 0.");
   327   check(clp->colUpperBound(x1)==LpSolver::INF,
   328         "The upper bound for variable x1 should be infty.");
   329 
   330   check(lp.rowLowerBound(upright)==-LpSolver::INF,
   331         "The lower bound for the first row should be -infty.");
   332   check(lp.rowUpperBound(upright)==1,
   333         "The upper bound for the first row should be 1.");
   334   e = clp->row(upright);
   335   check(e[x1] == 1, "The first coefficient should 1.");
   336   check(e[x2] == 1, "The second coefficient should 1.");
   337 
   338   de = clp->col(x1);
   339   check(de[upright] == 1, "The first coefficient should 1.");
   340 
   341   delete clp;
   342 
   343   //Maximization of x1+x2
   344   //over the triangle with vertices (0,0) (0,1) (1,0)
   345   double expected_opt=1;
   346   solveAndCheck(lp, LpSolver::OPTIMAL, expected_opt);
   347 
   348   //Minimization
   349   lp.sense(lp.MIN);
   350   expected_opt=0;
   351   solveAndCheck(lp, LpSolver::OPTIMAL, expected_opt);
   352 
   353   //Vertex (-1,0) instead of (0,0)
   354   lp.colLowerBound(x1, -LpSolver::INF);
   355   expected_opt=-1;
   356   solveAndCheck(lp, LpSolver::OPTIMAL, expected_opt);
   357 
   358   //Erase one constraint and return to maximization
   359   lp.erase(upright);
   360   lp.sense(lp.MAX);
   361   expected_opt=LpSolver::INF;
   362   solveAndCheck(lp, LpSolver::UNBOUNDED, expected_opt);
   363 
   364   //Infeasibilty
   365   lp.addRow(x1+x2 <=-2);
   366   solveAndCheck(lp, LpSolver::INFEASIBLE, expected_opt);
   367 
   368 }
   369 
   370 template<class LP>
   371 void cloneTest()
   372 {
   373   //Test for clone/new
   374 
   375   LP* lp = new LP();
   376   LP* lpnew = lp->newSolver();
   377   LP* lpclone = lp->cloneSolver();
   378   delete lp;
   379   delete lpnew;
   380   delete lpclone;
   381 }
   382 
   383 int main()
   384 {
   385   LpSkeleton lp_skel;
   386   lpTest(lp_skel);
   387 
   388 #ifdef LEMON_HAVE_GLPK
   389   {
   390     GlpkLp lp_glpk1,lp_glpk2;
   391     lpTest(lp_glpk1);
   392     aTest(lp_glpk2);
   393     cloneTest<GlpkLp>();
   394   }
   395 #endif
   396 
   397 #ifdef LEMON_HAVE_CPLEX
   398   try {
   399     CplexLp lp_cplex1,lp_cplex2;
   400     lpTest(lp_cplex1);
   401     aTest(lp_cplex2);
   402     cloneTest<CplexLp>();
   403   } catch (CplexEnv::LicenseError& error) {
   404     check(false, error.what());
   405   }
   406 #endif
   407 
   408 #ifdef LEMON_HAVE_SOPLEX
   409   {
   410     SoplexLp lp_soplex1,lp_soplex2;
   411     lpTest(lp_soplex1);
   412     aTest(lp_soplex2);
   413     cloneTest<SoplexLp>();
   414   }
   415 #endif
   416 
   417 #ifdef LEMON_HAVE_CLP
   418   {
   419     ClpLp lp_clp1,lp_clp2;
   420     lpTest(lp_clp1);
   421     aTest(lp_clp2);
   422     cloneTest<ClpLp>();
   423   }
   424 #endif
   425 
   426   return 0;
   427 }