1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
20 #include <lemon/lp_skeleton.h>
21 #include "test_tools.h"
22 #include <lemon/tolerance.h>
25 #include <lemon/config.h>
29 #include <lemon/lp_glpk.h>
33 #include <lemon/lp_cplex.h>
37 #include <lemon/lp_soplex.h>
40 using namespace lemon;
42 void lpTest(LpSolverBase & lp)
47 typedef LpSolverBase LP;
49 std::vector<LP::Col> x(10);
50 // for(int i=0;i<10;i++) x.push_back(lp.addCol());
52 lp.colLowerBound(x,1);
53 lp.colUpperBound(x,1);
57 std::vector<LP::Col> y(10);
60 lp.colLowerBound(y,1);
61 lp.colUpperBound(y,1);
64 std::map<int,LP::Col> z;
66 z.insert(std::make_pair(12,INVALID));
67 z.insert(std::make_pair(2,INVALID));
68 z.insert(std::make_pair(7,INVALID));
69 z.insert(std::make_pair(5,INVALID));
73 lp.colLowerBound(z,1);
74 lp.colUpperBound(z,1);
79 LP::Col p1,p2,p3,p4,p5;
115 e=((p1+p2)+(p1-p2)+(p1+12)+(12+p1)+(p1-12)+(12-p1)+
116 (f+12)+(12+f)+(p1+f)+(f+p1)+(f+g)+
117 (f-12)+(12-f)+(p1-f)+(f-p1)+(f-g)+
120 2.2*p1+p1*2.2+p1/2.2+
175 lp.addRow(LP::INF,e,23);
176 lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);
177 lp.addRow(LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23);
179 lp.addRow(x[1]+x[3]<=x[5]-3);
180 lp.addRow(-7<=x[1]+x[3]-12<=3);
181 lp.addRow(x[1]<=x[5]);
183 std::ostringstream buf;
186 //Checking the simplify function
188 // //How to check the simplify function? A map gives no information
189 // //on the question whether a given key is or is not stored in it, or
191 // Yes, it does, using the find() function.
194 buf << "Coeff. of p2 should be 0";
195 // std::cout<<e[p1]<<e[p2]<<e[p3]<<std::endl;
196 check(e.find(p2)==e.end(), buf.str());
201 e=((p1+p2)+(p1-0.99*p2));
202 //e.prettyPrint(std::cout);
203 //(e<=2).prettyPrint(std::cout);
204 double tolerance=0.001;
205 e.simplify(tolerance);
206 buf << "Coeff. of p2 should be 0.01";
207 check(e[p2]>0, buf.str());
210 e.simplify(tolerance);
211 buf << "Coeff. of p2 should be 0";
212 check(e.find(p2)==e.end(), buf.str());
219 LP::Row p1 = INVALID, p2 = INVALID, p3 = INVALID,
220 p4 = INVALID, p5 = INVALID;
245 2.2*p1+p1*2.2+p1/2.2+
253 void solveAndCheck(LpSolverBase& lp, LpSolverBase::SolutionStatus stat,
258 std::ostringstream buf;
259 buf << "Primalstatus should be: " << int(stat);
261 // itoa(stat,buf1, 10);
262 check(lp.primalStatus()==stat, buf.str());
264 if (stat == LpSolverBase::OPTIMAL) {
265 std::ostringstream sbuf;
266 sbuf << "Wrong optimal value: the right optimum is " << exp_opt;
267 check(std::abs(lp.primalValue()-exp_opt) < 1e-3, sbuf.str());
272 void aTest(LpSolverBase & lp)
274 typedef LpSolverBase LP;
276 //The following example is very simple
278 typedef LpSolverBase::Row Row;
279 typedef LpSolverBase::Col Col;
282 Col x1 = lp.addCol();
283 Col x2 = lp.addCol();
287 Row upright=lp.addRow(x1+x2 <=1);
288 lp.addRow(x1+x2 >=-1);
289 lp.addRow(x1-x2 <=1);
290 lp.addRow(x1-x2 >=-1);
291 //Nonnegativity of the variables
292 lp.colLowerBound(x1, 0);
293 lp.colLowerBound(x2, 0);
299 //Testing the problem retrieving routines
300 check(lp.objCoeff(x1)==1,"First term should be 1 in the obj function!");
301 check(lp.isMax(),"This is a maximization!");
302 check(lp.coeff(upright,x1)==1,"The coefficient in question is 1!");
303 // std::cout<<lp.colLowerBound(x1)<<std::endl;
304 check( lp.colLowerBound(x1)==0,
305 "The lower bound for variable x1 should be 0.");
306 check( lp.colUpperBound(x1)==LpSolverBase::INF,
307 "The upper bound for variable x1 should be infty.");
308 LpSolverBase::Value lb,ub;
309 lp.getRowBounds(upright,lb,ub);
310 check( lb==-LpSolverBase::INF,
311 "The lower bound for the first row should be -infty.");
312 check( ub==1,"The upper bound for the first row should be 1.");
313 LpSolverBase::Expr e = lp.row(upright);
314 check( e.size() == 2, "The row retrieval gives back wrong expression.");
315 check( e[x1] == 1, "The first coefficient should 1.");
316 check( e[x2] == 1, "The second coefficient should 1.");
318 LpSolverBase::DualExpr de = lp.col(x1);
319 check( de.size() == 4, "The col retrieval gives back wrong expression.");
320 check( de[upright] == 1, "The first coefficient should 1.");
322 LpSolverBase* clp = lp.copyLp();
324 //Testing the problem retrieving routines
325 check(clp->objCoeff(x1)==1,"First term should be 1 in the obj function!");
326 check(clp->isMax(),"This is a maximization!");
327 check(clp->coeff(upright,x1)==1,"The coefficient in question is 1!");
328 // std::cout<<lp.colLowerBound(x1)<<std::endl;
329 check( clp->colLowerBound(x1)==0,
330 "The lower bound for variable x1 should be 0.");
331 check( clp->colUpperBound(x1)==LpSolverBase::INF,
332 "The upper bound for variable x1 should be infty.");
334 clp->getRowBounds(upright,lb,ub);
335 check( lb==-LpSolverBase::INF,
336 "The lower bound for the first row should be -infty.");
337 check( ub==1,"The upper bound for the first row should be 1.");
338 e = clp->row(upright);
339 check( e.size() == 2, "The row retrieval gives back wrong expression.");
340 check( e[x1] == 1, "The first coefficient should 1.");
341 check( e[x2] == 1, "The second coefficient should 1.");
344 check( de.size() == 4, "The col retrieval gives back wrong expression.");
345 check( de[upright] == 1, "The first coefficient should 1.");
349 //Maximization of x1+x2
350 //over the triangle with vertices (0,0) (0,1) (1,0)
351 double expected_opt=1;
352 solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt);
357 solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt);
359 //Vertex (-1,0) instead of (0,0)
360 lp.colLowerBound(x1, -LpSolverBase::INF);
362 solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt);
364 //Erase one constraint and return to maximization
365 lp.eraseRow(upright);
367 expected_opt=LpSolverBase::INF;
368 solveAndCheck(lp, LpSolverBase::INFINITE, expected_opt);
371 lp.addRow(x1+x2 <=-2);
372 solveAndCheck(lp, LpSolverBase::INFEASIBLE, expected_opt);
374 //Change problem and forget to solve
376 check(lp.primalStatus()==LpSolverBase::UNDEFINED,
377 "Primalstatus should be UNDEFINED");
381 // if (lp.primalStatus()==LpSolverBase::OPTIMAL){
382 // std::cout<< "Z = "<<lp.primalValue()
383 // << " (error = " << lp.primalValue()-expected_opt
384 // << "); x1 = "<<lp.primal(x1)
385 // << "; x2 = "<<lp.primal(x2)
390 // std::cout<<lp.primalStatus()<<std::endl;
391 // std::cout<<"Optimal solution not found!"<<std::endl;
405 LpGlpk lp_glpk1,lp_glpk2;
411 LpCplex lp_cplex1,lp_cplex2;
417 LpSoplex lp_soplex1,lp_soplex2;