Reimplemented Suurballe class.
- The new version is the specialized version of CapacityScaling.
- It is about 10-20 times faster than the former Suurballe algorithm
and about 20-50 percent faster than CapacityScaling.
- Doc improvements.
- The test file is also replaced.
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,p2,p3,p4,p5;
244 2.2*p1+p1*2.2+p1/2.2+
252 void solveAndCheck(LpSolverBase& lp, LpSolverBase::SolutionStatus stat,
257 std::ostringstream buf;
258 buf << "Primalstatus should be: " << int(stat);
260 // itoa(stat,buf1, 10);
261 check(lp.primalStatus()==stat, buf.str());
263 if (stat == LpSolverBase::OPTIMAL) {
264 std::ostringstream sbuf;
265 sbuf << "Wrong optimal value: the right optimum is " << exp_opt;
266 check(std::abs(lp.primalValue()-exp_opt) < 1e-3, sbuf.str());
271 void aTest(LpSolverBase & lp)
273 typedef LpSolverBase LP;
275 //The following example is very simple
277 typedef LpSolverBase::Row Row;
278 typedef LpSolverBase::Col Col;
281 Col x1 = lp.addCol();
282 Col x2 = lp.addCol();
286 Row upright=lp.addRow(x1+x2 <=1);
287 lp.addRow(x1+x2 >=-1);
288 lp.addRow(x1-x2 <=1);
289 lp.addRow(x1-x2 >=-1);
290 //Nonnegativity of the variables
291 lp.colLowerBound(x1, 0);
292 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,"The lower bound for variable x1 should be 0.");
305 check( lp.colUpperBound(x1)==LpSolverBase::INF,"The upper bound for variable x1 should be infty.");
306 LpSolverBase::Value lb,ub;
307 lp.getRowBounds(upright,lb,ub);
308 check( lb==-LpSolverBase::INF,"The lower bound for the first row should be -infty.");
309 check( ub==1,"The upper bound for the first row should be 1.");
312 //Maximization of x1+x2
313 //over the triangle with vertices (0,0) (0,1) (1,0)
314 double expected_opt=1;
315 solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt);
320 solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt);
322 //Vertex (-1,0) instead of (0,0)
323 lp.colLowerBound(x1, -LpSolverBase::INF);
325 solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt);
327 //Erase one constraint and return to maximization
328 lp.eraseRow(upright);
330 expected_opt=LpSolverBase::INF;
331 solveAndCheck(lp, LpSolverBase::INFINITE, expected_opt);
334 lp.addRow(x1+x2 <=-2);
335 solveAndCheck(lp, LpSolverBase::INFEASIBLE, expected_opt);
337 //Change problem and forget to solve
339 check(lp.primalStatus()==LpSolverBase::UNDEFINED,"Primalstatus should be UNDEFINED");
342 // if (lp.primalStatus()==LpSolverBase::OPTIMAL){
343 // std::cout<< "Z = "<<lp.primalValue()
344 // << " (error = " << lp.primalValue()-expected_opt
345 // << "); x1 = "<<lp.primal(x1)
346 // << "; x2 = "<<lp.primal(x2)
351 // std::cout<<lp.primalStatus()<<std::endl;
352 // std::cout<<"Optimal solution not found!"<<std::endl;
366 LpGlpk lp_glpk1,lp_glpk2;
372 LpCplex lp_cplex1,lp_cplex2;
378 LpSoplex lp_soplex1,lp_soplex2;