test/lp_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 20 Jan 2021 16:31:29 +0100
changeset 1206 86a5b114a066
parent 1131 4add05447ca0
permissions -rw-r--r--
Implement CplLp::write() for LP format (#640)
     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 #include <lemon/concept_check.h>
    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 #ifdef LEMON_HAVE_LP
    43 #include <lemon/lp.h>
    44 #endif
    45 using namespace lemon;
    46 
    47 int countCols(LpBase & lp) {
    48   int count=0;
    49   for (LpBase::ColIt c(lp); c!=INVALID; ++c) ++count;
    50 #ifdef LEMON_CXX11
    51   int cnt = 0;
    52   for(auto c: lp.cols()) { cnt++; ::lemon::ignore_unused_variable_warning(c); }
    53   check(count == cnt, "Wrong STL iterator");
    54 #endif
    55   return count;
    56 }
    57 
    58 int countRows(LpBase & lp) {
    59   int count=0;
    60   for (LpBase::RowIt r(lp); r!=INVALID; ++r) ++count;
    61 #ifdef LEMON_CXX11
    62   int cnt = 0;
    63   for(auto r: lp.rows()) { cnt++; ::lemon::ignore_unused_variable_warning(r); }
    64   check(count == cnt, "Wrong STL iterator");
    65 #endif
    66   return count;
    67 }
    68 
    69 
    70 void lpTest(LpSolver& lp)
    71 {
    72 
    73   typedef LpSolver LP;
    74 
    75   // Test LpBase::clear()
    76   check(countRows(lp)==0, "Wrong number of rows");
    77   check(countCols(lp)==0, "Wrong number of cols");
    78   lp.addCol(); lp.addRow(); lp.addRow();
    79   check(countRows(lp)==2, "Wrong number of rows");
    80   check(countCols(lp)==1, "Wrong number of cols");
    81   lp.clear();
    82   check(countRows(lp)==0, "Wrong number of rows");
    83   check(countCols(lp)==0, "Wrong number of cols");
    84   lp.addCol(); lp.addCol(); lp.addCol(); lp.addRow();
    85   check(countRows(lp)==1, "Wrong number of rows");
    86   check(countCols(lp)==3, "Wrong number of cols");
    87   lp.clear();
    88 
    89   std::vector<LP::Col> x(10);
    90   //  for(int i=0;i<10;i++) x.push_back(lp.addCol());
    91   lp.addColSet(x);
    92   lp.colLowerBound(x,1);
    93   lp.colUpperBound(x,1);
    94   lp.colBounds(x,1,2);
    95 
    96   std::vector<LP::Col> y(10);
    97   lp.addColSet(y);
    98 
    99   lp.colLowerBound(y,1);
   100   lp.colUpperBound(y,1);
   101   lp.colBounds(y,1,2);
   102 
   103   std::map<int,LP::Col> z;
   104 
   105   z.insert(std::make_pair(12,INVALID));
   106   z.insert(std::make_pair(2,INVALID));
   107   z.insert(std::make_pair(7,INVALID));
   108   z.insert(std::make_pair(5,INVALID));
   109 
   110   lp.addColSet(z);
   111 
   112   lp.colLowerBound(z,1);
   113   lp.colUpperBound(z,1);
   114   lp.colBounds(z,1,2);
   115 
   116   {
   117     LP::Expr e,f,g;
   118     LP::Col p1,p2,p3,p4,p5;
   119     LP::Constr c;
   120 
   121     p1=lp.addCol();
   122     p2=lp.addCol();
   123     p3=lp.addCol();
   124     p4=lp.addCol();
   125     p5=lp.addCol();
   126 
   127     e[p1]=2;
   128     *e=12;
   129     e[p1]+=2;
   130     *e+=12;
   131     e[p1]-=2;
   132     *e-=12;
   133 
   134     e=2;
   135     e=2.2;
   136     e=p1;
   137     e=f;
   138 
   139     e+=2;
   140     e+=2.2;
   141     e+=p1;
   142     e+=f;
   143 
   144     e-=2;
   145     e-=2.2;
   146     e-=p1;
   147     e-=f;
   148 
   149     e*=2;
   150     e*=2.2;
   151     e/=2;
   152     e/=2.2;
   153 
   154     e=((p1+p2)+(p1-p2)+(p1+12)+(12+p1)+(p1-12)+(12-p1)+
   155        (f+12)+(12+f)+(p1+f)+(f+p1)+(f+g)+
   156        (f-12)+(12-f)+(p1-f)+(f-p1)+(f-g)+
   157        2.2*f+f*2.2+f/2.2+
   158        2*f+f*2+f/2+
   159        2.2*p1+p1*2.2+p1/2.2+
   160        2*p1+p1*2+p1/2
   161        );
   162 
   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 = (e  == f  );
   191     c = (e  == 2.2);
   192     c = (e  == 2  );
   193     c = (e  == p1 );
   194     c = (2.2== f  );
   195     c = (2  == f  );
   196     c = (p1 == f  );
   197     //c = (p1 == p2 );
   198     c = (p1 == 2.2);
   199     c = (p1 == 2  );
   200     c = (2.2== p2 );
   201     c = (2  == p2 );
   202 
   203     c = ((2 <= e) <= 3);
   204     c = ((2 <= p1) <= 3);
   205 
   206     c = ((2 >= e) >= 3);
   207     c = ((2 >= p1) >= 3);
   208 
   209     { //Tests for #430
   210       LP::Col v=lp.addCol();
   211       LP::Constr c = v >= -3;
   212       c = c <= 4;
   213       LP::Constr c2;
   214 #if ( __GNUC__ == 4 ) && ( __GNUC_MINOR__ == 3 )
   215       c2 = ( -3 <= v ) <= 4;
   216 #else
   217       c2 = -3 <= v <= 4;
   218 #endif
   219 
   220     }
   221 
   222     e[x[3]]=2;
   223     e[x[3]]=4;
   224     e[x[3]]=1;
   225     *e=12;
   226 
   227     lp.addRow(-LP::INF,e,23);
   228     lp.addRow(-LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);
   229     lp.addRow(-LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23);
   230 
   231     lp.addRow(x[1]+x[3]<=x[5]-3);
   232     lp.addRow((-7<=x[1]+x[3]-12)<=3);
   233     lp.addRow(x[1]<=x[5]);
   234 
   235     std::ostringstream buf;
   236 
   237 
   238     e=((p1+p2)+(p1-0.99*p2));
   239     //e.prettyPrint(std::cout);
   240     //(e<=2).prettyPrint(std::cout);
   241     double tolerance=0.001;
   242     e.simplify(tolerance);
   243     buf << "Coeff. of p2 should be 0.01";
   244     check(e[p2]>0, buf.str());
   245 
   246     tolerance=0.02;
   247     e.simplify(tolerance);
   248     buf << "Coeff. of p2 should be 0";
   249     check(const_cast<const LpSolver::Expr&>(e)[p2]==0, buf.str());
   250 
   251     //Test for clone/new
   252     LP* lpnew = lp.newSolver();
   253     LP* lpclone = lp.cloneSolver();
   254     delete lpnew;
   255     delete lpclone;
   256 
   257   }
   258 
   259   {
   260     LP::DualExpr e,f,g;
   261     LP::Row p1 = INVALID, p2 = INVALID;
   262 
   263     e[p1]=2;
   264     e[p1]+=2;
   265     e[p1]-=2;
   266 
   267     e=p1;
   268     e=f;
   269 
   270     e+=p1;
   271     e+=f;
   272 
   273     e-=p1;
   274     e-=f;
   275 
   276     e*=2;
   277     e*=2.2;
   278     e/=2;
   279     e/=2.2;
   280 
   281     e=((p1+p2)+(p1-p2)+
   282        (p1+f)+(f+p1)+(f+g)+
   283        (p1-f)+(f-p1)+(f-g)+
   284        2.2*f+f*2.2+f/2.2+
   285        2*f+f*2+f/2+
   286        2.2*p1+p1*2.2+p1/2.2+
   287        2*p1+p1*2+p1/2
   288        );
   289   }
   290 
   291 }
   292 
   293 void solveAndCheck(LpSolver& lp, LpSolver::ProblemType stat,
   294                    double exp_opt) {
   295   using std::string;
   296   lp.solve();
   297 
   298   std::ostringstream buf;
   299   buf << "PrimalType should be: " << int(stat) << int(lp.primalType());
   300 
   301   check(lp.primalType()==stat, buf.str());
   302 
   303   if (stat ==  LpSolver::OPTIMAL) {
   304     std::ostringstream sbuf;
   305     sbuf << "Wrong optimal value (" << lp.primal() <<") with "
   306          << lp.solverName() <<"\n     the right optimum is " << exp_opt;
   307     check(std::abs(lp.primal()-exp_opt) < 1e-3, sbuf.str());
   308   }
   309 }
   310 
   311 void aTest(LpSolver & lp)
   312 {
   313   typedef LpSolver LP;
   314 
   315  //The following example is very simple
   316 
   317   typedef LpSolver::Row Row;
   318   typedef LpSolver::Col Col;
   319 
   320 
   321   Col x1 = lp.addCol();
   322   Col x2 = lp.addCol();
   323 
   324 
   325   //Constraints
   326   Row upright=lp.addRow(x1+2*x2 <=1);
   327   lp.addRow(x1+x2 >=-1);
   328   lp.addRow(x1-x2 <=1);
   329   lp.addRow(x1-x2 >=-1);
   330   //Nonnegativity of the variables
   331   lp.colLowerBound(x1, 0);
   332   lp.colLowerBound(x2, 0);
   333   //Objective function
   334   lp.obj(x1+x2);
   335 
   336   lp.sense(lp.MAX);
   337 
   338   //Testing the problem retrieving routines
   339   check(lp.objCoeff(x1)==1,"First term should be 1 in the obj function!");
   340   check(lp.sense() == lp.MAX,"This is a maximization!");
   341   check(lp.coeff(upright,x1)==1,"The coefficient in question is 1!");
   342   check(lp.coeff(upright,x2)==2,"The coefficient in question is 1!");
   343   check(lp.colLowerBound(x1)==0,
   344         "The lower bound for variable x1 should be 0.");
   345   check(lp.colUpperBound(x1)==LpSolver::INF,
   346         "The upper bound for variable x1 should be infty.");
   347   check(lp.rowLowerBound(upright) == -LpSolver::INF,
   348         "The lower bound for the first row should be -infty.");
   349   check(lp.rowUpperBound(upright)==1,
   350         "The upper bound for the first row should be 1.");
   351   LpSolver::Expr e = lp.row(upright);
   352   check(e[x1] == 1, "The first coefficient should 1.");
   353   check(e[x2] == 2, "The second coefficient should 1.");
   354 
   355   lp.row(upright, x1+x2 <=1);
   356   e = lp.row(upright);
   357   check(e[x1] == 1, "The first coefficient should 1.");
   358   check(e[x2] == 1, "The second coefficient should 1.");
   359 
   360   LpSolver::DualExpr de = lp.col(x1);
   361   check(  de[upright] == 1, "The first coefficient should 1.");
   362 
   363   LpSolver* clp = lp.cloneSolver();
   364 
   365   //Testing the problem retrieving routines
   366   check(clp->objCoeff(x1)==1,"First term should be 1 in the obj function!");
   367   check(clp->sense() == clp->MAX,"This is a maximization!");
   368   check(clp->coeff(upright,x1)==1,"The coefficient in question is 1!");
   369   //  std::cout<<lp.colLowerBound(x1)<<std::endl;
   370   check(clp->colLowerBound(x1)==0,
   371         "The lower bound for variable x1 should be 0.");
   372   check(clp->colUpperBound(x1)==LpSolver::INF,
   373         "The upper bound for variable x1 should be infty.");
   374 
   375   check(lp.rowLowerBound(upright)==-LpSolver::INF,
   376         "The lower bound for the first row should be -infty.");
   377   check(lp.rowUpperBound(upright)==1,
   378         "The upper bound for the first row should be 1.");
   379   e = clp->row(upright);
   380   check(e[x1] == 1, "The first coefficient should 1.");
   381   check(e[x2] == 1, "The second coefficient should 1.");
   382 
   383   de = clp->col(x1);
   384   check(de[upright] == 1, "The first coefficient should 1.");
   385 
   386   delete clp;
   387 
   388   //Maximization of x1+x2
   389   //over the triangle with vertices (0,0) (0,1) (1,0)
   390   double expected_opt=1;
   391   solveAndCheck(lp, LpSolver::OPTIMAL, expected_opt);
   392 
   393   //Minimization
   394   lp.sense(lp.MIN);
   395   expected_opt=0;
   396   solveAndCheck(lp, LpSolver::OPTIMAL, expected_opt);
   397 
   398   //Vertex (-1,0) instead of (0,0)
   399   lp.colLowerBound(x1, -LpSolver::INF);
   400   expected_opt=-1;
   401   solveAndCheck(lp, LpSolver::OPTIMAL, expected_opt);
   402 
   403   //Erase one constraint and return to maximization
   404   lp.erase(upright);
   405   lp.sense(lp.MAX);
   406   expected_opt=LpSolver::INF;
   407   solveAndCheck(lp, LpSolver::UNBOUNDED, expected_opt);
   408 
   409   //Infeasibilty
   410   lp.addRow(x1+x2 <=-2);
   411   solveAndCheck(lp, LpSolver::INFEASIBLE, expected_opt);
   412 
   413 }
   414 
   415 template<class LP>
   416 void cloneTest()
   417 {
   418   //Test for clone/new
   419 
   420   LP* lp = new LP();
   421   LP* lpnew = lp->newSolver();
   422   LP* lpclone = lp->cloneSolver();
   423   delete lp;
   424   delete lpnew;
   425   delete lpclone;
   426 }
   427 
   428 template<class LP>
   429 void rangeConstraintTest()
   430 {
   431   LP lp;
   432   // Add two columns (variables) to the problem
   433   typename LP::Col x1 = lp.addCol();
   434   typename LP::Col x2 = lp.addCol();
   435   // Add rows (constraints) to the problem
   436   lp.addRow(x1 - 5 <= x2);
   437     lp.addRow(0 <= 2 * x1 + x2 <= 25);
   438   
   439   // Set lower and upper bounds for the columns (variables)
   440   lp.colLowerBound(x1, 0);
   441   lp.colUpperBound(x2, 10);
   442   
   443   // Specify the objective function
   444   lp.max();
   445   lp.obj(5 * x1 + 3 * x2);
   446   
   447   // Solve the problem using the underlying LP solver
   448   lp.solve();
   449   // Print the results
   450   check(lp.primalType() == LP::OPTIMAL, "Optimal solution is not found");
   451   check(lp.primal() <= 67.501 && lp.primal() >= 67.499, "Wrong objective value");
   452   check(lp.primal(x1) <= 7.501 && lp.primal(x1) >= 7.499, "Wrong value for x1");
   453   check(lp.primal(x2) <= 10.001 && lp.primal(x2) >= 9.999, "Wrong value for x2");
   454 }
   455 
   456 int main()
   457 {
   458   LpSkeleton lp_skel;
   459   lpTest(lp_skel);
   460 
   461 #ifdef LEMON_HAVE_LP
   462   {
   463     Lp lp,lp2;
   464     lpTest(lp);
   465     aTest(lp2);
   466     cloneTest<Lp>();
   467   }
   468 #endif
   469 
   470 #ifdef LEMON_HAVE_GLPK
   471   {
   472     GlpkLp lp_glpk1,lp_glpk2;
   473     lpTest(lp_glpk1);
   474     aTest(lp_glpk2);
   475     cloneTest<GlpkLp>();
   476     rangeConstraintTest<GlpkLp>();
   477   }
   478 #endif
   479 
   480 #ifdef LEMON_HAVE_CPLEX
   481   try {
   482     CplexLp lp_cplex1,lp_cplex2;
   483     lpTest(lp_cplex1);
   484     aTest(lp_cplex2);
   485     cloneTest<CplexLp>();
   486     rangeConstraintTest<CplexLp>();
   487   } catch (CplexEnv::LicenseError& error) {
   488     check(false, error.what());
   489   }
   490 #endif
   491 
   492 #ifdef LEMON_HAVE_SOPLEX
   493   {
   494     SoplexLp lp_soplex1,lp_soplex2;
   495     lpTest(lp_soplex1);
   496     aTest(lp_soplex2);
   497     cloneTest<SoplexLp>();
   498     rangeConstraintTest<Soplex>();
   499   }
   500 #endif
   501 
   502 #ifdef LEMON_HAVE_CLP
   503   {
   504     ClpLp lp_clp1,lp_clp2;
   505     lpTest(lp_clp1);
   506     aTest(lp_clp2);
   507     cloneTest<ClpLp>();
   508     rangeConstraintTest<ClpLp>();
   509   }
   510 #endif
   511 
   512   return 0;
   513 }