test/lp_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Sun, 11 Aug 2013 21:56:21 +0200
changeset 1098 cf6084618b1b
parent 1078 115031ac8001
child 1105 62dba6c90f35
permissions -rw-r--r--
Merge headmerge to the default branch
     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-2013
     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 int countCols(LpBase & lp) {
    45   int count=0;
    46   for (LpBase::ColIt c(lp); c!=INVALID; ++c) ++count;
    47   return count;
    48 }
    49 
    50 int countRows(LpBase & lp) {
    51   int count=0;
    52   for (LpBase::RowIt r(lp); r!=INVALID; ++r) ++count;
    53   return count;
    54 }
    55 
    56 
    57 void lpTest(LpSolver& lp)
    58 {
    59 
    60   typedef LpSolver LP;
    61 
    62   // Test LpBase::clear()
    63   check(countRows(lp)==0, "Wrong number of rows");
    64   check(countCols(lp)==0, "Wrong number of cols");
    65   lp.addCol(); lp.addRow(); lp.addRow();
    66   check(countRows(lp)==2, "Wrong number of rows");
    67   check(countCols(lp)==1, "Wrong number of cols");
    68   lp.clear();
    69   check(countRows(lp)==0, "Wrong number of rows");
    70   check(countCols(lp)==0, "Wrong number of cols");
    71   lp.addCol(); lp.addCol(); lp.addCol(); lp.addRow();
    72   check(countRows(lp)==1, "Wrong number of rows");
    73   check(countCols(lp)==3, "Wrong number of cols");
    74   lp.clear();
    75 
    76   std::vector<LP::Col> x(10);
    77   //  for(int i=0;i<10;i++) x.push_back(lp.addCol());
    78   lp.addColSet(x);
    79   lp.colLowerBound(x,1);
    80   lp.colUpperBound(x,1);
    81   lp.colBounds(x,1,2);
    82 
    83   std::vector<LP::Col> y(10);
    84   lp.addColSet(y);
    85 
    86   lp.colLowerBound(y,1);
    87   lp.colUpperBound(y,1);
    88   lp.colBounds(y,1,2);
    89 
    90   std::map<int,LP::Col> z;
    91 
    92   z.insert(std::make_pair(12,INVALID));
    93   z.insert(std::make_pair(2,INVALID));
    94   z.insert(std::make_pair(7,INVALID));
    95   z.insert(std::make_pair(5,INVALID));
    96 
    97   lp.addColSet(z);
    98 
    99   lp.colLowerBound(z,1);
   100   lp.colUpperBound(z,1);
   101   lp.colBounds(z,1,2);
   102 
   103   {
   104     LP::Expr e,f,g;
   105     LP::Col p1,p2,p3,p4,p5;
   106     LP::Constr c;
   107 
   108     p1=lp.addCol();
   109     p2=lp.addCol();
   110     p3=lp.addCol();
   111     p4=lp.addCol();
   112     p5=lp.addCol();
   113 
   114     e[p1]=2;
   115     *e=12;
   116     e[p1]+=2;
   117     *e+=12;
   118     e[p1]-=2;
   119     *e-=12;
   120 
   121     e=2;
   122     e=2.2;
   123     e=p1;
   124     e=f;
   125 
   126     e+=2;
   127     e+=2.2;
   128     e+=p1;
   129     e+=f;
   130 
   131     e-=2;
   132     e-=2.2;
   133     e-=p1;
   134     e-=f;
   135 
   136     e*=2;
   137     e*=2.2;
   138     e/=2;
   139     e/=2.2;
   140 
   141     e=((p1+p2)+(p1-p2)+(p1+12)+(12+p1)+(p1-12)+(12-p1)+
   142        (f+12)+(12+f)+(p1+f)+(f+p1)+(f+g)+
   143        (f-12)+(12-f)+(p1-f)+(f-p1)+(f-g)+
   144        2.2*f+f*2.2+f/2.2+
   145        2*f+f*2+f/2+
   146        2.2*p1+p1*2.2+p1/2.2+
   147        2*p1+p1*2+p1/2
   148        );
   149 
   150 
   151     c = (e  <= f  );
   152     c = (e  <= 2.2);
   153     c = (e  <= 2  );
   154     c = (e  <= p1 );
   155     c = (2.2<= f  );
   156     c = (2  <= f  );
   157     c = (p1 <= f  );
   158     c = (p1 <= p2 );
   159     c = (p1 <= 2.2);
   160     c = (p1 <= 2  );
   161     c = (2.2<= p2 );
   162     c = (2  <= p2 );
   163 
   164     c = (e  >= f  );
   165     c = (e  >= 2.2);
   166     c = (e  >= 2  );
   167     c = (e  >= p1 );
   168     c = (2.2>= f  );
   169     c = (2  >= f  );
   170     c = (p1 >= f  );
   171     c = (p1 >= p2 );
   172     c = (p1 >= 2.2);
   173     c = (p1 >= 2  );
   174     c = (2.2>= p2 );
   175     c = (2  >= p2 );
   176 
   177     c = (e  == f  );
   178     c = (e  == 2.2);
   179     c = (e  == 2  );
   180     c = (e  == p1 );
   181     c = (2.2== f  );
   182     c = (2  == f  );
   183     c = (p1 == f  );
   184     //c = (p1 == p2 );
   185     c = (p1 == 2.2);
   186     c = (p1 == 2  );
   187     c = (2.2== p2 );
   188     c = (2  == p2 );
   189 
   190     c = ((2 <= e) <= 3);
   191     c = ((2 <= p1) <= 3);
   192 
   193     c = ((2 >= e) >= 3);
   194     c = ((2 >= p1) >= 3);
   195 
   196     { //Tests for #430
   197       LP::Col v=lp.addCol();
   198       LP::Constr c = v >= -3;
   199       c = c <= 4;
   200       LP::Constr c2;
   201 #if ( __GNUC__ == 4 ) && ( __GNUC_MINOR__ == 3 )
   202       c2 = ( -3 <= v ) <= 4;
   203 #else
   204       c2 = -3 <= v <= 4;
   205 #endif
   206 
   207     }
   208 
   209     e[x[3]]=2;
   210     e[x[3]]=4;
   211     e[x[3]]=1;
   212     *e=12;
   213 
   214     lp.addRow(-LP::INF,e,23);
   215     lp.addRow(-LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);
   216     lp.addRow(-LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23);
   217 
   218     lp.addRow(x[1]+x[3]<=x[5]-3);
   219     lp.addRow((-7<=x[1]+x[3]-12)<=3);
   220     lp.addRow(x[1]<=x[5]);
   221 
   222     std::ostringstream buf;
   223 
   224 
   225     e=((p1+p2)+(p1-0.99*p2));
   226     //e.prettyPrint(std::cout);
   227     //(e<=2).prettyPrint(std::cout);
   228     double tolerance=0.001;
   229     e.simplify(tolerance);
   230     buf << "Coeff. of p2 should be 0.01";
   231     check(e[p2]>0, buf.str());
   232 
   233     tolerance=0.02;
   234     e.simplify(tolerance);
   235     buf << "Coeff. of p2 should be 0";
   236     check(const_cast<const LpSolver::Expr&>(e)[p2]==0, buf.str());
   237 
   238     //Test for clone/new
   239     LP* lpnew = lp.newSolver();
   240     LP* lpclone = lp.cloneSolver();
   241     delete lpnew;
   242     delete lpclone;
   243 
   244   }
   245 
   246   {
   247     LP::DualExpr e,f,g;
   248     LP::Row p1 = INVALID, p2 = INVALID;
   249 
   250     e[p1]=2;
   251     e[p1]+=2;
   252     e[p1]-=2;
   253 
   254     e=p1;
   255     e=f;
   256 
   257     e+=p1;
   258     e+=f;
   259 
   260     e-=p1;
   261     e-=f;
   262 
   263     e*=2;
   264     e*=2.2;
   265     e/=2;
   266     e/=2.2;
   267 
   268     e=((p1+p2)+(p1-p2)+
   269        (p1+f)+(f+p1)+(f+g)+
   270        (p1-f)+(f-p1)+(f-g)+
   271        2.2*f+f*2.2+f/2.2+
   272        2*f+f*2+f/2+
   273        2.2*p1+p1*2.2+p1/2.2+
   274        2*p1+p1*2+p1/2
   275        );
   276   }
   277 
   278 }
   279 
   280 void solveAndCheck(LpSolver& lp, LpSolver::ProblemType stat,
   281                    double exp_opt) {
   282   using std::string;
   283   lp.solve();
   284 
   285   std::ostringstream buf;
   286   buf << "PrimalType should be: " << int(stat) << int(lp.primalType());
   287 
   288   check(lp.primalType()==stat, buf.str());
   289 
   290   if (stat ==  LpSolver::OPTIMAL) {
   291     std::ostringstream sbuf;
   292     sbuf << "Wrong optimal value (" << lp.primal() <<") with "
   293          << lp.solverName() <<"\n     the right optimum is " << exp_opt;
   294     check(std::abs(lp.primal()-exp_opt) < 1e-3, sbuf.str());
   295   }
   296 }
   297 
   298 void aTest(LpSolver & lp)
   299 {
   300   typedef LpSolver LP;
   301 
   302  //The following example is very simple
   303 
   304   typedef LpSolver::Row Row;
   305   typedef LpSolver::Col Col;
   306 
   307 
   308   Col x1 = lp.addCol();
   309   Col x2 = lp.addCol();
   310 
   311 
   312   //Constraints
   313   Row upright=lp.addRow(x1+2*x2 <=1);
   314   lp.addRow(x1+x2 >=-1);
   315   lp.addRow(x1-x2 <=1);
   316   lp.addRow(x1-x2 >=-1);
   317   //Nonnegativity of the variables
   318   lp.colLowerBound(x1, 0);
   319   lp.colLowerBound(x2, 0);
   320   //Objective function
   321   lp.obj(x1+x2);
   322 
   323   lp.sense(lp.MAX);
   324 
   325   //Testing the problem retrieving routines
   326   check(lp.objCoeff(x1)==1,"First term should be 1 in the obj function!");
   327   check(lp.sense() == lp.MAX,"This is a maximization!");
   328   check(lp.coeff(upright,x1)==1,"The coefficient in question is 1!");
   329   check(lp.colLowerBound(x1)==0,
   330         "The lower bound for variable x1 should be 0.");
   331   check(lp.colUpperBound(x1)==LpSolver::INF,
   332         "The upper bound for variable x1 should be infty.");
   333   check(lp.rowLowerBound(upright) == -LpSolver::INF,
   334         "The lower bound for the first row should be -infty.");
   335   check(lp.rowUpperBound(upright)==1,
   336         "The upper bound for the first row should be 1.");
   337   LpSolver::Expr e = lp.row(upright);
   338   check(e[x1] == 1, "The first coefficient should 1.");
   339   check(e[x2] == 2, "The second coefficient should 1.");
   340 
   341   lp.row(upright, x1+x2 <=1);
   342   e = lp.row(upright);
   343   check(e[x1] == 1, "The first coefficient should 1.");
   344   check(e[x2] == 1, "The second coefficient should 1.");
   345 
   346   LpSolver::DualExpr de = lp.col(x1);
   347   check(  de[upright] == 1, "The first coefficient should 1.");
   348 
   349   LpSolver* clp = lp.cloneSolver();
   350 
   351   //Testing the problem retrieving routines
   352   check(clp->objCoeff(x1)==1,"First term should be 1 in the obj function!");
   353   check(clp->sense() == clp->MAX,"This is a maximization!");
   354   check(clp->coeff(upright,x1)==1,"The coefficient in question is 1!");
   355   //  std::cout<<lp.colLowerBound(x1)<<std::endl;
   356   check(clp->colLowerBound(x1)==0,
   357         "The lower bound for variable x1 should be 0.");
   358   check(clp->colUpperBound(x1)==LpSolver::INF,
   359         "The upper bound for variable x1 should be infty.");
   360 
   361   check(lp.rowLowerBound(upright)==-LpSolver::INF,
   362         "The lower bound for the first row should be -infty.");
   363   check(lp.rowUpperBound(upright)==1,
   364         "The upper bound for the first row should be 1.");
   365   e = clp->row(upright);
   366   check(e[x1] == 1, "The first coefficient should 1.");
   367   check(e[x2] == 1, "The second coefficient should 1.");
   368 
   369   de = clp->col(x1);
   370   check(de[upright] == 1, "The first coefficient should 1.");
   371 
   372   delete clp;
   373 
   374   //Maximization of x1+x2
   375   //over the triangle with vertices (0,0) (0,1) (1,0)
   376   double expected_opt=1;
   377   solveAndCheck(lp, LpSolver::OPTIMAL, expected_opt);
   378 
   379   //Minimization
   380   lp.sense(lp.MIN);
   381   expected_opt=0;
   382   solveAndCheck(lp, LpSolver::OPTIMAL, expected_opt);
   383 
   384   //Vertex (-1,0) instead of (0,0)
   385   lp.colLowerBound(x1, -LpSolver::INF);
   386   expected_opt=-1;
   387   solveAndCheck(lp, LpSolver::OPTIMAL, expected_opt);
   388 
   389   //Erase one constraint and return to maximization
   390   lp.erase(upright);
   391   lp.sense(lp.MAX);
   392   expected_opt=LpSolver::INF;
   393   solveAndCheck(lp, LpSolver::UNBOUNDED, expected_opt);
   394 
   395   //Infeasibilty
   396   lp.addRow(x1+x2 <=-2);
   397   solveAndCheck(lp, LpSolver::INFEASIBLE, expected_opt);
   398 
   399 }
   400 
   401 template<class LP>
   402 void cloneTest()
   403 {
   404   //Test for clone/new
   405 
   406   LP* lp = new LP();
   407   LP* lpnew = lp->newSolver();
   408   LP* lpclone = lp->cloneSolver();
   409   delete lp;
   410   delete lpnew;
   411   delete lpclone;
   412 }
   413 
   414 int main()
   415 {
   416   LpSkeleton lp_skel;
   417   lpTest(lp_skel);
   418 
   419 #ifdef LEMON_HAVE_GLPK
   420   {
   421     GlpkLp lp_glpk1,lp_glpk2;
   422     lpTest(lp_glpk1);
   423     aTest(lp_glpk2);
   424     cloneTest<GlpkLp>();
   425   }
   426 #endif
   427 
   428 #ifdef LEMON_HAVE_CPLEX
   429   try {
   430     CplexLp lp_cplex1,lp_cplex2;
   431     lpTest(lp_cplex1);
   432     aTest(lp_cplex2);
   433     cloneTest<CplexLp>();
   434   } catch (CplexEnv::LicenseError& error) {
   435     check(false, error.what());
   436   }
   437 #endif
   438 
   439 #ifdef LEMON_HAVE_SOPLEX
   440   {
   441     SoplexLp lp_soplex1,lp_soplex2;
   442     lpTest(lp_soplex1);
   443     aTest(lp_soplex2);
   444     cloneTest<SoplexLp>();
   445   }
   446 #endif
   447 
   448 #ifdef LEMON_HAVE_CLP
   449   {
   450     ClpLp lp_clp1,lp_clp2;
   451     lpTest(lp_clp1);
   452     aTest(lp_clp2);
   453     cloneTest<ClpLp>();
   454   }
   455 #endif
   456 
   457   return 0;
   458 }